刷题笔记11--面试必知必会

nSum问题

nSum问题就是给定一个整数数组 nums 和一个 target，要求找到 n 个nums中的元素，使得这n个元素的和等于 target，要求返回所有可能的不重复的情况。

【2Sum】问题是这类的基本情况，将数组排序后使用双指针即可解决问题。对于\(n > 2\)的情况，尤其是n比较大时，直接解决是比较困难的，可以采用==递归==解决。下面给出解决【nSum】问题的代码。

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
/** 
	nums: sorted之后的数组
	start: 开始寻找的位置
	k: 需要寻找多少个元素之和
	target: 目标值
*/
vector<vector<int>> nSum(vector<int>& nums, int start, int k, int target) {
    int n = nums.size();
    vector<vector<int>> res;
    if(k == 2){ // base case k ==
        int i = start; int j = n - 1;
        while(i < j){
            int left = nums[i]; int right = nums[j];
            int sum = left + right;
            if(sum == target){
                res.push({left, right});
                while(i < j && nums[i] == left) i++;
                while(i < j && nums[j] == right) j--;
            } else if(sum > target){
                while(i < j && nums[j] == right) j--;
            } else {
                while(i < j && nums[i] == left) i++;
            }
        }
    } else { // other case k > 2
        int i = start;
        while(i < n){
            int val = nums[i];
            int sub_target = target - val;
            vector<vector<int>> sub_res = nSum(nums, i+1, k-1, sub_target);
            for(vector<int> sub_res_i : sub_res){
                sub_res_i.push_back(val);
                res.push_back(sub_res_i);
            }
            while(i < n && nums[i] == val) i++;
        }
    }
    return res;
}

区间问题

区间问题就是给定一些区间，然后需要求解这些区间的交集、或者合并区间等问题

解决这类问题最核心的思想就是==排序==+==讨论==。

针对不同的问题，需要进行不同的排序，可能是对起点排序，也可能是对终点排序，有可能是升序，也有可能是降序。

1
2
3
4
5
6
7
static bool cmp(vector<int>& a, vector<int>& b){
    if(a[0] != b[0]) return a[0] < b[0];
    else return a[1] > b[1];
}

// 对nums进行排序，左端点升序排列，左端点相同右端点降序排列
sort(nums.begin(), nums.end(), cmp);

题目列表：

452. 用最少数量的箭引爆气球

435. 无重叠区间

1288. 删除被覆盖区间

56. 合并区间

986. 区间列表的交集

1024. 视频拼接

一道别致的区间问题！这道题在对区间进行排序之后的操作更为复杂一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int videoStitching(vector<vector<int>>& clips, int time) {
    sort(clips.begin(), clips.end(), cmp);
    
    // 由于是需要找出最少，所以就需要挑选出最合适的片段
    int n = clips.size();
    int i = 0;
    int end = 0;
    int cnt = 0;
    while(i < n){
        int max = -1;
        // 在后面有重叠的区间中找到终点最大的那个区间
        while(i < n && clips[i][0] <= end){
            if (clips[i][1] > max) max = clips[i][1];
            i++;
        }
        if(max == -1) return -1; // 中间有断开或者片段用完了但是没到time
        end = max;
        cnt ++;
        if (end >= time) return cnt;
    }
    return -1;
}

快速选择算法

215. 数组中的第K个最大元素

快速排序算法

快排（quick-sort）是一种经典的排序算法，和归并排序（merge-sort）一样都是 divide-and-conquer 类型的算法，平均时间复杂度为 \(O(NlogN)\)

【思路】

快排的思路是，要对nums[lo...hi]排序，先找到一个分界点pivot，然后使得nums[lo...pivot-1]都小于nums[pivot]，nums[pivot+1...hi]都大于nums[pivot]，然后递归地在nums[lo...pivot-1]和nums[pivot+1...hi]上执行相同的操作。

【实现过程】

首先可以轻易写出下面两个函数，最主要的难点是实现partition函数。

1
2
3
4
5
6
7
8
9
10
void quick_sort(vector<int>& nums){
    quick_sort_helper(nums, 0, nums.size() - 1);
}

