代码随想录学习记录

数组

双指针思想

二分查找

这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

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
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 左闭右闭
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 小于，目标值在右边，left往右边跑
            if (nums[mid] < target) {
                left = mid + 1;
            }
            // 大于，目标值在左边，right往左边跑
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            // 相等
            else {
                return mid;
            }
        }
        return -1;
    }
}

35. 搜索插入位置

35. 搜索插入位置 - 力扣（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 searchInsert(int[] nums, int target) {
         int left = 0, right = nums.length - 1;
        // 左闭右闭
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 小于，需要插入的位置在右边，left往右边跑
            if (nums[mid] < target) {
                left = mid + 1;
            }
            // 大于，需要插入的位置在左边，right往左边跑
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            // 相等直接在相等的位置插入
            else {
                return mid;
            }
        }
        //最后没找到相等的，left和right错开的位置结束了循环，是最接近target的位置，根据推算，返回left位置即可
        return left;
    }
}

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

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 左闭右闭
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 小于，需要插入的位置在右边，left往右边跑
            if (nums[mid] < target) {
                left = mid + 1;
            }
            // 大于，需要插入的位置在左边，right往左边跑
            else if (nums[mid] > target) {
                right = mid - 1;
            }

            // 相等就看左右哪个不相等就移动一个位置就好，不然就结束循环
            else {
                if (nums[left] != nums[mid]) {
                    left++;
                } else if (nums[right] != nums[mid]) {
                    right--;
                } else {
                    return new int[] { left, right };
                }
            }
        }
        // 最后没找到相等的，或者nums为空
        return new int[] { -1, -1 };
    }
}

**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, right = x, result = -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            long square = (long) mid * mid;  // 使用 long 防止溢出
            // 如果 mid * mid 小于 x，向右侧逼近
            if (square < x) {
                left = mid + 1;
            } else if (square > x) {
                // 如果 mid * mid 大于 x，向左侧逼近
                right = mid - 1;
            } else {
                // 如果正好等于 x，直接返回 mid
                return mid;
            }
        }
        // 最终返回的是最大的满足 mid*mid <= x 的 mid
        return right; // right 会是最接近但不大于 x 平方根的值
    }
}

367. 有效的完全平方数

367. 有效的完全平方数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0, right = num;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if ((long) mid * mid < num) {
                // 左指针向右移动尝试
                left = mid + 1;
            } else if ((long) mid * mid > num) {
                // 右指针向左移动尝试
                right = mid - 1;
            } else {
                // 相等直接返回true
                return true;
            }
        }
        // 走到这里说明只有逼近值，right，但是没有能够完全想等的
        return false;
    }
}

双指针

27. 移除元素

27. 移除元素 - 力扣（LeetCode）

双指针解决，快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int removeElement(int[] nums, int val) {
        // 相等的个数
        int count = 0;
        // 记录当前插入的下标
        int index = 0;
        // 记录当前遍历到的位置
        int i = 0;
        while (i <= nums.length - 1) {
            // 相等就i跳过，但是index不跳过，下次遇到不相等的插入到index就好
            if (nums[i] == val) {
                i++;
            }
            // 不相等就插入当前位置到index的位置，两个都加1
            else {
                nums[index++] = nums[i++];
                count++;
            }
        }
        return count;
    }
}

26. 删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（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 removeDuplicates(int[] nums) {
        //遇到相同的就直接跳过就好
        if(nums.length==0){
            return 0;
        }
        //不同元素的个数
        int count = 1;
        //上次的元素
        int lastDifferent = nums[0];
        //能够插入的位置
        int slow = 1;
        //快慢指针
        for(int fast = 1;fast<nums.length;fast++){
            if(nums[fast]!=lastDifferent){
                lastDifferent = nums[fast];
                  nums[slow++] = nums[fast];
                  count++;
            }
        }
        return count;
    }
}

283. 移动零

283. 移动零 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public void moveZeroes(int[] nums) {
        // 能够插入的位置
        int slow = 0;
        // 快慢指针
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
        }
        // 余下填充0
        while (slow <= nums.length - 1) {
            nums[slow++] = 0;
        }
    }
}

