刷题笔记1-数组/链表

前缀和

使用于 数组固定不变  而且需要频繁求和的情况

相关题目：

1、一维数组的区域和检索 303

2、二维数组的区域和检索 304

3、和为k的子数组个数 560

在求解数组和的时候，最普通的方法就是for循环遍历，复杂度为\(O(N)\)。

但是当需要多次调用求解数组和的方法时，就需要降低其复杂度

使用前缀和可以将复杂度降为\(O(1)\)

使用条件：调用数组求和方法前数组已经初始化 + 会调用大量的数组求和方法

1
2
3
4
5
6
7
8
9
10
// 在初始化的时候构建前缀和数组
int *preSum = new int[len + 1]{0};
for(int i = 0; i < len; i++){
    preSum[i+1] = preSum[i] + nums[i];
}

// 返回数组某个范围的和只需要用相应前缀和数组进行相减即可
int sunRange(int left, int right){
    return preSum[right+1] - preSum[left+1];
}

在二维数组（矩阵）中应用时，"前缀和" 就是 某点\((row, col)\) 到 \((0,0)\)或者其他定点所围成的区域的和。

1
2
3
4
5
6
7
8
9
10
/*
* 求解 row1, col1, row2, col2 所围成的区域的和
* Sum(row2, col2) - Sum(row2, col1) - Sum(row1, col2) + Su(row1, col1)
*/
int sumRegion(int row1, int col1, int row2, int col2){
    preMatrix[row2][col2] -
               (col1 > 0 ? preMatrix[row2][col1 - 1] : 0) -
               (row1 > 0 ? preMatrix[row1 - 1][col2] : 0) +
               (row1 > 0 && col1 > 0 ? preMatrix[row1 - 1][col1 - 1] : 0);
}

和为k的子数组个数

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
// 最普通的思路 O(N^3)
for(int i = 0; i < len; i++) {
    for(int j = i; j < len; j++){
        int sum = 0;
        for(int k = i; k <= j; k++){
            sum += nums[k];
        }
        if(sum == k){
            cnt++;
        }
    }
}

// 利用前缀和数组 => O(N^2)
for(int i = 0; i < len; i++){
    for(int j = 0; j < i; j++){
        if(preSum[i] - preSum[j] == k){
            cnt ++;
        }
    }
}

// 【O(N)】
// preSum[j] = preSum[i] - k ·········· (1)
unordered_map<int, int> preSum;
preSum[0] = 1; // 考虑有前缀和=k的qing
int len = nums.size();
int sum_i = 0, sum_j = 0;
for(int i = 0; i < len; i++){
    sum_i += nums[i];
    sum_j = sum_i - k;
    if(preSum.find(sum_j) != preSum.end()){ // 存在前缀和使得 (1) 成立
        cnt += preSum[sum_j];
    }
    if(preSum.find(sum_i) != preSum.end()){
        preSum[sum_i] ++;
    } else{
        preSum[sum_i] = 1;
    }
}

差分数组

差分数组适用于 需要频繁对数组的某个区间做增减的情况

区间加法 370

航班预定统计 1109

拼车 1094

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
class Difference
{
private:
    vector<int> diff;

public:
    // 初始化差分数组
    Difference(vector<int> &nums)
    {
        diff.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++)
        {
            diff.push_back(nums[i] - nums[i - 1]);
        }
    }

    // [startIndex, endIndex]区间 加和
    void increment(int startIndex, int endIndex, int inc)
    {
        diff[startIndex] += inc;
        if (endIndex < diff.size() - 1){
            diff[endIndex + 1] -= inc;
        }
    }

    // 由差分数组得到原数组并返回
    vector<int> getResult()
    {
        vector<int> nums(diff.size());
        nums[0] = diff[0];
        for (int i = 1; i < diff.size(); i++)
        {
            nums[i] += nums[i - 1] + diff[i];
        }
        return nums;
    }
};

在【航班预定统计】中，对航班人数形成的数组做差分

在【拼车】中，对每个位置车上的人数形成的数组做差分

