力扣刷题之数组专栏（共16道题）

忘是亡心i 2023-09-25 13:17 61阅读 0赞

#### 文章目录 ####

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

--------------------

简简单单向前冲(\*^o^)人(^o^\*)

--------------------

<table> 
 <thead> 
  <tr> 
   <th>自己需要注意的题目</th> 
   <th>刷题时间</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Code03、Code04、Code07、Code08、Code09</td> 
   <td>2022-11-22</td> 
  </tr> 
  <tr> 
   <td>Code02、Code03、Code05</td> 
   <td>2022-11-23</td> 
  </tr> 
 </tbody> 
</table>

--------------------

2022-11-22，写了10道题目

--------------------

## 一、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，写了6道题目

--------------------

## 二、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<Integer, Integer> 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<Character, Integer> sMap = new HashMap<>();
            Map<Character, Integer> 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);
                else
                    tMap.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);
                    else
                        sMap.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<Integer> spiralOrder(int[][] matrix) {
        
            //设置上下左右边界
            int upper = 0;
            int down = matrix.length - 1;
            int left = 0;
            int right = matrix[0].length - 1;
            List<Integer> 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;
        }
    }