算法基础五

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解题思路：这里数组的删除并不是真的删除，只是将要删除的元素移动到数组的后面，然后返回数组实际有效的长度即可。

public int removeElement(int[] nums, int val) {if (nums == null || nums.length == 0) {return 0;}int len = nums.length;int index = 0;for(int i = 0; i < len; i++) {if (nums[i] != val) {nums[index++] = nums[i];                }}return index;}

两数相除

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用 乘法、除法和取余运算。
整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。

示例 1:
输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = 3.33333… ，向零截断后得到 3 。
示例 2:
输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = -2.33333… ，向零截断后得到 -2 。

解题思路：可以用二分搜索来做。把除法运算后的商作为搜索目标，商的取值范围是[0，dividend]。利用二分好到（商 + 1）* 除数>被除数并且 商 * 除数 < 被除数或者 （商 + 1）* 除数 > 被除数 并且 商 * 除数 < 被除数的时候，就算找到商了，其余情况继续二分即可。

public int divide(int dividend, int divisor) {// 考虑被除数为最小值的情况if (dividend == Integer.MIN_VALUE) {if (divisor == 1) {return Integer.MIN_VALUE;}if (divisor == -1) {return Integer.MAX_VALUE;}}// 考虑除数为最小值的情况if (divisor == Integer.MIN_VALUE) {return dividend == Integer.MIN_VALUE ? 1 : 0;}// 考虑被除数为 0 的情况if (dividend == 0) {return 0;}// 一般情况，使用二分查找// 将所有的正数取相反数，这样就只需要考虑一种情况boolean rev = false;if (dividend > 0) {dividend = -dividend;rev = !rev;}if (divisor > 0) {divisor = -divisor;rev = !rev;}int left = 1, right = Integer.MAX_VALUE, ans = 0;while (left <= right) {// 注意溢出，并且不能使用除法int mid = left + ((right - left) >> 1);boolean check = quickAdd(divisor, mid, dividend);if (check) {ans = mid;// 注意溢出if (mid == Integer.MAX_VALUE) {break;}left = mid + 1;} else {right = mid - 1;}}return rev ? -ans : ans;}// 快速乘public boolean quickAdd(int y, int z, int x) {// x 和 y 是负数，z 是正数// 需要判断 z * y >= x 是否成立int result = 0, add = y;while (z != 0) {if ((z & 1) != 0) {// 需要保证 result + add >= xif (result < x - add) {return false;}result += add;}if (z != 1) {// 需要保证 add + add >= xif (add < x - add) {return false;}add += add;}// 不能使用除法z >>= 1;}return true;}

串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：
输入：s = “barfoothefoobarman”, words = [“foo”,“bar”] 输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。 子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。 子串 “foobar” 开始位置是 9。它是words 中以 [“foo”,“bar”] 顺序排列的连接。 输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”] 输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。 s 中没有子串长度为 16 并且等于 words的任何顺序排列的连接。 所以我们返回一个空数组。
示例 3：
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]，输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。 子串 “barthefoo” 开始位置是 9。它是 words 中以[“bar”,“the”,“foo”] 顺序排列的连接。 子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。

解题思路：这道题有两个前提条件。1，字符串数组里面的字符串长度都是一样的；2，字符串数组中的字符串都要连续连在一起，前后顺序可以任意组合。
先将字符串数组中所有字符串都存到map中，并累计出现的次数，然后从源字符串从头开始遍历，每次判断字符串数组里面的字符串是否全部用完，如果全部用完并且长度正好是字符串数组任意排列组合的长度，就记录这个组合的起始下标。

public List<Integer> findSubstring(String s, String[] words) {List<Integer> res = new ArrayList<Integer>();int wordNum = words.length;if (wordNum == 0) {return res;}int wordLen = words[0].length();//HashMap1 存所有单词,记录出现的次数HashMap<String, Integer> allWords = new HashMap<String, Integer>();for (String w : words) {int value = allWords.getOrDefault(w, 0);allWords.put(w, value + 1);}//遍历所有子串for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {//HashMap2 存当前扫描的字符串含有的单词HashMap<String, Integer> hasWords = new HashMap<String, Integer>();int num = 0;//判断该子串是否符合while (num < wordNum) {String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);//判断该单词在 HashMap1 中if (allWords.containsKey(word)) {int value = hasWords.getOrDefault(word, 0);hasWords.put(word, value + 1);//判断当前单词的 value 和 HashMap1 中该单词的 valueif (hasWords.get(word) > allWords.get(word)) {break;}} else {break;}num++;}//判断是不是所有的单词都符合条件if (num == wordNum) {res.add(i);}}return res;}

搜索旋转排列数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
示例 3：
输入：nums = [1], target = 0 输出：-1

解题思路：给定一个升序排列的数组，并且无重复值。需要把后面随机一段有序数组放到数组前面，形成前后两段有序的子数组。因为数组有序，可以使用二分搜索算法来实现。

public int search(int[] nums, int target) {int len = nums.length;if (len == 0) {return - 1;}if (len == 1) {return nums[0] == target ? 0 : -1;}int l = 0;int r = len - 1;while(l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) {return mid;}if(nums[0] <= nums[mid]) {if (nums[0] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[len - 1]) {l = mid + 1;} else {r = mid - 1;}}}return -1;}

在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]

解题思路：二分搜搜算法

public int[] searchRange(int[] nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {return new int[]{leftIdx, rightIdx};}return new int[] {-1, -1};}public int binarySearch(int[] nums, int target, boolean lower) {int left = 0;int right = nums.length - 1;int ans = nums.length;while(left <= right ) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}