滑动窗口

一般解决 在字符串中寻找子串 的问题

最小覆盖子串 76

字符串的排列 567

找到字符串中所有字母异位词 438

无重复字符最长子串 3

思路：

1、先用一个map记录满足要求的情况（比如子串中字符类型和数目）

2、用另一个map记录窗口内的情况（window）[ left, right )

3、【不断移动右边界，并对window内容做更新】 => 【在满足某种情况时，需要缩减窗口（即移动左边界），并做更新】 （循环这个过程，直到右边界到达字符串边界）

4、我们需要的结果在哪里更新？（移动右边界过程中，还是移动左边界过程中）

理解窗口缩小背后的含义

个人的理解：

滑动窗口的核心当然在于【窗口】的含义和【滑动】的含义

一般来说，窗口是帮助我们寻找答案的结构；滑动是我们寻找的答案的过程以及技巧。

所以，窗口的定义都是比较简单的。

真正灵活的是窗口的滑动。滑动避免了冗余的循环，大大降低了问题的复杂度

我们如果使用最一般的方法处理此类问题，首先要确定就是 字符串的开始位置 和 结束位置，之前我们使用循环是O(N^2)的复杂度；而使用窗口的滑动，右边界滑动是确定开始位置不断改变结束位置，而左边界滑动是确定结束位置不断改变开始位置，最多只需要对字符串做两次遍历，是O(N)复杂度，当然其中还涉及一些其他的技巧，帮助筛选掉一些情况。

滑动分为右边界滑动（窗口扩大）和左边界滑动（窗口缩小）

分别对应着 什么时候窗口扩大；窗口扩大之后干什么；什么时候窗口缩小；窗口缩小之后干什么

一般我们都将窗口初始化为 [ 0, 0 )

窗口扩大是对应于【寻找解】的过程；窗口缩小是对应于【优化解】的过程

寻找解的过程相对简单，根据问题的类型很容易可以写出相应的代码

【最难的是】 什么时候进行解的优化，以及怎么做？先根据题目来看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 滑动窗口的框架
void slideWindow(string s1, string s2){
    unordered_map<char, int> need;
    for(char c : s1) need[c]++;
    
    unordered_map<char, int> window;
    int left = 0, right = 0;
    int valid = 0;
    
    while(right < s2.size()){
        char c = s2[right];
        right++;
        
        // ... 窗口扩大时做的更新
        
        while( condition ){ // 什么时候停止窗口扩大，开始缩减窗口
            char d = s2[left];
            left++;
            // ... 窗口缩减时做的操作
        }
    }
}

针对上面的四个例子，具体地阐述一下框架的使用，以及对于那几个问题的思考

  • 【最小覆盖子串】

在 s 中找到 包含 t 中所有字符的最小子串

1、移动右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
...
char c = s2[right];
right++;
// 窗口增大时的更新操作
/*
如果加入窗口的这个字符 是need中的字符 (也就是说是 t 中的字符)
就将该字符在窗口中的数量+1
如果该字符在窗口中的数量 和 在need中的数量一样 (也就是说窗口中该字符满足了t中的要求)
valid +1 表示有效的字符数增加 当有效字符数和t中的字符类型数一样的时候 说明此时窗口中满足了要求 包含了t中所有字符
*/
if(need.count(c)){
    window[c]++;
    if(window[c] == need[c]){
        valid++;
    }
}

2、【窗口中满足要求时】，缩减窗口

为什么要缩减窗口？为什么要在窗口满足要求的时候缩减窗口？缩减时干什么？

问题是求解【最小子串】

在右边界不断移动的过程中，可能会有一些不必要的字符被加入窗口中，就会导致窗口中的答案可能不是最小的。比如（"adbc" 中包含 "bcd"，但是 "a"是无关紧要的，可以从窗口中移除的，应该变为 "dbc"）就需要对窗口进行缩减才能使得答案更优（局部最优）。

因为要对解进行优化，首先需要在窗口中出现解，或包含解，才能继续优化，所以需要在窗口满足要求时进行缩减。

