Chenaa's Notes

尘事如潮人如水

0%

代码随想录刷题笔记

发表于 更新于 分类于

算法性能分析

数组

二分查找

二分查找一般的前置条件为 有序

循环不变量原则，只有在循环中坚持对区间的定义，才能清楚的把握循环中的各种细节。

1
做好区间的定义[0，2],还是[0,2),开闭区间的定义，影响边界条件的判断，要保证开闭区间定义上的一致性，才能做到循环中的条件判断不会乱。
  • 704.二分查找
  • 35.搜索插入位置(opens new window)
  • 34.在排序数组中查找元素的第一个和最后一个位置(opens new window)
  • 69.x 的平方根
  • 367.有效的完全平方数

双指针

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。

  • 27.移除元素
  • 26.删除排序数组中的重复项
  • 283.移动零
  • 844.比较含退格的字符串
  • 977.有序数组的平方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
## 27 移除元素
class Solution {
    public int removeElement(int[] nums, int val) {
        int slowIdx = 0;
        for (int fastIdx = 0; fastIdx < nums.length; fastIdx++) {
            if (val == nums[fastIdx]) {
                // slowIdx不动

            } else {
                // 交换位置
                nums[slowIdx] = nums[fastIdx];
                // slowIdx 向前移动
                slowIdx++;
            }
        }
        return slowIdx;
    }
}

977 有序数组的平方
非原地移除，可以创建另外的数组保存数据
我们可以使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。

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 n = nums.length;  
        int[] ans = new int[n];  
        for (int i = 0, j = n - 1, pos = n - 1; i <= j; ) {  
            if (nums[i] * nums[i] > nums[j] * nums[j]) {  
                ans[pos] = nums[i] * nums[i];  
                ++i;  
            } else {  
                ans[pos] = nums[j] * nums[j];  
                --j;  
            }  
            --pos;  
        }  
        return ans;  
    }  
}

滑动窗口

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

  • 209.长度最小的子数组
  • 904.水果成篮
  • 76.最小覆盖子串

模拟行为

  1. 复杂边界条件下，坚持循环不变量原则
  2. 通过定义模拟数组，对每一条边的遍历变量进行模拟
1
2
## 59.螺旋矩阵II 定义directions 模拟边的行为
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
  • 59.螺旋矩阵II
  • 54.螺旋矩阵
  • 剑指Offer 29.顺时针打印矩阵

参考

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