void quick_sort_helper(vector<int>& nums, int i, int j){
    if(i >= j) return;
    int pivot = partition(nums, i, j);
    quick_sort_helper(nums, i, pivot-1);
    quick_sort_helper(nums, pivot+1, j);
}

partition函数所做的工作就是，对一个数组nums[lo...hi]，返回一个下标pivot，使得数组nums[lo...pivot-1]部分的元素全部都小于nums[pivot]，数组nums[pivot+1...hi]部分的元素全部都大于nums[pivot]。

  1. 首先任意选取一个值作为pivot，比如选择最后一个元素`
  2. smaller_idx变量是用来记录所有<=nums[pivot]的元素的下标
  3. 遍历数组，当遇到<=nums[pivot]的元素时，就要把它放在smaller_idx指定的位置上（for循环中if块中的内容）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int partition(vector<int>& nums, int lo, int hi){
    int pivot = nums[hi];
    int smaller_idx = lo-1; // 标记<=nums[pivot]元素的下标
    for(int i = lo; i <= hi; i++){
        if(nums[i] <= pivot){
            smaller_idx ++;
            swap(nums, smaller_idx, i);
        }
    }
    return smaller_idx;
}

void swap(vector<int>& nums, int i, int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

quick-sort

上面的partition函数返回的pivot其实就是数组的第pivot大元素，而问题需要的是第k大元素，所以可以借用【二分搜索】思想进行求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findKthLargest(vector<int>& nums, int k) {
    int lo = 0; int hi = nums.size() - 1;
    int idx = nums.size() - k;
    while(lo <= hi){
        int pi = partition(nums, lo, hi);
        if(idx > pi){
            lo = pi+1;
        } else if (idx < pi){
            hi = pi-1;
        } else {
            return nums[pi];
        }
    }
    return -1;
}

二叉堆

这道题最简单的还是采用二叉堆（优先队列）的解法

1
2
3
4
5
6
7
8
9
10
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, std::greater<int>> pq; // 采用小顶堆
    for(int i : nums){
        pq.push(i);
        if(pq.size() > k){
            pq.pop();
        }
    }
    return pq.top();
}

priority_queue数据结构自定义比较如何书写？

1、首先优先队列默认情况下是使用less比较，即大顶堆（最大元素作为堆顶出现）。如果想要改成小顶堆，需要使用greater比较。

2、如果要自定义优先队列的比较，可以在一个结构体里==重载()运算符==

1
2
3
4
5
struct cmp{
  bool operator()(vector<int>& a, vector<int>& b){
      // ...
  }  
};

3、或者可以重载复合数据类型的比较运算符（改变原本less和greater中比较运算符的含义）

sort函数中的自定义比较应该如何书写？

1、默认情况下按照升序对容器内元素进行排序。

2、一般情况下只要重写一个比较函数传入sort函数即可

1
2
3
4
5
bool cmp(vector<int>& a, vector<int>& b){
    // ...
}

sort(container.begin(), container.end(), cmp); // container 是 vector<vector<int>>

但是如果要在类中使用，自定义的比较函数一定得是静态成员函数或者全局函数

因为std::sort函数是全局的，不能依赖于只有创建实例后才能使用的普通成员函数

运算优先级：分治算法

241. 为运算表达式设计优先级

使用递归思想解决问题，一定要从整体出发考虑问题的结构，而不能局限于某个细节。将大问题不断分解成规模更小的子问题，当规模小到一定程度时就可以轻易求解，然后再将小规模问题的答案合并，得到最终问题的结果，这就是分治的思想。

这道题也是一样，给定一个表达式字符串，要求出该表达式所有可能的结果。无论如何改变运算符优先级，或者说增加括号，本质上表达式的计算都可以回到【操作数1 操作符 操作数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
26
27
28
vector<int> diffWaysToCompute(string expression) {
    vector<int> res;
    int n = expression.size();
    for(int i = 0; i < n; i++){
        char c = expression[i];
        if (c == '+' || c == '-' || c == '*'){
            vector<int> left = diffWaysToCompute(expression.substr(0, i));
            vector<int> right = diffWaysToCompute(expression.substr(i+1, n - i));
            for (int op1 : left){
                for (int op2 : right){
                    switch(c){
                        case '+': res.push_back(op1+op2); break;
                        case '-': res.push_back(op1-op2); break;
                        case '*': res.push_back(op1*op2); break;
                    }
                }
            }
        }
    }
    if (res.empty()){
        int val = 0;
        for(int i = 0; i < n; i ++){
            val = 10 * val + expression[i] - '0';
        }
        res.push_back(val);
    }
    return res;
}

贪心算法

加油站

134. 加油站

看到问题的一个反应就是把两个数组变成一个数组diff，diff[i]表示在i加油站加完油开到i+1加油站的油量变化。那么要找到那个点，应该尽可能的让车在刚开始一段时间油量尽可能多，这样才能保证最后可以走完一圈。可以将diff的值标在图上，连起来之后最低点的下一个点就应该是出发的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int n = gas.size();
    vector<int> diff; // 从i加完油开到i+1剩下的油量
    int sum = 0;
    for (int i = 0; i < n; i++){
        int onediff = gas[i] - cost[i];
        diff.push_back(onediff);
        sum += onediff;
    }
    if (sum < 0) return -1;
    int total = 0;
    int res = 0; int min = 10000;
    for (int i = 0; i < n; i ++){
        total += diff[i];
        if (total < min){
            min = total;
            res = i;
        }
    }

    return (res+1)%n;
}

换一个思路，这道题更为普遍的想法应该是用一个双重循环去枚举所有的情况。可以增加一个trick：当发现从i开到j不能到达时，那么i到j中间的任何一个点出发都行不通。这样就避免了很多重复的情况，复杂度可以达到线性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int canCompleteCircuit(vector<int>& gas, vector<int>& cost){
    int n = gas.size();
    vector<int> diff; // 从i加完油开到i+1剩下的油量
    int sum = 0;
    for (int i = 0; i < n; i++){
        int onediff = gas[i] - cost[i];
        diff.push_back(onediff);
        sum += onediff;
    }
    if (sum < 0) return -1;
    for(int i = 0; i < n; i++){
        if (diff[i] < 0) continue;
        int j = (i+1)%n;
        int total = diff[i];
        for (; j != i; j = (j+1)%n){
            total += diff[j];
            if(total < 0) break;
        }
        if (j == i) return i;
        i = (j + n - 1) % n; // trick
    }

    return -1;
}

分割数组为连续子序列

659. 分割数组为连续子序列

贪心算法：要想满足上述条件，应该使得每个子序列尽可能地长，即尽可能不要建造新的子序列。

所以当遍历到nums中x时，判断是否有以x-1结尾的子序列，如果有：将x加在子序列的后面；如果没有：看x+1和x+2这两个数字是否还有，如果还有，则建造一个以x+2结尾的子序列，如果没有，则返回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
bool isPossible(vector<int>& nums) {
    unordered_map<int, int> cnt; // 存储nums中每个数字的个数
    unordered_map<int, int> endx; // 存储以x结尾的子序列的个数
    
    for (int num : nums) cnt[num] ++;
    
    for (int x : nums) {
        if (cnt[x] > 0) { // 该数字还有
            if (endx[x-1] > 0) { // 存在以x-1结尾的子序列
                endx[x-1] --;
                endx[x] ++;
                cnt[x] --;
            } else { // 不存在以x-1结尾的子序列
                if (cnt[x+1] > 0 && cnt[x+2] > 0) {
                    endx[x+2]++;
                    cnt[x]--; cnt[x+1]--; cnt[x+2]--;
                } else {
                    return false;
                }
            }
        }
    }
    
    return true;
}

计算器

224. 基本计算器

227. 基本计算器 II

给定一个字符串，包含数字、四则运算符、括号以及空格，要求计算该表达式的值

可以将这个问题进行分解，比如：如何将字符串中的数提取出来、如何处理四则运算以及如何处理括号。

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
int calculate(string s){
    stack<int> stk;
    int n = s.size();
    int i = 0;
    int val = 0;
    char sign = '+';
    while(i < n){
        // 处理字符串中的数字
        if (s[i] >= '0' && s[i] <= '9'){
            val = 10 * val + (s[i] - '0');
        }
        // 处理四则运算
        if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == n-1){
            switch(s[i]){
                case '+': stk.push(val); break;
                case '-': stk.push(-1 * val); break;
                case '*': val = stk.top() * val; stk.pop(); stk.push(val); break;
                case '/': val = stk.top() / val; stk.pop(); stk.push(val); break;
            }
            val = 0;
            sign = s[i];
        }
        // 处理括号
        if (s[i] == '('){
            int start = i + 1;
            int cnt = 1;
            while(cnt != 0){
                i ++;
                if (s[i] == '(') cnt ++;
                if (s[i] == ')') cnt --;
            }
            val = calculate(s.substr(start, i - start)); // 递归
        }
        
        i ++;
    }
    
    int res = 0;
    while(!stk.empty()){
        res += stk.top();
        stk.pop();
    }
    
    return 
}

完美矩形

391. 完美矩形

精确覆盖的意思是：这些小矩形可以恰好组成一个大矩形，中间不能有重叠，也不能有空隙。

  • 首先，很明显可以从面积出发。找到组成的大矩形的顶点，算出大矩形的面积，如果小矩形面积之和不等于大矩形面积的话，肯定实现不了。
  • 其次，尽管算出来面积是相等的，也不能保证就可以恰好组成一个大矩形。可以从顶点出发，如果可以恰好围成一个大矩形，那么在所有小矩形的顶点中，有且只有4个顶点只出现一次（围成大矩形的四个顶点/角），其他顶点一定只出现2次或者4次。
  • 由下图可以看出，只有当某个顶点只出现奇数次才会作为围成图形的角。很明显，要想恰好围成大矩形，必须有其只有4个顶点符合情况一，且不能出现情况三。

图片来源：《labuladong算法秘籍》

注意：

  1. 找到的大矩形顶点只是理论上的：就是说给定这些矩形，所可以围成的大矩形的顶点理论上是这个值。
  2. 考虑顶点的时候，除了判断只有4个顶点出现1次，还需要判断这4个顶点是否就是理论上的那4个顶点。
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
typedef pair<int, int> p;
bool isRectangleCover(vector<vector<int>>& rectangles) {
    map<p, int> points;
    // 大矩形的左下顶点坐标和右上顶点坐标
    long long X1 = INT_MAX, Y1 = INT_MAX, X2 = INT_MIN, Y2 = INT_MIN;
    long long areaSum = 0;
    for (vector<int> rectangle : rectangles) {
        long long x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
        X1 = min(X1, x1);
        Y1 = min(Y1, y1);
        X2 = max(X2, x2);
        Y2 = max(Y2, y2);
        areaSum += (x2 - x1) * (y2 - y1);
        p p1 = {x1, y1}, p2 = {x1, y2}, p3 = {x2, y1}, p4 = {x2, y2};
        points[p1]++;points[p2]++;points[p3]++;points[p4]++;
    } 
    long long bigArea = (X2 - X1) * (Y2 - Y1);
    if (areaSum != bigArea) return false; // 面积不相等 false
    int v_cnt = 0;
    for (const auto& p0 : points){
        // 计算图形中角的个数
        if (p0.second % 2 == 1) v_cnt++;
    }
    if (v_cnt != 4) return false; // 如果围成大矩形，只能有4个角
    // 最后还需要判断这四个角确实是大矩形的四个顶点
    p p1 = {X1, Y1}, p2 = {X1, Y2}, p3 = {X2, Y1}, p4 = {X2, Y2};
    return points[p1]==1 && points[p2]==1 && points[p3]==1 && points[p4]==1;
}

这里使用的是map而不是一般的unordered_map，原因是在unordered_map是使用hash来计算key，但是hash不能处理pair类型数据，所以不能在unordered_map中使用pair数据类型。

参考文章

leetcode刷题笔记
#leetcode
刷题笔记11--面试必知必会
http://example.com/2022/11/19/leetcode/刷题笔记11（面试）/
作者
zhc
发布于
2022年11月19日
许可协议