根据前面我们要缩减窗口的原因，在缩减窗口时，我们需要做的就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
    将字符从左边界移出，直到窗口中刚好不满足要求，此时窗口内的解为局部最优
*/
while( valid == need.size() ){
    char d = s2[left];
    left++;
    
    /*
    	如果移出的字符在need中，而且移出前该字符在窗口中的数量刚好满足要求
    	移出后，valid --
    	window[d] --
    */
    if(need.count(d)){
        if(window[d] == need[d]){
            valid--;
        }
        window[d]--;
    }
}

3、由于我们需要的最小子串，那么肯定需要对解进行判断和更新，在哪？

我们需要的全局最优解，更新的时候肯定是考虑局部最优解，所以自然就应该将答案的更新放在窗口缩小中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while( valid == need.size() ){
    // 对答案进行更新
    if(right - left < len){
        start = left; 
        len = right - left;
    }
    
    char d = s2[left];
    left++;
    
    if(need.count(d)){
        if(window[d] == need[d]){
            valid--;
        }
        window[d]--;
    }
}
  • 【字符串的排列】【找到字符串中所有字母异位词】

判断字符串 s1 中是否包含 s2 的排列

找到字符串 s1 中 s2 所有排列的起始位置

这两个问题的核心是一样的，都是查找字符串的排列

应用上面的框架，移动右边界寻找解的过程是一致的，区别和难点在于【缩减窗口的时机】和【缩减窗口的操作】

什么时候缩减窗口

缩减窗口的目的是 优化解。

所以，可以得出缩减窗口的两个时机就是 1、窗口中包含了解 2、明显知道窗口中的内容不能满足解，需要对窗口中的内容进行修正。

这两个时机可以任选一个，就看不同的问题中，哪个时机更加明显。

对于上一个问题：最小覆盖子串中，时机1是更加明显的，只要窗口中包含了和need中一样的字符和数量（valid == need.size()）；相比之下，时机2是不明显的，【修正解】在这个问题中是需要解先出现的，因为子串可以包含其他字符，在解出现之间都不能知道这个解需不需要被修正。

而这个问题中，我们很容易就能知道什么时候解需要修正：1、出现了其他字符；（need.count(c) == 0）2、字符数量过多了（窗口的size大于s2的size：right - left > s2.size()）。对于什么时候窗口中包含解，我们是更难以知道的，我们要验证窗口这一块区域，难度更大，也不合适。

至于缩减窗口的操作，经过思考很容易能够得到，就是将 字符从左边界移出，并更新window和valid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
	出现了其他字符如果没有处理会导致字符数量过多, 所以选择用 rigth - left > s2.size() 来判断
	我们需要判断结果的出现，所以将 = 放进了判断中
*/
while( right - left >= s2.size() ){
    if(valid == need.size()){
        // 满足情况
    }
    
    char d = s1[left];
    left++;
    if(need.count(d)){
        if(window[d] == need[d]){
            valid --;
        }
        window[d]--;
    }
}
  • 【无重复字符最长子串】

找到 s 中没有重复字符的最长子串。

"pwwkew" => "wke"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 这道题在框架上更为简单，是一个变种，但是在考虑缩减窗口上还是值得思考一番
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;
    int left = 0, right = 0;
    int len = 0;
    
    while(right < s.size()){
        char c = s[right];
        right++;
        window[c]++;
        /* 
        	缩减窗口的时机: 存在重复字符
        */
        while(window[c] > 1){
            char d = s[left];
            left++;
            window[d]--;
        }
        len = max(len, right-left);
    }
    return len;
}

二分搜索

【二分搜索】是十分常见的算法，其思想十分简单，但是在细节上的处理较为繁琐和复杂。

下面针对不同的场景和问题来探究一下二分搜索的细节

二分搜索框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearchFramework(vector<int> &nums, int target){
    int left = 0, right = ...
    whilie(...){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            ...
        } else if (nums[mid] > target){
            right = ...
        } else if (nums[mid] < target){
            left = ...
        }
    }
    return ...
}
  • ... 处就是之后要考虑的细节
  • left + (right - left) / 2 防止溢出问题

