文章目录

• 一、2022/11/22
• 二、2022/11/23

一、2022/11/22

/*** @Auther: sht2002* @Date: 2022-11-22 18:31* @Description: 704、二分查找*/
public class Code01 {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int middle = left + ((right - left) >> 1);if (nums[middle] == target) {return middle;} else if (nums[middle] > target) {right = middle - 1;} else {left = middle + 1;}}return -1;}
}

/*** @Auther: sht2002* @Date: 2022-11-22 18:38* @Description: 35. 搜索插入位置* return left也是可以的*/
public class Code02 {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int middle = left + ((right - left) >> 1);if (nums[middle] == target) {return middle;} else if (nums[middle] > target) {right = middle - 1;} else {left = middle + 1;}}return (right + 1);}
}

/*** @Auther: sht2002* @Date: 2022-11-22 18:46* @Description: 34. 在排序数组中查找元素的第一个和最后一个位置（中等）* 千万注意要在while中检查数组下标是否越界！*/
public class Code03 {public int[] searchRange(int[] nums, int target) {int index = binarySearch(nums, target);if (index == -1) return new int[]{-1, -1};int left = index;int right = index;//这两个while是核心代码while (left - 1 >= 0 && nums[left - 1] == target) {left--;}while (right + 1 < nums.length && nums[right + 1] == target) {right++;}return new int[]{left, right};}private int binarySearch(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int middle = left + ((right - left) >> 1);if (nums[middle] == target) {return middle;} else if (nums[middle] > target) {right = middle - 1;} else {left = middle + 1;}}return -1;}
}

/*** @Auther: sht2002* @Date: 2022-11-22 19:30* @Description: 69. x的平方根* 这里的 x 可以理解为经典二分查找里面的数组长度-1，要注意int 强转为long的使用细节*/
public class Code04 {public int mySqrt(int x) {int left = 0;int right = x;int res = 0;while (left <= right) {int middle = left + ((right - left) >> 1);if ((long) middle * middle <= x) {
//            if ((long) (middle * middle) <= x) { 这样的代码，已经发生了数值溢出res = middle;left = middle + 1;} else {right = middle - 1;}}return res;}
}

/*** @Auther: sht2002* @Date: 2022-11-22 19:49* @Description: 367.有效的完全平方数* 注意类型转换！*/
public class Code05 {public boolean isPerfectSquare(int num) {int left = 0;int right = num;while (left <= right) {int middle = left + ((right - left) >> 1);if ((long) middle * middle == num) {return true;} else if ((long) middle * middle > num) {right = middle - 1;} else {left = middle + 1;}}return false;}
}

/*** @Auther: sht2002* @Date: 2022-11-22 20:01* @Description: 27. 移除元素* 快慢指针法*/
public class Code06 {public int removeElement(int[] nums, int val) {int slow = 0;int fast = 0;while (fast < nums.length) {if (nums[fast] != val) {nums[slow] = nums[fast];slow++;}fast++;}return slow;}
}

/*** @Auther: sht2002* @Date: 2022-11-22 20:09* @Description: 283. 移动零* 只要fast位置的值不是0，就把该位置的值给slow位置，最后把数组后面的值全部填充为0*/
public class Code07 {public void moveZeroes(int[] nums) {int slow = 0;int fast = 0;while (fast < nums.length) {if (nums[fast] != 0) {nums[slow] = nums[fast];slow++;}fast++;}while (slow < nums.length) {nums[slow] = 0;slow++;}}
}

/*** @Auther: sht2002* @Date: 2022-11-22 20:10* @Description: 26. 删除有序数组中的重复项* 让快指针fast从下标 1出发，当遇到慢指针的值与快指针的值不相等时，先让slow++，然后再赋值* 注意return返回的是 slow + 1*/
public class Code08 {public int removeDuplicates(int[] nums) {int slow = 0;int fast = 1;while (fast < nums.length) {if (nums[slow] != nums[fast]) {slow++;nums[slow] = nums[fast];}fast++;}return (slow + 1);}
}

/*** @Auther: sht2002* @Date: 2022-11-22 21:27* @Description: 844. 比较含退格的字符串* 得好好琢磨各个判断条件的含义*/
public class Code09 {public boolean backspaceCompare(String s, String t) {int sNum = 0;int tNum = 0;int i = s.length() - 1;int j = t.length() - 1;while (true) {while (i >= 0) {if (s.charAt(i) == '#') {sNum++;} else {if (sNum > 0) sNum--;// break来比较 if (s.charAt(i) != t.charAt(j))else break;}i--;}while (j >= 0) {if (t.charAt(j) == '#') {tNum++;} else {if (tNum > 0) tNum--;else break;}j--;}if (i < 0 || j < 0) break;if (s.charAt(i) != t.charAt(j)) return false;i--;j--;}if (i == -1 && j == -1) return true;return false;}
}

/*** @Auther: sht2002* @Date: 2022-11-22 22:54* @Description: 977.有序数组的平方* 平方后的数最大值一定在数组的两端，需要注意temp要放最大值* 不能放最小值，因为你不知道最小值在哪里*/
public class Code10 {public int[] sortedSquares(int[] nums) {int len = nums.length;int[] temp = new int[len];int left = 0;int right = len - 1;int index = len - 1;while (left <= right) {if (nums[left] * nums[left] < nums[right] * nums[right]) {temp[index] = nums[right] * nums[right];right--;} else {temp[index] = nums[left] * nums[left];left++;}index--;}return temp;}
}

二、2022/11/23

/*** @Auther: sht2002* @Date: 2022-11-23 18:09* @Description: 209. 长度最小的子数组（中等）* 滑动窗口:当sum >= target时，就开始移动slow，并在过程中记录len的最小值*/
public class Code01 {public int minSubArrayLen(int target, int[] nums) {int slow = 0;int fast = 0;int sum = 0;int len = Integer.MAX_VALUE;while (fast < nums.length) {sum += nums[fast];while (sum >= target) {len = Math.min(len, fast - slow + 1);sum -= nums[slow];slow++;}fast++;}return (len == Integer.MAX_VALUE ? 0 : len);}
}

/*** @Auther: sht2002* @Date: 2022-11-23 18:23* @Description: 904. 水果成篮（中等）* 滑动窗口*/
public class Code02 {public int totalFruit(int[] fruits) {int slow = 0;int fast = 0;int ans = 0;Map map = new HashMap<>();while (fast < fruits.length) {if (map.containsKey(fruits[fast])) {map.put(fruits[fast], map.get(fruits[fast]) + 1);} else {map.put(fruits[fast], 1);}while (map.size() > 2) {map.put(fruits[slow], map.get(fruits[slow]) - 1);//需要注意if的作用：让map.size()减一if (map.get(fruits[slow]) == 0) {map.remove(fruits[slow]);}slow++;}ans = Math.max(ans, fast - slow + 1);fast++;}return ans;}
}

/*** @Auther: sht2002* @Date: 2022-11-23 18:56* @Description: 76. 最小覆盖子串（困难）*/
public class Code03 {public String minWindow(String s, String t) {Map sMap = new HashMap<>();Map tMap = new HashMap<>();int left = 0;int right = 0;int count = 0;int start = 0;int ans = Integer.MAX_VALUE;for (char c : t.toCharArray()) {if (tMap.containsKey(c))tMap.put(c, tMap.get(c) + 1);elsetMap.put(c, 1);}while (right < s.length()) {char c = s.charAt(right);right++;if (tMap.containsKey(c)) {if (sMap.containsKey(c))sMap.put(c, sMap.get(c) + 1);elsesMap.put(c, 1);//体会这个if的作用if (tMap.get(c).equals(sMap.get(c)))count++;}//当满足count == tMap.size()时，这个while用来找最优解while (count == tMap.size()) {if (right - left < ans) {ans = right - left;start = left;}//下面代码用来更新窗口char d = s.charAt(left);//不要忘记窗口的缩小left++;if (tMap.containsKey(d)) {//注意两者的先后顺序if (tMap.get(d).equals(sMap.get(d)))count--;sMap.put(d, sMap.get(d) - 1);}}}return ans == Integer.MAX_VALUE ? "" : s.substring(start, start + ans);}
}

/*** @Auther: sht2002* @Date: 2022-11-23 20:09* @Description: 59. 螺旋矩阵 II（中等）* 这次终于一次性过了，遵循左闭右开的原则，模拟整个过程*/
public class Code04 {public int[][] generateMatrix(int n) {int[][] ans = new int[n][n];int loop = n / 2;int middle = n / 2;int offset = 1;int count = 1;int x = 0, y = 0;while (loop-- > 0) {int i = x;int j = y;for (; j < n - offset; j++)ans[i][j] =count++;for (; i < n - offset; i++)ans[i][j] = count++;for (; j > y; j--)ans[i][j] = count++;for (; i > x; i--)ans[i][j] = count++;x++;y++;offset++;}if (n % 2 == 1) {ans[middle][middle] = count;}return ans;}
}

/*** @Auther: sht2002* @Date: 2022-11-23 20:21* @Description: 54. 螺旋矩阵（中等）* 有点难度，好好琢磨*/
public class Code05 {public List spiralOrder(int[][] matrix) {//设置上下左右边界int upper = 0;int down = matrix.length - 1;int left = 0;int right = matrix[0].length - 1;List res = new ArrayList<>();while (true) {for (int i = left; i <= right; i++)res.add(matrix[upper][i]);//重新定义上下边界，若上边界大于下边界，则遍历结束(可以假设matrix只有一行的情况)if (++upper > down) break;for (int i = upper; i <= down; i++)res.add(matrix[i][right]);if (--right < left) break;for (int i = right; i >= left; i--)res.add(matrix[down][i]);if (--down < upper) break;for (int i = down; i >= upper; i--)res.add(matrix[i][left]);if (++left > right) break;}return res;}
}

/*** @Auther: sht2002* @Date: 2022-11-23 22:38* @Description: 剑指 Offer 29. 顺时针打印矩阵* 学会了Code5，就学会了Code6*/
public class Code06 {public int[] spiralOrder(int[][] matrix) {if (matrix.length == 0) return new int[]{};int upper = 0;int down = matrix.length - 1;int left = 0;int right = matrix[0].length - 1;int[] ans = new int[(down + 1) * (right + 1)];int index = 0;while (true) {for (int i = left; i <= right; i++)ans[index++] = matrix[upper][i];if (++upper > down) break;for (int i = upper; i <= down; i++)ans[index++] = matrix[i][right];if (--right < left) break;for (int i = right; i >= left; i--)ans[index++] = matrix[down][i];if (--down < upper) break;for (int i = down; i >= upper; i--)ans[index++] = matrix[i][left];if (++left > right) break;}return ans;}
}