前言

在此篇开始前已完成代码随想录一刷，对于算法题算是初窥门径，但是一刷的周期很长，有很多东西已经记不清了，而且有很多对我于个人来说比较妙且有用的语法表达（基于Java）没有记录。故开此篇，总体上依照代码随想录的顺序开启二刷，并记录下遇到的难点和一些感想。

由衷感谢“卡哥”的开源精神！

代码随想录：https://programmercarl.com/

在每道题的标题后面会有一些符号：

  • 无任何符号：没有思路 or 没有通过全部样例 or 解题过程中参考了一些题解思路
  • ✔：Acess！
  • ❗：在编写代码的过程中遇到一些语法上的问题，需要留意

Leetcode

数组

【704】二分查找✔

题目链接：704. 二分查找 - 力扣（LeetCode）

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        // int mid = (right - left) / 2 + left;  //防止溢出的表达
        int mid = (left + right) / 2;  //也可以

        while(left <= right) {  //注意区间的表达
            mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] < target) {
                left = mid + 1;  //注意区间的表达
            }
            if(nums[mid] > target) {
                right = mid - 1;  //注意区间的表达
            }
        }

        return -1;
    }
}
  1. int mid = (right - left) / 2 + left;是一种防溢出的表达。
  2. 注意区间的表达。

【35】搜索插入位置✔

题目链接：35. 搜索插入位置 - 力扣（LeetCode）

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right) / 2;

        while(left <= right) {
            mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] < target) {
                left = mid + 1;
            }
            if(nums[mid] > target) {
                right = mid - 1;
            }
        }
        return left;  //注意返回值
    }
}
  1. 使用二分法。
  2. 注意返回值。

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

题目链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

题解：

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if(nums.length == 0) {
            return result;
        }

        // 找左边界
        int left1 = 0;
        int right1 = nums.length - 1;
        int mid1 = (left1 + right1) / 2;
        int left_board = -1;
        while(left1 <= right1) {
            mid1 = (left1 + right1) / 2;
            if(nums[mid1] == target) {
                left_board = mid1;  //记录结果
                right1 = mid1 - 1;  //关键，使搜索区间更靠近左侧
            }
            if(nums[mid1] > target) {
                right1 = mid1 - 1;
            }
            if(nums[mid1] < target) {
                left1 = mid1 + 1;
            }
        }

        // 找右边界
        int left2 = 0;
        int right2 = nums.length - 1;
        int mid2 = (left2 + right2) / 2;
        int right_board = -1;
        while(left2 <= right2) {
            mid2 = (left2 + right2) / 2;
            if(nums[mid2] == target) {
                right_board = mid2;  //记录结果
                left2 = mid2 + 1;  //关键，使搜索区间更靠近右侧
            }
            if(nums[mid2] > target) {
                right2 = mid2 - 1;
            }
            if(nums[mid2] < target) {
                left2 = mid2 + 1;
            }
        }

        result[0] = left_board;
        result[1] = right_board;

        return result;
    }
}

思路：直接利用二分法分别找到左右边界。

与基础二分法题目不同的是，如果nums[mid] == target，则需要根据查找的左、右目标边界，相对应地移动当前的右、左边界。目的是使当前的搜索区间更靠近目标方向。

【69】x的平方根

题目链接：69. x 的平方根 - 力扣（LeetCode）

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int mid = (right + left) / 2;

        while(left <= right) {
            mid = (right + left) / 2;
            if((long) mid * mid == x) {
                return mid;
            }
            if((long) mid * mid < x) {
                left = mid + 1;
            }
            if((long) mid * mid > x) {
                right = mid - 1;
            }
        }
        return left - 1;
    }
}

由于返回的值只要求整数部分，可以使用二分法查找。

注意：在计算判断语句中(long) mid * mid不可以写为(long) (mid * mid)，后者如果当(mid * mid)计算结果溢出，再转为long类型没有意义，依旧会报错。

【367】有效的完全平方数✔