普通二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 使用 [left, right] 型的搜索区间
int binarySearch(vector<int> &nums, int target){
    int left = 0, right = nums.size() - 1;
    whilie( left <= right ){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target){
            right = mid - 1;
        } else if (nums[mid] < target){
            left = mid + 1;
        }
    }
    return -1;
}
  • right = nums.size() - 1 表示是在 [left, right] 这样的闭区间中搜索的 => 所以 while 中的循环条件是 left <= right 而不是 left < right 因为 left == right 时，[left, right]这个区间仍然是可用的。
  • 在 if-else 结构中的操作，和搜索区间是统一的。【搜索区间】其实就是可能出现解的区间，问题在于区间的开闭需要统一。比如 如果要使用闭区间，就要right = nums.size() - 1 ，在更新left 和 right 的时候也要保证更新后搜索区间是闭区间。相反，如果要使用开区间，就要 right = nums.size() ，在更新 left 和 right 时也要保证更新后搜索区间是开区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// [left, right) 型搜索区间
int binarySearch(vector<int> &nums, int target){
    int left = 0, right = nums.size(); // 注意
    while( left < right ){ // 注意
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target){
            right = mid; // 注意
        } else if (nums[mid] < target){
            left = mid + 1;
        }
    }
    return -1;
}

寻找左侧边界的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// [left, right] 搜索区间
int searchLeftBound(vector<int> &nums, int target){
    int left = 0, right = nums.size() - 1; // [1]
    while(left <= right){ // [2]
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            right = mid - 1; // [3]
        } else if(nums[mid] > target){
            right = mid - 1; // [4]
        } else if(nums[mid] < target){
            left = mid + 1;
        }
    }
    return (left < nums.size() && nums[left] == target) ? left : -1; // [5]
}
  • [1]：right = nums.size() - 1 意味着选择 闭区间 作为搜索区间 [left, right]
  • [2]：闭区间，有效的循环范围是 left <= right 或者说终止条件是 left = right + 1
  • [3]、[4]：保证搜索区间是闭区间（保证搜索区间之间没有重叠）
  • [5]：考虑终止条件时，left和right的情况：1、如果nums中存在target，nums[left] == target；2、如果nums中不存在target，left == nums.size() || left == 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// [left, right) 搜索区间
int searchLeftBound(vector<int> &nums, int target){
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            right = mid;
        } else if(nums[mid] > target){
            right = mid;
        } else if(nums[mid] < target){
            left = mid + 1;
        }
    }
    return (left < nums.size() && nums[left] == target) ? left : -1;
}

寻找右侧边界的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 使用 [left, right] 闭区间
int searchRightBound(vector<int> &nums, int target){
    int left = 0, right = nums.size() - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            left = mid + 1;
        } else if(nums[mid] > target){
            right = mid - 1;
        } else if(nums[mid] < target){
            left = mid + 1;
        }
    }
    return (right >= 0 && nums[right] == target) ? right : -1;
}
  • 重点说一下return：查找右边界的情况要些许复杂一点，和搜索区间的开闭有一定的关系。对于闭区间，终止条件是 left == right + 1，经过简单的推理可以知道如果nums中存在target的话，nums[right] == target；如果不存在的话，right == -1 || right = nums.size() - 1，分别对应于target小于全部nums元素和大于全部nums元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 使用 [left, right) 开区间
int searchRightBound(vector<int> &nums, int target){
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            left = mid + 1;
        } else if(nums[mid] > target){
            right = mid;
        } else if(nums[mid] < target){
            left = mid + 1;
        }
    }
    return (right > 0 && nums[right - 1] == target) ? right - 1 : -1;
}
  • 而对于开区间，如果nums中存在target，nums[right - 1] == target （因为是开区间，right位置的值是取不到的，所以需要减一）；如果不存在的话，right == 0 || right == nums.size()，同样分别对应于target小于全部nums元素和大于全部nums元素。