844. 比较含退格的字符串

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
54
55
class Solution {
    public boolean backspaceCompare(String s, String t) {
        // #会导致回退，可以倒序双指针比较
        int i = s.length() - 1, j = t.length() - 1;
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0) {
            // 先处理s
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    // 删除一个元素，但是可能存在多个，这里先保存需要删除多少个
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    // 需要删除
                    skipS--;
                    i--;
                } else {
                    // 到这里说明这个元素是最后存在的
                    break;
                }
            }
            // 同理处理t
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    // 删除一个元素，但是可能存在多个，这里先保存需要删除多少个
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    // 需要删除
                    skipT--;
                    j--;
                } else {
                    // 到这里说明这个元素是最后存在的
                    break;
                }
            }
            // 看是不是两个都在正常位置
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            }
            // 访问到超出范围的情况，但是有一个还是能取到元素就说明不相等
            else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            // 比较到两个相等的一个位置了，整体前移动继续比较
            i--;
            j--;
        }
        return true;
    }
}

977. 有序数组的平方

977. 有序数组的平方 - 力扣（LeetCode）

还可以就是先全部平方，然后一个sort搞定，就是原地操作了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] result = new int[nums.length];
        int i = result.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] < nums[right] * nums[right]) {
                result[i--] = nums[right] * nums[right];
                right--;
            } else {
                result[i--] = nums[left] * nums[left];
                left++;
            }
        }
        return result;
    }
}

滑动窗口

209. 长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢。

首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？

此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 暴力解法就是On^2会超时，这里用双指针的滑动窗口，时间复杂度On 严格是O2n
        //保存结果
        int result = Integer.MAX_VALUE;
        //保存当前计算区间内的和
        int sum = 0;
        //左指针
        int left  = 0;
        for(int right = 0;right<nums.length;right++){
            sum+=nums[right];
            //如果出现区间内的和大于等于就可以移动左指针缩小区间了
            while(sum>=target){
                //先保存结果再缩小区间
                result = Math.min(result,right-left+1);
                sum-=nums[left++];
            }
        }

        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

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
class Solution {
    public int totalFruit(int[] fruits) {
        int result = 0;
        int left = 0;
        // 定义一个哈希表来保证只存在两个不同的值，也就是不同的篮子
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int right = 0; right < fruits.length; right++) {
            // 先往哈希表里面放
            map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
            // 看哈希表是不是超过2个篮子,超过两个篮子，就不断移动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;
            }
            result = Math.max(result, right - left + 1);
        }
        return result;
    }
}

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
class Solution {

    HashMap<Character, Integer> map1 = new HashMap<>();
    HashMap<Character, Integer> map2 = new HashMap<>();

    public String minWindow(String s, String t) {
        // 把目标值的不同字符的数量保存到map
        for (int i = 0; i < t.length(); i++) {
            map1.put(t.charAt(i), map1.getOrDefault(t.charAt(i), 0) + 1);
        }

        int left = 0;
        // len保存最小满足条件的长度,l为答案的左边，r为答案右边
        int len = Integer.MAX_VALUE, l = -1, r = -1;
        for (int right = 0; right < s.length(); right++) {
            // t存在这个字符
            if (map1.containsKey(s.charAt(right))) {
                map2.put(s.charAt(right), map2.getOrDefault(s.charAt(right), 0) + 1);
            }
            // 满足情况下移动左指针
            while (check() && left <= right) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    l = left;
                    r = right;
                }
                if (map1.containsKey(s.charAt(left))) {
                    map2.put(s.charAt(left), map2.getOrDefault(s.charAt(left), 0) - 1);
                }
                left++;
            }
        }
        return l == -1 ? "" : s.substring(l, r + 1);
    }

    // 检查map2是否都包含map1的值和数量
    public boolean check() {
        for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
            if (map2.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}

模拟 螺旋

59. 螺旋矩阵 II

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
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];

        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int i = 0, j = 0, temp = 1;
        while (top <= bottom && left <= right) {
            // 向右
            for (int k = left; k <= right; k++) {
                result[top][k] = temp++;
            }
            top++;
            // 向下
            for (int k = top; k <= bottom; k++) {
                result[k][right] = temp++;
            }
            right--;
            // 向左
            for (int k = right; k >= left; k--) {
                result[bottom][k] = temp++;
            }
            bottom--;
            // 向上
            for (int k = bottom; k >= top; k--) {
                result[k][left] = temp++;
            }
            left++;
        }

        return result;
    }
}