题目链接：367. 有效的完全平方数 - 力扣（LeetCode）

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0;
        int right = num;
        int mid = (left + right) / 2;

        while(left <= right) {
            mid = (left + right) / 2;
            if((long) mid * mid == num) {
                return true;
            }
            if((long) mid * mid < num) {
                left = mid + 1;
            }
            if((long) mid * mid > num) {
                right = mid - 1;
            }
        }
        return false;
    }
}

正常使用二分法解决

【27】移除元素✔

题目链接：27. 移除元素 - 力扣（LeetCode）

题解：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;  //定义一个慢指针
        for(int fast = 0; fast < nums.length; fast++) {  //定义一个快指针，并利用for循环控制
            if(nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

双指针的一种思路：将快指针定义在for循环条件处，并利用for循环控制快指针移动，覆盖前面的目标值。

【26】删除有序数组中的重复项✔

题目链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

题解：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        for(int fast = 0; fast < nums.length; fast++) {
            if(nums[fast] > nums[slow]) {
                slow++;  // 先移动指针
                nums[slow] = nums[fast];  // 再进行替换
            }
        }
        return slow + 1;  // 注意返回值
    }
}

双指针解法，这里注意要先移动指针再替换。

【283】移动零✔

题目链接：283. 移动零 - 力扣（LeetCode）

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        // 先将slow指针移动到第一个0处
        while(slow < nums.length && nums[slow] != 0) {
            slow++;
        }
        // fast指针初始化和slow一致
        for(int fast = slow; fast < nums.length; fast++) {
            if(nums[fast] != 0) {
                nums[slow] = nums[fast];
                nums[fast] = 0;  // 相当于交换
                slow++;
            }
        }
    }
}

双指针思路：先将slow指针移动到第一个0处，注意不要让slow指针超出数组范围，再初始化fast指针，初始化和slow指针一致。

【844】比较含退格的字符串✔

题目链接：844. 比较含退格的字符串 - 力扣（LeetCode）

题解：

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
class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] s_list = s.toCharArray();
        char[] t_list = t.toCharArray();
        Stack<Character> s_stack = new Stack<>();
        Stack<Character> t_stack = new Stack<>();

        // 处理s
        for(int i = 0; i < s_list.length; i++) {
            // 如果不是'#'，则字母入栈
            if(s_list[i] != '#') {
                s_stack.push(s_list[i]);
            }
            // 如果是'#'，则先判断栈是否为空：如果栈为空，则跳过，否则弹出字母
            else if(s_list[i] == '#') {
                if(s_stack.isEmpty()) {
                    continue;
                } else {
                    s_stack.pop();
                }
            }
        }
        // 处理t
        for(int i = 0; i < t_list.length; i++) {
            // 如果不是'#'，则字母入栈
            if(t_list[i] != '#') {
                t_stack.push(t_list[i]);
            }
            // 如果是'#'，则先判断栈是否为空：如果栈为空，则跳过，否则弹出字母
            else if(t_list[i] == '#') {
                if(t_stack.isEmpty()) {
                    continue;
                } else {
                    t_stack.pop();
                }
            }
        }

        // 如果两个栈长度不一致，直接返回false
        if(s_stack.size() != t_stack.size()) {
            return false;
        }
        // 逐个弹出元素判断
        while(!s_stack.isEmpty()) {
            if(s_stack.pop() != t_stack.pop()) {
                return false;
            }
        }

        return true;
    }
}

很容易联想到栈，利用栈解决。

【977】有序数组的平方✔