二分搜索的题型解析

从上面的例子可以看出，我们使用二分搜索的情景一般如下：【有序数组】、【查找元素或元素边界】

但是这大大限制了二分搜索的使用，下面我们对二分搜索使用的场景做一下抽象和总结。

首先，我们还是把眼光放到二分搜索的最普通的场景上。其实对二分搜索最重要的是【有序数组】，只有数组是有序的，我们才能根据中间位置的情况一次筛除掉一半的元素，以达到\(lg(n)\)的时间复杂度。

其实，【有序数组】本质上是【单调】，二分搜索之所以可以达到\(lg(n)\)的复杂度，就是利用了【单调】的性质。

进一步泛化，我们可以将上述情景抽象成

存在一个单调函数 f(x) ，给定 一个值 target ，返回 令 f(x) = target 成立的 x

（这个单调函数其实就是返回下标x对应的nums数组中的值）

所以，如果我们可以从题目中抽象出

1、自变量 x

2、建立在 x 上的单调函数

3、一个target

我们就可以使用二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int f(vector<int>& nums, int x){
    return nums[x];
}

int binarySearch(vector<int> &nums, int target){
    int left = 0, right = nums.size() - 1;
    whilie(left <= right){
        int mid = left + (right - left) / 2;
        int res = f(nums, mid);
        if(res == target) {
            return mid;
        } else if (res > target){
            right = mid - 1;
        } else if (res < target){
            left = mid + 1;
        }
    }
    return -1;
}

下面通过三个题目来具体讲解一下

  • 【875.爱吃香蕉的珂珂】

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

分析：

  1. x：吃香蕉的速度 k

  2. f(x)：在k的吃香蕉速度下，需要的时间

    \(f(x) = \sum_{i=1}^{n} \lceil \frac{piles[i]}{x} \rceil\)

    很明显是一个单调函数

  3. target：f(x) <= h

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
class Solution {
   public:
    int minEatingSpeed(vector<int>& piles, int h) {
        // 1 确定 吃香蕉速度 x 的区间 [low, high]
        int low = 1;
        int max = 0;
        for (int pile : piles) {
            if (max < pile) {
                max = pile;
            }
        }
        int high = max;
        
        // 2 二分搜索
        while (low <= high) {
            int mid = low + (high - low) / 2;
            long hours = timeCost(piles, mid);
            if (hours <= h) {
                high = mid - 1;
            } else if (hours > h) {
                low = mid + 1;
            }
        }

        return low;
    }

    // f(x)
    long timeCost(vector<int>& nums, int k) {
        long hours = 0;
        double speed = k;
        for (int i = 0; i < nums.size(); i++) {
            hours += ceil(nums[i] / speed);
        }
        return hours;
    }
};
  • 【1011.在-d-天内送达包裹的能力】

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

分析：

  1. x：船的运载能力

  2. f(x)：船的运载能力对应的需要的天数

    这个比较明显，很容易想到，船的运载能力越大，需要的天数肯定不会越多，应该是 非递增函数。

  3. target：f(x) <= days

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
class Solution {
   public:
    int shipWithinDays(vector<int>& weights, int days) {
        // 船的最低承载能力不能小于weights数组中最大的元素
        // 最高承载能力只要是weights数组元素之和即可
        int low = 0, high = 0;
        for (int weight : weights) {
            low = max(weight, low);
            high += weight;
        }
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int day = daysNeeded(weights, mid);
            if (day <= days) {
                high = mid - 1;
            } else if (day > days) {
                low = mid + 1;
            }
        }
        
        return low;
    }

    // f(x) 某运载能力下，需要的天数
    int daysNeeded(vector<int>& weights, int capacity) {
        int sum = 0;
        int days = 0;
        for (int weight : weights) {
            if (sum + weight > capacity) {
                days++;
                sum = weight;
            } else {
                sum += weight;
            }
        }
        if (sum > 0) days++;
        return days;
    }
};
  • 【410.分割数组的最大值】

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

