• 力扣刷题之数组专栏(共16道题)



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

    自己需要注意的题目刷题时间
    Code03、Code04、Code07、Code08、Code092022-11-22
    Code02、Code03、Code052022-11-23

    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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    /**
     * @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);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    /**
     * @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++;
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    /**
     * @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);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    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);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    /**
     * @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);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    /**
     * @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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
  • 相关阅读:
    手记系列之六 ----- 分享个人使用kafka经验
    FPGA模块——IIC协议(读写PCF8591)
    中视频伙伴计划开通收益功能的方法和使用介绍
    InfiniBand vs 光纤通道,存储协议的选择
    vite进行打包时如何把某个静态文件原封不动地拷贝到打包后的文件中
    支付通道的安全性探讨
    Parallels 将扩展桌面平台产品,以进一步改善在 Mac 上运行 Windows 的用户体验和工作效率
    “在 ArchiMate EA 建模中的组合关系:构建块和依赖关系
    emlog文章页实现自动加关键词内链方法(非插件)
    LeetCode-剑指39-数组中出现次数冲过一半的数字
  • 原文地址:https://blog.csdn.net/weixin_59654772/article/details/127988900