题目链接：977. 有序数组的平方 - 力扣（LeetCode）

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        
        //左右指针从数组两边往中间靠，result数组从后往前添加
        for(int i = result.length - 1; i >= 0; i--) {
            if(Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[i] = nums[left] * nums[left];
                left++;
            } else {
                result[i] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}

双指针解法：左右指针从数组两边往中间靠，result数组从后往前添加，依次添加绝对值最大的数字的平方。

【209】长度最小的子数组✔

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;  // 定义左边界
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {  // 定义右边界
            sum += nums[right];  //for循环每一轮都向右边扩展
            // 一旦sum满足条件，就利用left左边界缩小范围
            while (sum >= target) {
                result = Math.min(result, right - left + 1);  
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

利用双指针构成滑动区间解决。关键思路：for循环条件内定义右边界，每轮循环扩展右边界，一旦sum满足条件，就利用while循环缩小左边界。

【904】水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

题解：

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
class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int result = 0;

        // 创建right，利用for循环不断遍历水果
        for(int right = 0; right < fruits.length; right++) {
            // 如果篮子有当前水果，直接把当前水果放入到对应的篮子里
            if(map.containsKey(fruits[right])) {
                map.put(fruits[right], map.get(fruits[right]) + 1);
                result = Math.max(result, right - left + 1);  // 计算最大值
            } 
            // 如果篮子没有当前水果
            else {
                // 如果篮子数量小于2，则直接创建一个新篮子，把当前水果放到该篮子中
                if(map.size() < 2) {
                    map.put(fruits[right], 1);
                    result = Math.max(result, right - left + 1);  // 计算最大值
                } 
                // 如果篮子数量大于2
                else {
                    map.put(fruits[right], 1);  // 先创建一个新篮子，然后把当前水果放到该篮子中
                    // 利用while循环删除包含fruits[left]的篮子（关键）
                    // 必须要逐步移动left，因为这个过程可能包含另外一种水果，也需要把该水果的数量减一
                    while(map.size() > 2) {
                        map.put(fruits[left], map.get(fruits[left]) - 1);
                        if(map.get(fruits[left]) == 0) {
                            map.remove(fruits[left]);
                        }
                        left++;
                    }
                }
            }
        }
        return result;
    }
}

利用滑动窗口的思想解题，用map记录水果种类（篮子）。

做题踩坑点：一开始想到了解题思路，但是在删除包含fruits[left]的篮子过程中没有逐步移动left，而是直接清空map中的fruits[left]，再重定位left。这样可能导致区间[left, right-1]中包含另一种水果的数量没有及时减去，导致最终结果偏大。

【76】最小覆盖子串✔❗

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

题解：

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
class Solution {
    public String minWindow(String s, String t) {
        char[] s_list = s.toCharArray();
        char[] t_list = t.toCharArray();
        Map<Character, Integer> s_map = new HashMap<>();
        Map<Character, Integer> t_map = new HashMap<>();

        // 初始化t_map
        for(int i = 0; i < t_list.length; i++) {
            t_map.put(t_list[i], t_map.getOrDefault(t_list[i], 0) + 1);
        }

        int left = 0;  //定义左指针
        StringBuilder sb = new StringBuilder();
        String result = s + t;  // 初始化result，一定要大于字符串s的长度（初始值无所谓）

        // 在for循环中定义右指针
        for(int right = 0; right < s_list.length; right++) {
            // 每轮循环不停地移动右指针，sb跟随着添加字符
            s_map.put(s_list[right], s_map.getOrDefault(s_list[right], 0) + 1);
            sb.append(s_list[right]);
            // 一旦符合题目中的条件，就移动左指针，缩小区间
            while(judge(s_map, t_map)) {
                s_map.put(s_list[left], s_map.get(s_list[left]) - 1);
                left++;
                result = result.length() < sb.toString().length() ? result : sb.toString();  // 先收集结果
                sb.deleteCharAt(0);  // 再缩减sb
            }
        }

        return result = result.equals(s + t) ? "" : result;
    }

    // 定义judge函数用于判断是否满足题目条件：s_map中是否全部包含t_map的“键”，并且大于等于“值”
    public Boolean judge(Map<Character, Integer> s_map, Map<Character, Integer> t_map) {
        for(Map.Entry<Character, Integer> entry : t_map.entrySet()) {
            if(!s_map.containsKey(entry.getKey())) {
                return false;
            }
            else if(s_map.get(entry.getKey()) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}

利用滑动区间解决问题，复杂的地方在于对字符串操作。

一些语法需要注意❗

  • Map集合的创建方式：

    1
    Map<Character, Integer> s_map = new HashMap<>();

  • Map集合设定默认值的添加方法.getOrDefault(Key, Value)：

    1
    t_map.put(t_list[i], t_map.getOrDefault(t_list[i], 0) + 1);

  • StringBuilder的添加和删除方法：

    1
    2
    sb.append(s_list[right]);  //添加
    sb.deleteCharAt(0);  //删除指定位置的元素

  • Map集合的forEach遍历方式：

    1
    2
    3
    4
    for(Map.Entry<Character, Integer> entry : t_map.entrySet()) {
        entry.getKey();
        entry.getValue();
    }

【59】螺旋矩阵Ⅱ✔

题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

题解：

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
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int number = 1;  // 定义填入的数字
        int offset = 1;  // 定义偏移量
        int x = 0, y = 0;  // 定义坐标
        int round = n / 2;  // 循环的轮次

        // 每次while循环就是一轮
        while(round > 0) {
            // 左上→右上
            for(; y < n - offset; y++) {
                matrix[x][y] = number;
                number++;
            }
            // 右上→右下
            for(; x < n - offset; x++) {
                matrix[x][y] = number;
                number++;
            }
            // 右下→左下
            for(; y > offset - 1; y--) {
                matrix[x][y] = number;
                number++;
            }
            // 左下→左上
            for(; x > offset - 1; x--) {
                matrix[x][y] = number;
                number++;
            }
            x++;
            y++;
            offset++;
            round--;
        }
        // 如果n为奇数，则最中心的位置单独填入数字
        if(n % 2 == 1) {
            int index = n / 2;
            matrix[index][index] = n * n;
        }

        return matrix;
    }
}

解题思路就是模拟转圈填写数字，利用offset控制每一圈的起止位置。

【54】螺旋矩阵✔

题目链接：54. 螺旋矩阵 - 力扣（LeetCode）

题解：

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int x = 0, y = 0;
        int offset = 1;  // 定义偏移量
        int x_length = matrix.length;  // 定义x_length
        int y_length = matrix[0].length;  // 定义y_length
        int round = Math.min(x_length, y_length) / 2;  // 循环的轮次

        // 每次while循环就是一轮
        while(round > 0) {
            // 左上→右上
            for(; y < y_length - offset; y++) {
                result.add(matrix[x][y]);
            }
            // 右上→右下
            for(; x < x_length - offset; x++) {
                result.add(matrix[x][y]);
            }
            // 右下→左下
            for(; y > offset - 1; y--) {
                result.add(matrix[x][y]);
            }
            // 左下→左上
            for(; x > offset - 1; x--) {
                result.add(matrix[x][y]);
            }
            x++;
            y++;
            offset++;
            round--;
        }

        // 如果x_length和y_length中的最小值为偶数，那么上述循环一定可以全部遍历
        // 如果x_length和y_length中的最小值为奇数，那么就需要分类遍历剩余的数字
        if(Math.min(x_length, y_length) % 2 == 1) {
            // 如果x_length较小，那么就需要 左→右 遍历中心剩余的行
            if(x_length < y_length) {
                for(; y < y_length - offset + 1; y++) {  // 需要注意y的边界条件
                    result.add(matrix[x][y]);
                }
            } 
            // 如果y_length较小，那么就需要 上→下 遍历中心剩余的列
            else {
                for(; x < x_length - offset + 1; x++) {  // 需要注意x的边界条件
                    result.add(matrix[x][y]);
                }
            }
        }

        return result;
    }
}

解题思路：模拟转圈遍历数字。关键在于对中心剩余数字的判定和遍历。

链表

哈希表

字符串

栈与队列

二叉树

回溯算法

贪心算法

动态规划

单调栈

图论

后记

To be continued…