这道题在f(x)的选择上比较巧妙

【分析】

首先，划分成多少个子数组（m）是确定的，子数组和的最大值只是跟划分方式有关。但是划分方式又不好用数表示出来，所以想写成 子数组和的最大值关于划分方式的函数 肯定是行不通的。

其次，我们要写成 f(x) 的形式，其中 x 肯定是数。在这道题中，唯一会变化的数就是子数组的和的最大值。所以大概可以确定，x 就是子数组和的最大值。

那 f(x) 是什么呢？根据题意大概就是【是否存在某种划分方式使得子数组和的最大值=x】这样的函数，得到的是 0 和 1。只要这个函数以某个分界点一边是0一边是1，也是一种单调函数。

但是很遗憾，【是否存在某种划分方式使得子数组和的最大值=x】这个函数得到的0/1分布是散乱的。

下面这个就是最有技巧的一步了：【是否存在某种划分方式使得子数组和的最大值 <= x】

这个函数得到的0/1分布就是以某个点为分界线的，是单调的。

  1. x：子数组和的最大值
  2. f(x)：是否存在某种划分方式使得子数组和的最大值 <= x
  3. target：f(x) == 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
class Solution {
   public:
    int splitArray(vector<int>& nums, int m) {
        // 1 判断 x 的范围: 数组nums的最大值 - 数组nums的元素之和
        int low = 0, high = 0;
        for (int num : nums) {
            low = max(num, low);
            high += num;
        }
        
        // 2 二分搜索
        while (low <= high) {
            int mid = low + (high - low) / 2;
            bool res = isExist(nums, m, mid);
            if (res == true) {
                high = mid - 1;
            } else if (res == false) {
                low = mid + 1;
            }
        }

        return low;
    }

    // 判断是否存在一种分割方式使得子数组的和的最大值<=x
    /**
     * 相反的思路: 将数组尽可能少的分成和小于x的子数组，如果最终得到的子数组数 <= m(要求划分的子数组个数), 那么就是c
     */
    bool isExist(vector<int>& nums, int m, int max) {
        long sum = 0;
        int cnt = 0;
        for (int num : nums) {
            if (sum + num > max) {
                cnt++;
                sum = num;
            } else {
                sum += num;
            }
        }
        if (sum > 0) cnt++;
        return cnt <= m;
    }
};

在两个数组中寻找第k个元素

4. 寻找两个正序数组的中位数

这道题使用二分查找的话，可以将问题转化成 【在两个有序数组中寻找第k小的元素】

【思路】是对k做二分。每次向前走k/2-1个元素，直到数组末尾，这样一次比较就可以排除k/2个元素，就是更小的那个元素对应数组走的那k/2个元素。

过程 
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
// nums1和nums2为两个有序数组
// 需要找到两个数组中第k小的元素 注意第1小的元素应该是0为下标
int findKthElement(vector<int>& nums1, vector<int>& nums2, int k) {
    int m = nums1.size(), n = nums2.size();
    int index1 = 0, index2 = 0;
    while(true){
        // 一个数组已经遍历完，直接去另一个数组的对应区间中找
        if (index1 >= m) return nums[index2+k-1];
        if (index2 >= n) return nums[index1+k-1];
        // base case 选择两个数组当前走到位置里更小的一个
        if (k == 1) return min(nums1[index1], nums2[index2]);
        
        // 需要考虑是否会超出数组长度
        int newIndex1 = min(index1+k/2, m) - 1;
        int newIndex2 = min(index2+k/2, n) - 1;
        
        if (nums1[newIndex1] >= nums2[newIndex2]) {
            k -= (newIndex2 - index2 + 1);
            index2 = newIndex2 + 1;
        } else {
            k -= (newIndex1 - index1 + 1);
            index1 = newIndex1 + 1;
        }
    }
}

田忌赛马

优势洗牌 870

算法思想：如果没办法赢 就用最差的去输