54. 螺旋矩阵

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 List<Integer> spiralOrder(int[][] matrix) {
        // 行数量
        int row = matrix.length;
        if (row == 0) {
            return new ArrayList<Integer>();
        }
        // 列数
        int column = matrix[0].length;
        // 保存结果
        List<Integer> result = new ArrayList<>();
        // 保存当前外围范围
        int top = 0, bottom = row - 1, left = 0, right = column - 1;
        // 这里的条件要改为 &&，保证同时检查行和列的边界
        while (top <= bottom && left <= right) {
            // 向右和向下一开始保证了，但向左和向上没有，并且是反向的需要在循环中进行判断
            // 向右
            for (int k = left; k <= right; k++) {
                result.add(matrix[top][k]);
            }
            top++;
            // 向下
            for (int k = top; k <= bottom; k++) {
                result.add(matrix[k][right]);
            }
            right--;
            // 向左
            if (top <= bottom) {
                for (int k = right; k >= left; k--) {
                    result.add(matrix[bottom][k]);
                }
                bottom--;
            }
            // 向上
            if (left <= right) {
                for (int k = bottom; k >= top; k--) {
                    result.add(matrix[k][left]);
                }
                left++;
            }
        }
        return result;
    }
}

LCR 146. 螺旋遍历二维数组

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
class Solution {
    public int[] spiralArray(int[][] array) {
        // 行数量
        int row = array.length;
        if (row == 0) {
            return new int[0];
        }
        // 列数
        int column = array[0].length;
        // 保存结果
        int[] result = new int[row * column];
        // 保存当前外围范围
        int top = 0, bottom = row - 1, left = 0, right = column - 1;
        // 保存结果当前填充到哪个下标
        int temp = 0;

        // 这里的条件要改为 &&，保证同时检查行和列的边界
        while (top <= bottom && left <= right) {
            // 向右和向下一开始保证了，但向左和向上没有，并且是反向的需要在循环中进行判断
            // 向右
            for (int k = left; k <= right; k++) {
                result[temp++] = array[top][k];
            }
            top++;
            // 向下
            for (int k = top; k <= bottom; k++) {
                result[temp++] = array[k][right];
            }
            right--;
            // 向左
            if (top <= bottom) {
                for (int k = right; k >= left; k--) {
                    result[temp++] = array[bottom][k];
                }
                bottom--;
            }
            // 向上
            if (left <= right) {
                for (int k = bottom; k >= top; k--) {
                    result[temp++] = array[k][left];
                }
                left++;
            }
        }
        return result;
    }
}

前缀和

区间和

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。

1
2
3
4
5
6
7
8
5
1
2
3
4
5
0 1
1 3
1
2
3
9

如果，我们想统计，在vec数组上 下标 2 到下标 5 之间的累加和，那是不是就用 p[5] - p[1] 就可以了。

为什么呢？

p[1] = vec[0] + vec[1];
p[5] = vec[0] + vec[1] + vec[2] + vec[3] + vec[4] + vec[5];
p[5] - p[1] = vec[2] + vec[3] + vec[4] + vec[5];

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] vec = new int[n];
        int[] p = new int[n];

        int presum = 0;
        for (int i = 0; i < n; i++) {
            vec[i] = scanner.nextInt();
            presum += vec[i];
            p[i] = presum;
        }

        while (scanner.hasNextInt()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            int sum;
            if (a == 0) {
                sum = p[b];
            } else {
                sum = p[b] - p[a - 1];
            }
            System.out.println(sum);
        }

        scanner.close();
    }
}

开发商购买土地

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。

为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

【输入描述】

第一行输入两个正整数，代表 n 和 m。

接下来的 n 行，每行输出 m 个正整数。

输出描述

请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

【输入示例】

3 3 1 2 3 2 1 3 1 2 3

【输出示例】

0

【提示信息】

如果将区域按照如下方式划分：

1 2 | 3 2 1 | 3 1 2 | 3

两个子区域内土地总价值之间的最小差距可以达到 0。

【数据范围】：

  • 1 <= n, m <= 100；
  • n 和 m 不同时为 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
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int sum = 0;
        int[][] vec = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vec[i][j] = scanner.nextInt();
                sum += vec[i][j];
            }
        }

        // 统计横向
        int[] horizontal = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                horizontal[i] += vec[i][j];
            }
        }

        // 统计纵向
        int[] vertical = new int[m];
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                vertical[j] += vec[i][j];
            }
        }

        int result = Integer.MAX_VALUE;
        int horizontalCut = 0;
        for (int i = 0; i < n; i++) {
            horizontalCut += horizontal[i];
            result = Math.min(result, Math.abs(sum - 2 * horizontalCut));
        }

        int verticalCut = 0;
        for (int j = 0; j < m; j++) {
            verticalCut += vertical[j];
            result = Math.min(result, Math.abs(sum - 2 * verticalCut));
        }

        System.out.println(result);
        scanner.close();
    }
}