给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

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
bool cmp(const pair<int, int>& p1, const pair<int, int>& p2) {
    return p1.second < p2.second;
}
class Solution {
   public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        // 1 由于最终的结果是根据nums2的原始顺序的，所以不能直接对nums2进行排序，需要使用priority_queue进行排序
        vector<pair<int, int>> v;
        for (int i = 0; i < nums2.size(); i++) {
            v.push_back({i, nums2[i]});
        }
        sort(v.begin(), v.end(), cmp);
        // 2 排序nums1
        sort(nums1.begin(), nums1.end());
        // 3 使用双指针进行遍历
        vector<int> res(nums1.size());
        int right = nums1.size() - 1, left = 0;
        int index = right;

        while (index >= 0) {
            // 有优势
            if (nums1[right] > v[index].second) {
                res[v[index].first] = nums1[right];
                right--;
            } else {  // 没有优势
                res[v[index].first] = nums1[left];
                left++;
            }
            index--;
        }

        return res;
    }
};

原地修改数组

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

删除排序链表中的重复元素 83

移除元素 27

移动零 283

快慢指针

让快指针在前面探路，当快指针所指向的值和慢指针不同时，则将慢指针向前移动并更新其值为快指针所指向的值

  • 【删除有序数组中的重复项】
1
2
3
4
5
6
7
8
9
10
11
int removeDuplicates(vector<int>& nums) {
    int slow = 0, fast = 0;
    while(fast != nums.size()){
        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
ListNode* deleteDuplicates(ListNode* head) {
    if(head == nullptr) return nullptr;
    ListNode* slow = head, * fast = head;
    while(fast != nullptr){
        if(fast->val != slow->val){
            slow->next = fast;
            slow = slow->next;
        }
        fast = fast->next;
    }
    slow->next = nullptr;
    return head;
}
  • 【移除元素】
1
2
3
4
5
6
7
8
9
10
11
12
int removeElement(vector<int>& nums, int val) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        if (nums[left] == val) {
            nums[left] = nums[right];
            right--;
        } else {
            left++;
        }
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
// 快慢指针
int removeElement(vector<int>& nums, int val) {
    int slow = 0, fast = 0;
    while (fast != nums.size()) {
        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
21
22
23
24
25
/*
	移除0元素 + 末尾修改成0
*/
void moveZeroes(vector<int>& nums) {
    int len = removeElement(nums, 0);
    for(; len < nums.size(); len++){
        nums[len] = 0;
    }
}

// ku'ao
void moveZeroes(vector<int>& nums) {
    int slow = 0, fast = 0;
    while (fast != nums.size()) {
        if (nums[fast] != 0) {
            // swap
            int tmp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = tmp;
            
            slow++;
        }
        fast++;
    }
}

单链表问题

合并两个有序链表 21

合并K个升序链表 23

环形链表 141

环形链表Ⅱ 142

链表的中间节点 876 => 快慢指针 fast指针走2步，slow指针走1步

相交链表 160

删除链表的倒数第N个节点 19 => 双指针 一个指针先走n步，再两个指针同时走

  • 【合并两个有序链表】

采用双指针 + dummy 头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummy = new ListNode(-1);
    ListNode *p = dummy, *p1 = list1, *p2 = list2;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->val > p2->val) {
            p->next = p2;
            p2 = p2->next;
        } else {
            p->next = p1;
            p1 = p1->next;
        }
        p = p->next;
    }
    if (p1 != nullptr) {
        p->next = p1;
    }
    if (p2 != nullptr) {
        p->next = p2;
    }

    return dummy->next;
}
  • 【合并k个升序链表】

前一道题的升级版。难度在于如何快速找到 k 个 ListNode 中的最小结点 => 使用 priority_queue 最小堆

算法时间复杂度是 \(O(NlgK)\)

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
struct cmp {
    bool operator()(ListNode* p1, ListNode* p2) { return p1->val > p2->val; }
};

class Solution {
   public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 最小堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != nullptr) q.push(lists[i]);
        }

        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        while (!q.empty()) {
            ListNode* t = q.top();
            q.pop();
            p->next = t;
            p = p->next;
            // 该链表的下一个元素，加入堆中
            if (t->next != nullptr) {
                t = t->next;
                q.push(t);
            }
        }
        return dummy->next;
    }
};
  • 【删除链表的倒数第N个节点】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode *p1 = head, *p2 = dummy;
    // p1先向前走n步
    for (int i = 0; i < n; i++) {
        p1 = p1->next;
    }
    // p1和p2一起向前走 直到p1走到链表末尾
    while (p1 != nullptr) {
        p1 = p1->next;
        p2 = p2->next;
    }
    p2->next = p2->next->next;
    return dummy->next;
}
  • 【链表的中间节点】
1
2
3
4
5
6
7
8
9
10
11
// 快慢指针
ListNode* middleNode(ListNode* head) {
    ListNode *fast = head, *slow = head;
    // fast一次走两步 slow一次走一步
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next;
        fast = fast->next;
    }
    return slow;
}
  • 【环形链表】
1
2
3
4
5
6
7
8
9
10
11
12
13
bool hasCycle(ListNode* head) {
    ListNode *fast = head, *slow = head;
    // fast 一次走两部 slow 一次走一步
    // 由于fast更快 只要存在环 fast和slow一定会相遇
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            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
ListNode *detectCycle(ListNode *head) {
    bool hasCycle = false;
    ListNode *fast = head, *slow = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    if (!hasCycle) return nullptr;
    
    /*
    	设 s 是环的起点到链表起点的距离 l 是相遇点到环的起点的距离
    	易知 慢指针走过的距离为 s + l 快指针走过的是 2(s + l)
    	又 快指针比慢指针多走一个环的长度
    	所以 2(s+l) - (s+l) = n
    	s + l = n
    	=> s = n - l
    	所以 让慢指针回到链表起点 快指针继续向前 以相同的速度走 最后会在环的起点相遇
    */
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}
  • 【相交链表】
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
/*
	设A链表与B链表相交的部分长度为 m
	A链表剩余部分长度为 x B链表剩余部分长度为 y
	
	让 p1 先走A链表 走完再走B链表
	p2 先走B链表 走完再走A链表
	
	如果存在相交部分 那么就会在相交的起点相遇 因为走的距离都为 x + y + m
	如果不存在相交部分 那么就会使得 p1 p2 都为 nullptr
*/
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *p1 = headA, *p2 = headB;
    while (p1 != p2) {
        if (p1 == nullptr)
            p1 = headB;
        else
            p1 = p1->next;

        if (p2 == nullptr)
            p2 = headA;
        else
            p2 = p2->next;
    }
    return p1;
}

链表操作递归思想

反转链表 206

反转链表 Ⅱ 92

  • 反转整个链表
1
2
3
4
5
6
7
8
ListNode* reverse(ListNode* head){
    if(head == nullptr || head->next == nullptr) return head;
    ListNode* p = reverse(head->next);
    // 把后一个结点的next指针指向当前的节点(head)
    head->next->next = head;
    head->next = nullptr;
    return p;
}
  • 反转链表的前n个结点
1
2
3
4
5
6
7
8
9
10
11
ListNode* successor = nullptr;
ListNode* reverseN(ListNode* head, int n){
    if(n == 1){
        successor = head->next;
        return head;
    }
    ListNode* p = reverseN(head->next, --n);
    head->next->next = head;
    head->next = successor; // 改变每次的后继 使得反转后的最后一个结点指向链表剩余部分(n+1个结点)
    return p;
}
  • 反转链表的一部分
1
2
3
4
5
6
7
8
ListNode* reverseBetween(ListNode* head, int left, int right){
    if(left == 1){ // 就是反转前n个结点
        return reverseN(head, right-left+1);
    }
    // 向前di'gui
    head->next = reverseBetween(head->next, left-1, right-1);
    return head;
}
leetcode刷题笔记
#leetcode
刷题笔记1-数组/链表
http://example.com/2022/09/15/leetcode/刷题笔记1（数组链表）/
作者
zhc
发布于
2022年9月15日
许可协议