说明

  • 记录一下左程云算法讲课的内容，方便查找
  • 左程云：算法
  • 基础提升
    • 哈希函数与哈希表：大文件限制内存求数字、哈希表与哈希函数性质、布隆过滤器与位图、一致性哈希
    • 有序表与并查集：岛屿问题、并查集、KMP
    • KMP与Manacher：Manacher算法、窗口内最大值最小值更新结构、单调栈
    • 滑动窗口与单调栈：树形DP、Morris遍历、大文件小内存问题
    • 二叉树的Morris遍历：大数据题目解题技巧（大文件找中位数、重复数）、位运算（不使用比较进行比较、幂次判断、加减乘除）
    • 大数据题目：暴力递归改动态规划（机器人移动，最少的硬币数）
  • 技巧
    • 中级提升班1：滑动窗口、打表优化、预处理、随机函数位运算
    • 中级提升班2、3：递归转dp、遍历、哈希表、业务分析、dp、辅助栈、二叉树套路、右上角查找
    • 中级提升班4：业务分析（考虑当前位置）、宏观调度（旋转打印类）

基础提升-哈希函数与哈希表（P40）

哈希函数性质介绍

  • 视频：0:02:40-0:21:00

求大文件中出现次数最多的数（内存限制1G）

  • 视频：0:21:00-0:36:40
  • 有一个大文件，里面数的范围是$[0, 2^{32}-1]$，数量为40亿，内存限制为1G，求出现次数最多的数

image-20220415093025325

思路1——直接使用哈希表进行统计

  • 这种方案不行，会爆内存
  • 因为哈希表中一条记录至少8字节，还不考虑额外开销，当40亿个数都不相同时，所占内存为8字节 * 40亿 = 320亿字节 = 32G(因为$1G = 2^{30}字节\approx10亿$)

思路2——哈希表改进

  • 前置知识
    • 哈希表空间的使用只和不同数的种类有关，即假设1出现2次和3出现1w次，所占用的空间一样，都是8字节（不考虑额外开销，key和val都是int）
    • 经过哈希函数计算后，数在$[0,S]$均匀分布，那么再模上一个M，最终在$[0,M-1]$均匀分布
  • 对文件中的每个数用一个哈希函数计算得到一个结果，然后对一个M取模（此处取M=100），那么每个数会均匀分布在0-99号文件（相同的数会进同一个文件），即0-99号文件中，数的种类接近
  • 然后找到每个文件中出现次数最多的那个，合并100个结果，即可找到最终答案
  • 由于分成了100个文件，那么每个文件所占用的空间只有32G/100，符合要求

image-20220415095421591

哈希表性质介绍

  • 视频：0:36:40-0:54:20
  • 哈希函数 + 开链法

设计RandomPool结构

image-20220415101001875

思路及代码

  • 哈希表+数组或者两个哈希表+数量size
    • 哈希表 + 数组：哈希表存[字符串，下标]，数组存[下标，字符串]
    • 两个哈希表：哈希表1存[字符串，下标]，哈希表2存[下标，字符串]，size即为元素个数
  • 删除时，和最后一个元素进行交换
  • 等概率返回：使用随机生成器rand()得到0-size-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
class RandomizedSet {
private:
    // value对应的下标
    unordered_map<int, int> valToIndex;
    // 存储value
    vector<int> arr;

public:
    RandomizedSet() {

    }
    
    bool insert(int val) {
        if (valToIndex.count(val)) {
            return false;
        }
        valToIndex[val] = arr.size();
        arr.push_back(val);

        return true;
    }
    
    bool remove(int val) {
        if (!valToIndex.count(val)) {
            return false;
        }
        // 找到对应元素的下标
        int index = valToIndex[val];
        // 把arr中对应的元素和arr中最后一个元素互换位置
        valToIndex[arr.back()] = index;
        swap(arr[index], arr.back());
        valToIndex.erase(val);
        arr.pop_back();

        return true;
    }
    
    int getRandom() {
        return arr[rand() % arr.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

布隆过滤器与位图

  • 视频：1:07:35-1:55:40

前置知识

  • 需要一个集合（有增加、查询功能，没有删除功能）

    • 如维护一个网址黑名单，存放url，每个url限制为64字，共100亿条数据
    • 如爬虫去重问题：多线程时不想爬取同一个url

  • 直接用hashset存，内存代价较高，即需要64字节 * 100亿= 6400亿字节 = 640G

  • 布隆过滤器：放置在内存，但允许一定的失误率，失误率指不在黑名单，但误报了在里面（通过人为设计，可以降得很低）

位图

  • 位图：每个位置是1 bit，那么长度为100的共占100 * 1/8 字节

  • 实现：通过基础类型拼凑实现

    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
    /*
     * @Author       : 955nice
     * @Date         : 2022-04-15 10:40:48
     * @version      : 1.0
     * @LastEditors  : 955nice
     * @LastEditTime : 2022-04-15 10:57:41
     * @Description  : 基础类型实现bitmap
     * @FilePath     : /code/job/bitmap.cpp
     * Talk is cheap, Show me the code
     * @refer        : None
     */
    #include <iostream>

    using namespace std;

    int main()
    {
        int a = 0;          // 32bit:4byte * 8bit
        int arr[10];        // 320bit:4 byte * 8bit * 10
        // arr[0] int 0 ~ 31
        // arr[1] int 32 ~ 63
        // arr[2] int 64 ~ 95
        
        // 想取得178bit的状态
        int i = 178;        
        int numIndex = 178 / 32;
        int bitIndex = 178 % 32;
        // 拿到第i位的状态
        int s = ((arr[numIndex] >> bitIndex) & 1);
        // 将第i位的状态修改为1
        arr[numIndex] = arr[numIndex] | (1 << bitIndex);
        // 将第i位的状态修改为0
        arr[numIndex] = arr[numIndex] & (~(1 << bitIndex));

        return 0;
    }

布隆过滤器

  • 哈希函数 + 位图

  • 每一个url使用k个哈希函数进行求值，求得的结果再模以M（位图长度），得到最终结果，将位图中这一位的状态修改为1（假设初始为0）

  • 在查询某个url时，同样使用k个哈希函数进行求值，求得的结果再模以M，得到最终结果，如果和位图中这些位都为1，那么即存在在黑名单中

    image-20220415110611501

  • 位图M越大，失误率越低，哈希函数数量k与数据和位图大小有关

    image-20220415110711862

计算公式

  • 使用前提
    • 符合集合查询的要求
    • 要求知道样本量n和失误率p
    • 注：单样本大小不影响布隆过滤器设计
  • 公式1：$m = -\frac{n*lnp}{(ln2)^2}$，计算位图大小，那么假设失误率p=0.0001，n=100亿，那么占用内存大约为26G
  • 公式2：$k = ln2\frac{m}{n} \approx 0.7\frac{m}{n}$，计算哈希函数个数，约等于19（向上取整）
  • 公式3：$p_{真}=(1-e^{-\frac{n*k_{真}}{m_{真}}})^{k_{真}}$，如果实际内存可以更大，可以算出真实失误率

image-20220415111956140

一致性哈希

基础提升-有序表与并查集（P41）

岛屿数量

image-20220422084336631

思路及代码

  • 标准bfs感染过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void bfs(vector<vector<int>>& arr, int m, int n, int i, int j) {
    if (i < 0 || i >= m || j < 0 || j <= n || arr[i][j] != 1) return ;
    arr[i][j] = 2;
    bfs(arr, m, n, i - 1, j);
    bfs(arr, m, n, i + 1, j);
    bfs(arr, m, n, i, j - 1);
    bfs(arr, m, n, i, j + 1);
}

int countIslands(vector<vector<int>>& arr) {
    int m = arr.size(), n = arr[0].size();
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1) {
                res++;
                bfs(arr, m, n, i, j);
            }
        }
    }
    
    return res;
}

并查集

  • 视频：0:25:00-1:05:50

思路及代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*
 * @Author       : 955nice
 * @Date         : 2022-04-01 10:04:34
 * @version      : 1.0
 * @LastEditors  : 955nice
 * @LastEditTime : 2022-04-01 11:06:27
 * @Description  : 并查集
 * @FilePath     : /code/job/union_search.cpp
 * Talk is cheap, Show me the code
 * @refer        : None
 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 全局变量，记录合并后不同集合的数量
int cnt = 0;

// 初始化父亲为自己
void init(vector<int>& father) {
    for (int i = 1; i <= father.size(); i++) father[i] = i;
}

// 查找x所在集合的根节点
int findFather(vector<int>& father, int x) {
    int a = x;
    // 寻找根节点
    while (x != father[x]) {
        x = father[x];
    }
    // 路径压缩，只存每个节点的祖父
    // 此时x存放的是根节点，将路径上的所有节点的father都改成根节点
    while (a != father[a]) {
        int z = a;                      // 因为a会被father[a]覆盖，所以保存一下
        a = father[a];                  // a回溯父节点
        father[z] = x;                  // 将原先节点a的父亲修改为x
    }

    return x;
}

int minimumCost(vector<vector<int>> &conections, int n) {
    // 题目要求最小路径和，先根据路径和进行排序
    sort(conections.begin(), conections.end(), [&](vector<int>& a, vector<int>& b){return a[2] < b[2];});
    for (int i = 0; i < conections.size(); i++) {
        cout << conections[i][0] << ", " << conections[i][1] << ", " << conections[i][2] << endl;
    }

    vector<int> father(n + 1);          // 节点一般从1开始，所以数组开大一个
    init(father);                       // 初始化
    int dis = 0;                        // 最小通路路径
    // 根据规则建立并查集
    for (int i = 0; i < conections.size(); i++) {
        int a = conections[i][0];
        int b = conections[i][1];
        int distance = conections[i][2];
        int faA = findFather(father, a);
        int faB = findFather(father, b);
        // 不是一个集合，进行合并
        if (faA != faB) {
            father[faA] = faB;
            dis += distance;
            cnt++;
        }
    }
    // 如果两点之间不在一个集合，说明不能连通
    for (int i = 2; i <= n; i++){
        if (findFather(father, i) != findFather(father, i - 1)) {
            cnt = -1;
            return -1;
        }
    }
    return dis;
}

int main()
{   
    // 自定义节点个数
    int n = 5;                          
    // conections[i]表示conections[i][0]和conections[i][1]之间的距离是conections[i][2]
    vector<vector<int>> conections = {
        {1, 2, 6},
        {1, 3, 5},
        {1, 5, 9},
        {2, 3, 2},
        {3, 4, 7}
    };
    int dis = minimumCost(conections, n);
    cout << "cnt = " << cnt << ", distance = " << dis << endl;
    return 0;
}

岛进阶（并行算法）

  • 二维数组巨大，需要先进行分割计算然后合并结果=>并查集
  • 视频：1:05:50-1:20:40

思路

  • 记录切割边界信息（由哪个点感染得到）

image-20220422090003628

KMP

  • 视频：1:28:00-3:15:20

思路及代码

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
vector<int> getNext(string str2) {
    if (str2.size() == 1) return {-1};
    int n = str2.size();
    vector<int> next(n);
    // 人为规定前两个的值
    next[0] = -1;
    next[1] = 0;
    // 当前要求的next[i]
    int i = 2;
    // 表示 i 前一个 i-1 位置最长前缀和后缀长度
    int cnt = 0;
    while (i < n) {
        // 如果相等，那么next[i]就等于next[i-1] + 1
        // 注意此时的next[i - 1]中i - 1不一定是i前面的位置，所以这里使用cnt
        if (str2[i - 1] == str2[cnt]) {
            next[i++] = ++cnt;
        } else if (cnt > 0) {
            // 如果不等，且cnt还能往前跳，那么继续比较
            cnt = next[cnt];
        } else {
            // 比较到的第0个还不等，那么说明此时没有前后缀相等的情况
            next[i++] = 0;
        }
    }
    
    return next;
}

int strstr(string str1, string str2) {
	// 注意，这是特殊要求，其他题目不一定是这样
    if (str2.empty()) return 0;
    // 当str1长度小于str2长度时，一定无法匹配
    if (str1.size() < str2.size()) return -1;
    // i 用于匹配 str1 中的字符
    // j 用于匹配 str2 中的字符
    int i = 0, j = 0;
    // 当两者都不越界时
    while (i < str1.size() && j < str2.size()) {
		// 如果比较的两个字符相等，那么都往右边移动
        if (str1[i] == str2[j]) {
            i++;
            j++;
        } else if (next[j] == -1) {
            // 如果 j 比较到了位置0，还不想等，此时 j 不能往前跳了，所以只能 i 往下移动
            // 条件等价于j == 0
            i++;
        } else {
            j = next[j];
        }
    }
    
    // 如果 i 或者 j 越界了
    return j == str2.size() ? i - j : -1;
}

基础提升-KMP与Manacher（P42）

Manacher

  • 视频：0:02:35-1:40:00

思路及代码

  • 详细笔记：Manacher
  • 下列代码与笔记略有不同，与视频讲解一致，区别在于一个求长度，一个求真正的串
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
int maxLcpsLength(string s) {
        // 处理原串，添加特殊字符
        string cur = "#";
        for (auto c : s) {
            // 需要分行写，否则会乱码
            cur += c;
            cur += '#';
        }
        int n = cur.size();
        vector<int> pArr(n);        // 回文半径数组
        int C = -1;                 // 中心
        int R = -1;                 // 回文右边界的再往右一个位置，最右的有效区是R - 1，实际代码为了简便，做了一点小改进
        int maxLen = INT_MIN;       // 扩出来的最大值
        // 对每一个位置都求回文半径
        for (int i = 0; i < n; i++) {
            // i至少的回文区域，先给pArr[i]
            // 下面这行整合了四种情况
            // 如果i在R外，那么至少有一个位置（本身）不需要考虑
            // 如果i在R内，那么两者中的最小值即为至少的回文区域
            pArr[i] = R > i ? min(pArr[2 * C - i], R - i) : 1;
            
            // 看是否还能扩展
            // 针对情况1和情况2的情况3，可以扩展
            // 针对情况2的情况1和情况2，进行一次比较就会失败，不会影响复杂度
            while (i + pArr[i] < n && i - pArr[i] > -1) {
                if (cur[i + pArr[i]] == cur[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            // 判断此时的回文右边界是否已经超出之前的位置，如果是进行更新
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
			maxLen = max(maxLen, pArr[i]);
        }

        return maxLen - 1;
    }

窗口内最大值最小值更新结构——双端队列

image-20220429201420122

思路及代码

  • 首先窗口左右边界L和R只能往右动，左边界永远不要超过右边界

  • 求最大值：保证双端队列是单调递减的

    如果求最小值：保证双端队列是单调递增的

  • 双端队列deque放下标（为了获得更多的信息）

  • 时间复杂度：每个位置数最多进窗口一次，最多出窗口一次，双端队列的更新总代价为O(n)，一共n个数，所以单次的平均时间复杂度为O(1)

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:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 单调递减队列
        deque<int> deq;
        for (int i = 0; i < k; i++) {
            // 如果当前值比之前的大，那么在窗口内之前的必不可以为最大值
            while (!deq.empty() && nums[i] > nums[deq.back()]) deq.pop_back();
            deq.push_back(i);
        }
        vector<int> ans = {nums[deq.front()]};
        for (int i = k; i < nums.size(); i++) {
            // 如果当前值比之前的大，那么在窗口内之前的必不可以为最大值
            while (!deq.empty() && nums[i] > nums[deq.back()]) deq.pop_back();
            deq.push_back(i);
            // 如果窗口越界，一直弹出
            while (i - deq.front() >= k) deq.pop_front();
            ans.push_back(nums[deq.front()]);
        }

        return ans;
    }
};

单调栈*

image-20220429203236054

思路及代码

  • 无重复值：求左右比当前位置大的最近位置：单调递减栈

  • 有重复值：单调栈每个元素时一个链表（相同数字串成链表）

    image-20220429204535765

累计和与最小值乘积的最大值——单调栈*

  • 视频：2:37:05-2:47:55
  • 数组中元素都为正数，子数组是连续的

image-20220429204727958

思路及代码

  • 要点：必须包含i位置的值，且i位置为子数组中的最小值，哪个子数组得到的指标A得到的结果最大
  • 单调递增栈实现（即求出每个位置左右两边比当前位置小的范围）

基础提升——滑动窗口与单调栈（P43）

树形DP套路

  • 使用前提

    image-20220430092551554

  • 步骤

    image-20220430092621169

二叉树节点间的最大距离——树形DP

image-20220430092708478

思路及代码

  • 考虑以X为头的数，两种情况

    • 最长距离和X有关，即路径经过X
    • 最长距离和X无关，即路径在左孩子上或路径在右孩子上

    image-20220430093630400

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    struct Info {
        int maxDistance;
        int height;
        Info(int dis, int h):maxDistance(dis), height(h){}
    };

    Info* process(TreeNode* x) {
        if (x == nullptr) return new Info(0, 0);
        Info* leftInfo = process(x->left);
        Info* rightInfo = process(x->right);
        int p1 = leftInfo->maxDistance;
        int p2 = rightInfo->maxDistance;
        int p3 = leftInfo->height + 1 + rightInfo->height;
        int maxDistance = max(p3, max(p1, p2));
        int height = max(leftInfo->height, rightInfo->height) + 1;

        return new Info(maxDistance, height);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        return process(root)->maxDistance - 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
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    private:
        int ans = 0;

        // 用来判断节点个数
        int process(TreeNode* root) {
            if (root == nullptr) return 0;
            int left = process(root->left);
            int right = process(root->right);
            ans = max(ans, left + right + 1);
            
            return max(left, right) + 1;
        }

    public:
        int diameterOfBinaryTree(TreeNode* root) {
            process(root);

            return ans - 1;
        }
    };

排队最大快乐值

image-20220430094905864

思路及代码

  • 分为两种大情况

    • 当前员工X来：那么下层员工都不能来，那么当前的值为X的快乐值 + 下级不来的最大快乐值
    • 当前员工不X来：那么下层员工可能来，求max(下级不来的最大快乐值, 下级来的最大快乐值)

    image-20220430095333492

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
56
57
58
59
60
61
62
#include <iostream>
#include <vector>

using namespace std;


struct Employee {
    int happy;
    vector<Employee*> nexts;
    Employee(int h) : happy(h){}
};

struct Info {
    int laiMaxHappy;
    int buMaxHappy;
    Info(int lai, int bu):laiMaxHappy(lai), buMaxHappy(bu){}
};

Info* process(Employee* x) {
    // x 是基层员工
    if (x->nexts.empty()) {
        return new Info(x->happy, 0);
    }
    int lai = x->happy;
    int bu = 0;
    for (auto v : x->nexts) {
        Info* nextInfo = process(v);
        lai += nextInfo->buMaxHappy;
        bu += max(nextInfo->buMaxHappy, nextInfo->laiMaxHappy);
    }

    return new Info(lai, bu);
}

int maxHappy(Employee* boss) {
    if(boss == nullptr) {
        return 0;
    }
    Info* headInfo = process(boss);

    return max(headInfo->laiMaxHappy, headInfo->buMaxHappy);    
}

int main() {
    int n, root;
    cin >> n >> root;
    vector<Employee*> all_people;
    all_people.push_back({0});
    int happy_val;
    for(int i = 0; i < n; ++i) {
        cin >> happy_val;
        all_people.push_back(new Employee(happy_val));
    }
    int boss, sub;
    for(int i = 0; i < n - 1; i++) {
        cin >> boss >> sub;
        all_people[boss]->nexts.push_back(all_people[sub]);
    }
    int res = maxHappy(all_people[root]);
    cout << res;
    return 0;
}

Morris遍历

  • 视频：0:39:25-1:37:40

思路及代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Morris(TreeNode* root) {
    if (root == nullptr) return;
    
    TreeNode* cur = root;
    TreeNode* mostRight = nullptr;
    while (cur != nullptr) {
        mostRight = cur->left;
        // 有左子树
        if (mostRight != nullptr) {
            // 找到左子树的最右节点，两种情况
            // 右子树为空或者执行cur
            while(mostRight->right != nullptr && mostRight->right != cur) mostRight = mostRight->right;
            if (mostRight->right == nullptr) {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            } else {
                mostRight->right = nullptr;
            }
        }
        // 没有左子树或者第二次来到cur，cur向右移动
        cur = cur->right;
    }
}

树形DP与Morris

  • 视频：1:37:40-1:40:00
  • 树形DP：必须做第三次信息的强整合
  • Morris：其他情况

大范围数小内存找没出现的数（内存限制1G）——位图

  • 视频：1:44:45-2:05:20

image-20220430102145837

基础：1GB

  • 用整形表示位图，那么一个int为4字节，可以表示32 bit
  • 数的范围为$2^{32} - 1$，那么需要$2^{32}/8$字节大小的空间（申请$2^{32}$bit大小的数组，一个字节表示8位，共需要512M即可）

进阶1：3KB

  • 只有3 KB内存，求一个没出现的数字
  • 首先看，3 KB内存可以支持开多大的整形数组=>3 KB / 4 = 700+，那么最接近的是512（512 * 4字节=2KB）
  • 然后将，范围内的数字分成512份，那么每一份为$2^{32} / 2^9 = 8388608$
  • 此时，数组中的每一位表示某个范围内的数出现的次数，如arr[0]表示0 ~ 8388607出现的次数，依次类推
  • 那么对于40亿中的某个数，落在的范围即x / 8388608，落在哪个位置，就词频++
  • 那么范围为0 ~ 42亿，而数字为40亿个，那么必然有某个范围的数不足 8388608个
  • 找到某个不足量的位置后，然后继续拆分，直到定位到没出现的数字

进阶2：有限几个变量

  • 先对范围二分（0~42亿），因为只有40亿数，所以必然有一边不足$2^{32} / 2$，对不足的一半继续二分

基础提升——二叉树的Morris遍历（P44）

大数据题目解题技巧

image-20220503085948978

大数据范围找重复URL

  • 视频：0:02:35-0:13:45

image-20220503090022098

基础——哈希函数

  • 哈希函数分流：每一个URL算出一个哈希值，然后对m取模，所以一种URL会进一个小文件，然后依次对每个小文件计数，最后汇总
  • 布隆过滤器（存在一定误差）：边添加边查询

补充——二维堆

  • 堆：根据系统配置，分成多个小文件，每个小文件按大根堆组织，然后准备一个总大根堆，里面放每个小文件的top1，然后依次从总大根堆弹出记录，并更新小文件（假设总大根堆的top1为文件3的top1，那么弹出总大根堆的top1且删除文件3的top1，并将文件3的top2加入总堆，依次类推，直到找到top100）

image-20220503090902599

大范围小内存找出现了两次的数

  • 视频：0:13:45-0:36:25

image-20220503091119731

基础：1GB

  • 哈希函数分流：因为会爆内存（一条记录至少8字节，最坏情况，40亿数都不相同，即320亿字节，大约为32G）

  • 位图：用两个位图表示，那么对于$2^{32}$种数，每一个数用两位表示，换算成字节，共需要$2^{32} * 2 / 8$字节，即1G

    1
    2
    3
    4
    5
    6
    /*
    00：表示没出现过
    01：表示出现1次
    10：表示出现2次
    11：表示出现2次以上
    */

进阶：10MB/10KB等——找中位数

  • 看给定的内存能支持开辟多大的无符号整形数组，每一位表示一个范围的词频数量
    • 对于10MB：10MB/4B，最接近的$2^?$为$2^{20}$，即可以开这么大数组，那么数组每一位表示$2^{32}/2^{20}$大小的数，记录累计词频即可
    • 对于10KB：10KB/4B，最接近的$2^?$为$2^{11}$，即可以开这么大数组，那么数组每一位表示$2^{32}/2^{11}$大小的数，记录累计词频即可
  • ==视频中每一位表示的范围说的有点问题，大概这个意思就行==

补充题：无序大文件变有序大文件

  • 视频：0:40:15-1:06:40

  • 有一个无序的10G大文件，每一条记录是一个整数，给定5G内存，要求变成有序文件（保留所有数）

image-20220503092735830

基础：5G内存

  • 堆：使用小根堆，小根堆存放某个数及其出现的次数，并根据数的大小进行组织，而不是出现的次数，那么一条记录占用8字节（可能小根堆组织需要内存，所以可以假设一条记录使用16字节），因为对于5G内存，最多$5GB/16B=2^{28}$条记录，然后将范围等分成$2^{32}/2^{28}=16$份
  • 然后从小范围到大范围依次统计出现的情况，并将其按照数的大小及词频添加到最终文件中

位运算——不使用比较比较大小

  • 视频：1:06:40-1:22:45

image-20220503094101352

思路及代码

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
/*
 * @Author       : 955nice
 * @Date         : 2022-04-06 10:30:42
 * @version      : 1.0
 * @LastEditors  : 955nice
 * @LastEditTime : 2022-04-06 10:40:55
 * @Description  : 有符号32整数，比大小（不能使用比较判断）
 * @FilePath     : /code/job/bit_compare.cpp
 * Talk is cheap, Show me the code
 * @refer        : https://www.bilibili.com/video/BV1YL4y1v7Hy?p=44
 */
#include <iostream>

using namespace std;

// 1 --> 0
// 0 --> 1
int flip(int n) {
    return n ^ 1;
}

// 如果是非负数，返回1
// 如果是负数，返回0
int sign(int n) {
    return flip((n >> 31) & 1);
}

int getMax(int a, int b) {
    // 可能溢出，所以后面做了单独判断
    int c = a - b;
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);
    int diffSab = sa ^ sb;              // a与b符号不一样为1，一样为0
    int sameSab = flip(diffSab);        // a与b符号一样为1，不一样为0
    // 返回A的情况
    // 如果a和b同符号，那么返回a的条件是，a - b ≥ 0
    // 如果a和b不是同符号，那么返回a的条件是，a ≥ 0
    int returnA = sameSab * sc + diffSab * sa;
    int returnB = flip(returnA);

    return a * returnA + b * returnB;
}

int main()
{
    int a = -16, b = -1;
    cout << getMax(a, b) << endl;
    a = 2147483647;
    b = -2147483648;
    cout << getMax(a, b) << endl;
    return 0;
}

位运算——判断是否为2或4的幂次

  • 视频：1:25:55-1:34:15

image-20220503094415811

思路及代码

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
/*
 * @Author       : 955nice
 * @Date         : 2022-04-06 10:48:00
 * @version      : 1.0
 * @LastEditors  : 955nice
 * @LastEditTime : 2022-05-03 09:47:03
 * @Description  : 位运算判断是否为2的幂次，4的幂次
 * @FilePath     : /code/job/bit_power.cpp
 * Talk is cheap, Show me the code
 * @refer        : https://www.bilibili.com/video/BV1YL4y1v7Hy?p=44
 */
#include <iostream>

using namespace std;

// 只有一个1
bool is2Power(int n) {
    return (n & (n - 1)) == 0;
}

// 只有一个1且1出现在偶数位
bool is4Power(int n) {
    return (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}

int main()
{
    int a = 4, b = 8;
    cout << is2Power(a) << endl;
    cout << is4Power(a) << endl;
    cout << is2Power(b) << endl;
    cout << is4Power(b) << endl;
    return 0;
}

位运算——加减乘除

  • 视频：1:34:15-2:18:50

image-20220503094841763

思路及代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
 * @Author       : 955nice
 * @Date         : 2022-04-06 10:06:45
 * @version      : 1.0
 * @LastEditors  : 955nice
 * @LastEditTime : 2022-05-03 10:11:44
 * @Description  : 位运算实现加减乘除
 * @FilePath     : /code/job/bit_ammd.cpp
 * Talk is cheap, Show me the code
 * @refer        : https://www.bilibili.com/video/BV1YL4y1v7Hy?p=44，https://blog.csdn.net/yzt629/article/details/100545654
 */
#include <iostream>

using namespace std;

// 加
// 异或：无进位相加
// 与：左移1位以后表示进位信息
int my_add(int a, int b) {
    int sum = a;
    while (b != 0) {
        sum = a ^ b;
        b = (a & b) << 1;
        a = sum;
    }

    return sum;
}

// 减：a - b = > a + (-b)
// 获得相反数：取反加1
int negNum(int a) {
    return my_add(~a, 1);
}

int my_minus(int a, int b) {
    return my_add(a, negNum(b));
}

// 判断正负
bool isNeg(int n) {
    return n < 0;
}

// 乘
// 小学乘法知识，不过这里只有0和1两位
// 每次取b的最后一位，如果为1，那么应该是加上a左移了某位以后的值
int my_multi(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    //先将被乘数与乘数全部弄为正数
    int x = isNeg(a) ? negNum(a) : a;
    int y = isNeg(b) ? negNum(b) : b;
    int res = 0;
    while (y > 0) {
        //如果最后一位是1，则进行加运算
        if ((y & 1) != 0)
            res = my_add(res, x);
        //无论是否进行了加运算，都将被乘数左移一位，乘数右移一位
        x <<= 1;
        y >>= 1;
    }
    //恢复符号，a^b为负值时表示两者异号，相乘必为负值
    return isNeg(a) ^ isNeg(b) ? my_add(~res, 1) : res;
}

// 除
int my_divide(int a, int b) {
    if (b == 0)
        return -1;
    int x = isNeg(a) ? negNum(a) : a;
    int y = isNeg(b) ? negNum(b) : b;
    int res = 0;
    for (int i = 31; i > -1; i = my_minus(i, 1))
    {
        if ((x >> i) >= y)
        {
            res |= (1 << i);
            x = my_minus(x, y << i);
        }
    }

    return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}

int main()
{
    int a = 7, b = -3;
    cout << my_add(a, b) << endl;
    cout << my_minus(a, b) << endl;
    cout << my_multi(a, b) << endl;
    cout << my_divide(a, b) << endl;
    return 0;
}

基础提升——大数据题目（P45）

机器人左右移动——递归转DP

  • 视频：0:02:45-0:59:50
  • 题意：给定一个数组，表示机器人可以移动的范围，机器人起始位置为S，可以走K步，想要去到E，问有多少种方法

image-20220506091443610

暴力递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int process1(int N, int E, int cur, int rest) {
    if (rest == 0) {
        return cur == E ? 1 : 0;
    }
    if (cur == 1) {
        return process1(N, E, 2, rest - 1);
    }
    if (cur == N) {
        return process1(N, E, N - 1, rest - 1);
    }

    return process1(N, E, cur - 1, rest - 1) + process1(N, E, cur + 1, rest - 1);
}

int walkWays1(int N, int E, int S, int K) {
    return process1(N, E, S, K);
}

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int process2(int N, int E, int cur, int rest, vector<vector<int>>& memo) {
    if (memo[cur][rest] != -1) return memo[cur][rest];

    if (rest == 0) {
        memo[cur][rest] = cur == E ? 1 : 0;
    } else if (cur == 1) {
        memo[cur][rest] = process2(N, E, 2, rest - 1, memo);
    } else if (cur == N) {
        memo[cur][rest] = process2(N, E, N - 1, rest - 1, memo);
    } else {
        memo[cur][rest] = process2(N, E, cur - 1, rest - 1, memo) + process2(N, E, cur + 1, rest - 1, memo);
    }

    return memo[cur][rest];
}

int walkWays2(int N, int E, int S, int K) {
    vector<vector<int>> memo(N + 1, vector<int>(K + 1, -1));
    process2(N, E, S, K, memo);
    return memo[S][K];
}

动态规划

  • 画图来帮助改DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int walkWays3(int N, int E, int S, int K) {
    vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));
    dp[E][0] = 1;
    for (int rest = 1; rest <= K; rest++) {
        for (int cur = 1; cur <= N; cur++) {
            if (cur == 1) {
                dp[cur][rest] = dp[2][rest - 1];
            } else if (cur == N) {
                dp[cur][rest] = dp[N - 1][rest - 1];
            } else {
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
        }
    }

    return dp[S][K];
}

凑零钱（有重复，只能选一次）

  • 视频：1:05:50-2:03:01
  • 题意：给定一个数组，代表硬币的面值（可能有重复，只能选一次），问凑出aim的最少硬币数量，不能凑出，返回-1

image-20220506094352472

暴力递归

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
int process1(vector<int>& nums, int index, int rest) {
    // 不能搞定，返回-1
    if (rest < 0) {
        return -1;
    }
    // 搞定了，只需要0枚硬币
    if (rest == 0) {
        return 0;
    }
    // 如果选到最后一个硬币，还剩余rest，说明没解决
    if (index == nums.size()) {
        return -1;
    }
    int p1 = process1(nums, index + 1, rest - nums[index]);
    int p2 = process1(nums, index + 1, rest);
    if (p1 == -1 && p2 == -1) {
        return -1;
    } else if (p1 != -1) {
        return 1 + p1;
    } else if (p2 != -1) {
        return p2;
    }

    return min(1 + p1, p2);
}

int minCoins1(vector<int>& nums, int aim) {
    return process1(nums, 0, aim);
}

记忆化搜索

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
int process2(vector<int>& nums, int index, int rest, vector<vector<int>>& memo) {
    // 不能搞定，返回-1
    if (rest < 0) {
        return -1;
    }

    // 搞定了，只需要0枚硬币
    if (rest == 0) {
        memo[index][rest] = 0;
        return memo[index][rest];
    }

    if (index == nums.size()) {
        memo[index][rest] = -1;
        return memo[index][rest];
    }
    if (memo[index][rest] != -2) return memo[index][rest];

    int p1 = process1(nums, index + 1, rest - nums[index]);
    int p2 = process1(nums, index + 1, rest);
    if (p1 == -1 && p2 == -1) {
        memo[index][rest] = -1;
    } else if (p1 != -1) {
        memo[index][rest] = 1 + p1;
    } else if (p2 != -1) {
        memo[index][rest] = p2;
    } else {
        memo[index][rest] = min(p1, p2);
    }

    return memo[index][rest];
}

int minCoins2(vector<int>& nums, int aim) {
    vector<vector<int>> memo(nums.size() + 1, vector<int>(aim + 1, -2));
    return process2(nums, 0, aim, memo);
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int minCoins3(vector<int>& nums, int aim) {
    int n = nums.size();
    vector<vector<int>> dp(n + 1, vector<int>(aim + 1, -1));
    for (int index = 0; index <= n; index++) dp[index][0] = 0;
    for (int index = n - 1; index >= 0; index--) {
        for (int rest = 1; rest <= aim; rest++) {
            int p1 = rest - nums[index] < 0 ? -1 : dp[index + 1][rest - nums[index]];
            int p2 = dp[index + 1][rest];
            if (p1 == -1 && p2 == -1) {
                dp[index][rest] = -1;
            } else if (p1 != -1) {
                dp[index][rest] = 1 + p1;
            } else if (p2 != -1) {
                dp[index][rest] = p2;
            } else {
                dp[index][rest] = min(p1, p2);
            }
        }
    }

    return dp[0][aim];
}

基础提升——暴力递归（P46）

先手后手数组取数问题

  • 视频：0:03:15-0:30:00
  • 有一个数组，里面数字全是正数，然后两个人依次从数组拿数（数被拿了就相当于从数组中删除，只能从数组头或者数组尾拿数），问拿出数的最大和

暴力递归

  • 设计两个函数：先手函数和后手函数，分别在$[L, R]$上取数，代码如下
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
int s(vector<int>& arr, int L, int R);

// 先手函数，在L, R上自由选数
int f(vector<int>& arr, int L, int R) {
    // 只有一个数，先手拿完
    if (L == R) return arr[L];

    // 普遍情况
    // 选择拿头或者拿尾，先手拿完后，下一次变成后手
    return max(arr[L] + s(arr, L + 1, R), arr[R] + s(arr, L, R - 1));
}

int s(vector<int>& arr, int L, int R) {
    // 只有一个数，先手拿完了，后手拿不了
    if (L == R) return 0;

    // 普遍情况
    // 先手拿了头，那么只能从[L + 1, R]中拿数
    // 先手拿了尾，那么只能从[L, R - 1]中拿数
    return min(f(arr, L + 1, R), f(arr, L, R - 1));
}

int win(vector<int>& arr) {
    if (arr.empty() || arr.size() < 1) return 0;

    return max(f(arr, 0, arr.size() - 1), s(arr, 0, arr.size() - 1));
}

动态规划

  • 根据暴力递归，f和s函数生成两个表
  • 根据暴力递归主函数调用，确定最终需要的答案
  • 左边界不可能大于右边界，所以两个动态规划表下半部分不需要，然后根据暴力递归画图确定填表路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int winDp(vector<int>& arr) {
    if (arr.empty() || arr.size() < 1) return 0;
    int n = arr.size();
    vector<vector<int>> dpF(n, vector<int>(n));
    vector<vector<int>> dpS(n, vector<int>(n));
    // 把退出条件给填好
    for (int i = 0; i < n; i++) {
        dpF[i][i] = arr[i];
        dpS[i][i] = 0;
    }

    // 一定要画图来确定更新规则
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            dpF[i][j] = max(arr[i] + dpS[i + 1][j], arr[j] + dpS[i][j - 1]);
            dpS[i][j] = min(dpF[i + 1][j], dpF[i][j - 1]);
        }
    }

    return max(dpF[0][n - 1], dpS[0][n - 1]);
}

中级提升班1(P49)

绳子覆盖点问题——滑动窗口

  • 视频：0:02:50-0:16:30

image-20220307085654830

思路及代码

  • 思路1：每个数轴上存在的点作为绳子右端点，二分查找

  • 思路2：每个数轴上存在的点作为绳子左端点，滑动窗口

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // 滑动窗口
    int solution(vector<int>& vec, int lens) {
        int L = 0, R = 0;
        int n = vec.size();
        int ans = -1;
        while (R < n) {
            while (R < n && vec[R] - vec[L] <= lens) R++;
            ans = max(ans, R - L + 1);
            L = R;
            R++;
        }

        return ans;
    }

捆绑交易最少袋子数量——打表优化

  • 视频：0:16:30-0:44:00

image-20220307091430083

思路及代码

  • 提前筛选：奇数通通不行，偶数才继续试

  • 普通思路：先尝试最大的8个袋子数，然后看剩下的苹果是否能被6整除，如果能，找到并返回，如果不能，减少8个袋子数

  • 改进思路：在本题中，考虑到袋子数量是6和8，那么在剩余的苹果数超过24（最小公倍数），提前停止

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int minBagBase6(int rest) {
        return rest % 6 == 0 ? rest / 6 : -1;
    }

    int minBags(int apple) {
        if (apple < 0 || apple & 1) {
            return -1;
        }
        int bag6 = -1;
        int bag8 = apple / 8;
        int rest = apple - bag8 * 8;
        while (bag8 >= 0 && res < 24) {
            int resUse6 = minBagBase6(rest);
            if (resUse6 != -1) {
                bag6 = resUse6;
                break;
            }
            rest = apple - 8 * (--bag8);
        }
        
        return bag6 == -1 ? -1 : bag8 + bag6;
    }

  • 进阶思路：如果输入和输出都是一个数，那么可以通过打表发现规律

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int minBagAwesome(int apple) {
        if ((apple & 1) != 0) {
            return -1;
        }
        if (apple < 18) {
            return apple == 0 ? 0 : (apple == 6 || apple == 8) ? 1 : (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;
        }
        return (apple - 18) / 8 + 3;
    }

补充题：先手后手$4^k$吃草——打表优化

  • 视频：0:44:00-1:10:10

  • 两只动物，先后吃草，没只动物只能吃$4^k,k≥0$数量的草，输入草的数量$N$，问谁赢？（谁先吃完草谁赢）

思路及代码

  • 普通思路：分析普通情况，然后考虑当前的尝试逻辑，先吃1份，看能不能赢，如果不能，尝试吃4份，直到越界或者找到答案

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    string winner1(int n) {
    	if (n < 5) {
            return (n == 0 || n == 2) ? "后手":"先手";
        }    
        // 先手决定吃的草
        int base = 1;
        while (base <= n) {
            // 母过程的先手是子过程的后手
            if (winner1(n - base) == "后手") {
                return "先手";
            }
            if (base > n / 4) {
                break;
            }
            base *= 4;
        }
        return "后手";
    }

  • 打表：通过尝试多个输入，找到规律

    1
    2
    3
    4
    5
    6
    string winner2(int n) {
        if (n % 5 == 0 || n % 5 == 2) {
            return "后手";
        }
        return "先手";
    }

染色的最少次数——预处理(前缀后缀和)

  • 视频：1:10:10-1:28:20

image-20220307094937068

思路及代码

  • 说明：讲的时候可能看错题了，题目要求左R右G，他说的是左G右R，不影响

  • 普通思路：划分为左右两侧，即左侧全为G（如果是R就需要染色），右侧全为R（如果是G就需要染色）

    image-20220307095315301

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int minPaint1(string s) {
        int N = s.size();
        // 枚举左侧部分为L，右侧部分为N-L
        for (int L = 0; L <= N; L++) {
            if (L == 0) {
            	// 统计s[0..N-1]有多少个R    
            }
            if (L == N) {
                // 统计s[0..N-1]有多少个G
            }
            // 统计s[0..L]有多少个G + 统计s[L + 1..N - 1]有多少个R
        }
    }

  • 进阶思路：提前处理s[0..i]上有多少个R(从左往右)，提前处理s[i..N-1]上有多少个G(从右往左)

    image-20220307100007294

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int minPaint2(string s) {
        if (s.size() < 2) return 0;
        int n = s.size();
        // 统计右侧有多少个R
        vector<int> right(n);
        right[n - 1] = s[n - 1] == 'R' ? 1 : 0;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] + (s[i] == 'R' ? 1 : 0);
        }
        int res = right[0];
        // 统计左侧有多少个G
        int left = 0;
        for (int i = 0; i < n - 1; i++) {
            left += s[i] == 'G' ? 1 : 0;
            res = min(res, left + right[i + 1]);
        }
        return min(res, left + (s[n - 1] == 'G' ? 1 : 0))
    }

边框全是1的最大值——预处理

  • 视频：1:30:00-1:55:25

image-20220307100735538

思路及代码

  • 正方形：枚举左上角点开始，边长为1开始尝试，直接碰到边界
  • 从右往左计算当前点右侧包括自己一共有几个连续的1，right矩阵(和原数组等规模)
  • 从下往上计算当前点下侧包括自己一共有几个连续的1，down矩阵(和原数组等规模)

给定随机函数加工出另一个随机函数——位运算

  • 视频：1:55:25-2:06:50

image-20220307102805507

  • 以第一题为例：如果随机函数返回1，2返回0，如果随机函数返回3，4返回1，如果是5重新计算，然后通过位运算（3位就可以，因为三位最大可以表示7）计算出等概率返回0~6即可

中级提升班2,3(P48,P50)

不同二叉树结构——递归转dp

  • 视频：P480:00:30-0:07:26

image-20220308190755532

思路及代码

  • 全局考虑，分左孩子多少种情况，右树多少种情况，最后相乘=>递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int process(int n) {
        if (n < 0) return 0;
        // 空树
        if (n == 0 || n == 1) return 1;
        if (n == 2) return 2;
        int res = 0;
        for (int i = 0; i <= n -1; i++) {
            res += process(i) * process(n - i - 1);
        }
        
        return res;
    }

  • 递归改动规

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int dpWay(int n) {
        if (n < 0) return 0;
        // 空树
        if (n == 0 || n == 1) return 1;
        
        vector<int> dp(n + 1);
        dp[0] = 1;
        // 外层循环表示总节点个数
        for (int i = 1; i < n + 1; i++) {
            // 表示左树节点个数
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        
        return dp[n];
    }

完整括号串需要添加的括号数量——遍历

  • 视频：P480:07:26-0:17:00

image-20220308192558217

思路及代码

  • 两个变量，cnt遇到左括号加一，遇到右括号减一，ans如果cnt再减会变成负数，那么加一
  • 最终结果即为需要的左括号数量（cnt）加需要的右括号数量（ans）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int needParenthess(string str) {
    int cnt = 0;
    int ans = 0;
    for (auto c : str) {
        if (c == '(') {
            cnt++;
        } else {
            if (cnt == 0) {
                ans++;
            } else {
                cnt--;
            }
        }
    }
    return cnt + ans;
}

差值为k的去重数字对——哈希表

  • 视频：P480:17:00-0:21:24

image-20220308193051102

思路及代码

  • 用哈希表将数组中的元素存储，每次查找哈希表中k-arr[i]是否存在，存在即加入答案
1
2
3
4
5
6
7
8
9
10
int getGroups(vector<int>& vec, int k) {
    unordered_set<int> st;
    for (auto v : vec) st.insert(v);
    int ans = 0;
    for (auto v : vec) {
        if (st.count(k - v)) ans++;
    }
    
    return ans;
}

magic操作：两数组平均值——业务分析

  • 视频：P480:21:24-结尾+P500:00:00-0:05:00

image-20220308193847742

思路及代码

  • 分析三种情况
    • 集合A和集合B平均值相等：无法进行操作，返回0
    • 集合A的平均值大于集合B的平均值：只能在平均值大的集合中拿两个集合平均值之间的数
  • 注意：平均值用double存储
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
double avg(double sum, int size) {
    return sum / double(size);
}

int maxOps(vector<int>& arr1, vector<int>& arr2) {
    double sum1 = 0;
    for (auto v : arr1) sum1 += (double)v;
    double sum2 = 0;
    for (auto v : arr2) sum2 += (double)v;
    if (avg(sum1, arr1.size()) == avg(sum2, arr2.size())) {
        return 0;
    }
    vector<int> arrMore;
    vector<int> arrLess;
    double sumMore = 0;
    double sumLess = 0;
    if (avg(sum1, arr1.size()) > avg(sum2, arr2.size())) {
        arrMore = arr1;
        sumMore = sum1;
        arrLess = arr2;
        sumLess = sum2;
    } else {
        arrMore = arr2;
        sumMore = sum2;
        arrLess = arr1;
        sumLess = sum1;
    }
    sort(arrMore.begin(), arrMore.end());
    // 因为要保证移动的元素在平均值较少集合中不存在，所以需要哈希表存储
    unordered_set<int> setLess;
    for (auto v : arrLess) setLess.insert(v);
    int moreSize = arrMore.size();      // 平均值大的集合还剩几个数
    int lessSize = arrLess.size();      // 平均值小的集合还剩几个数
    int ops = 0;
    for (int i = 0; i < arrMore.size(); i++) {
        double cur = (double)arrMore[i];
        if (cur < avg(sumMore, moreSize) && cur > avg(sumLess, lessSize) && !setLess.count(arrMore[i])) {
            sumMore -= cur;
            moreSize--;
            sumLess += cur;
            lessSize++;
            setLess.insert(arrMore[i]);
            ops++;
        }
    }

    return ops;
}

合法括号的深度——dp

  • 视频：P500:05:00-0:26:15

image-20220308200145219

思路及代码

  • 考虑以$i$结尾（包含）的位置

    • 如果为(：设为0
    • 如果为)：那么看前一个位置i-1的结果的再往前一个位置P
      • 如果是(，至少为前一个位置结果+2，并且需要接上p-1位置的答案
      • 如果是)，结果为0

    image-20220308200651585

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxLens(string s) {
    if (s.empty() || s == "") return 0;
    vector<int> dp(s.size(), 0);
    int pre = 0;
    int res = 0;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == ')') {
            pre = i - dp[i - 1] - 1;
            if (pre >= 0 && s[pre] == '(') {
                dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
            }
        } 
        res = max(res, dp[i]);
    }

    return res;
}

使栈中元素升序排序——辅助栈

  • 视频：P500:26:15-0:30:20

image-20220308202023757

思路及代码

  • 准备一个辅助栈，递减栈，两个栈相互倒元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void sortStack(stack<int>& stk) {
    if (stk.empty()) return ;
    stack<int> helper;
    int cur;
    while (!stk.empty()) {
        cur = stk.top();
        stk.pop();
        while (!helper.empty() && cur > helper.top()) {
            stk.push(helper.top());
            helper.pop();
        }
        helper.push(cur);
    }
    while (!helper.empty()) {
        cout << helper.top() << " ";
        stk.push(helper.top());
        helper.pop();
    }
}

数字转字符串个数：递归转dp

  • 视频：P500:30:30-0:46:19

image-20220308203201333

思路及代码

  • 递归：从左往右尝试模型

    • 如果当前位置为0，表示不能匹配，返回0
    • 如果当前位置等于字符串长度，说明找到了一种匹配方式，返回1
    • 普遍位置：下一次递归从index+1开始，如果此时index已经到了最后一位，那么直接返回，如果还有下一位，那么判断是否小于27
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int process(string str, int index) {
        if (str.size() < 1) return 0;

        // 开头为0，不能进行匹配
        if (str[index] == '0') return 0;
        // 遍历到结尾，找到一种可能性
        if (index == str.size()) return 1;
        
        int res = process(str, index + 1);
        // 到了最后一个字符了
        if (index == str.size() - 1) {
            return res;
        }
        if (((str[index] - '0') * 10 + str[index + 1] - '0') < 27) {
            res += process(str, index + 2);
        }

        return res;
    }

  • 递归转dp

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int dpWays(string str) {
        if (str.size() < 1) return 0;
        int n = str.size();
        vector<int> dp(n + 1);
        dp[n] = 1;
        dp[n - 1] = str[n - 1] == '0' ? 0 : 1;
        for (int i = n - 2; i >= 0; i--) {
            if (str[i] == '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1] + (((str[i] - '0') * 10 + str[i + 1] - '0') < 27 ? dp[i + 2] : 0);
            }
            
        }

        return dp[0];
    }

二叉树，根节点到叶结点的最大路径和——二叉树套路

  • 视频：P500:46:19-1:00:45

image-20220308204817149

思路及代码

  • 二叉树套路题，找左右两个孩子要答案
1
2
3
4
5
6
7
8
9
int process(TreeNode* root) {
    if (root->left == nullptr && root->right == nullptr) {
        return root->val;
    }
    int left = root->left ? process(root->left) : 0;
    int right = root->right ? process(root->right) : 0;

    return max(left, right) + root->val;
}

二维矩阵搜索（每行每列升序）——右上角查找

  • 视频：P501:01:15-1:04:45

image-20220308210030745

思路及代码

  • 从右上角开始进行二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int i = 0, j = n - 1;
    while (i < m && j >= 0) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] > target) {
            j--;
        } else {
            i++;
        }
    }

    return false;
}

补充题：求含有连续1最多的行——右上角查找

  • 视频：P501:04:45-1:10:40

  • 每一行数，0一定在1的左边，要求找到1最多的行

思路及代码

  • 从右上角开始，如果是1往左走，如果是0往下一行一走，继续这个套路

image-20220308210355180

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countOne(vector<vector<int>>& arr) {
    if (arr.size() < 1) return 0;
    int res = 0;
    int m = arr.size(), n = arr[0].size();
    int i = 0, j = n - 1;
    while (i < m && j > -1) {
        while (j > -1 && arr[i][j] == 1) j--;
        res = max(res, n - j - 1);
        i++;
    }

    return res;

}

中级提升班4(P51)

洗衣机问题——分析当前位置

  • 视频：0:01:14-0:25:15

image-20220310104728796

思路及代码

  • 考虑当前位置i，那么我可以知道
    • 左侧目前有多少衣服，实际需要多少衣服
    • 右侧目前有多少衣服，实际需要多少衣服
    • 假设需要衣服为负数，扔出衣服为正数
  • 四种情况
    • 总和不能被整除，肯定不符合，返回0
    • 左右两侧都接收衣服（都为负数）：那么肯定是当前位置i往两边扔，由于一次只能扔一件，所以需要abs(left) + abs(right)
    • 左右两侧都扔出衣服（都为正数）：那么只有当前位置i需要接收衣服，接收能力没有限制，所以共需要max(abs(left), abs(right))
    • 一侧扔一侧接收（一正一负）：那么中间需要操作的次数同都为正数的情况，因为可以在接收的同时扔出衣服
  • 那么每个位置最高的瓶颈即为答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int findMinMoves(vector<int>& machines) {
    int n = machines.size();
    int sum = 0;
    for (auto v : machines) sum += v;
    if (sum % n) return -1;

    int avg = sum / n;
    int leftSum = 0;
    int res = 0;
    for (int i = 0; i < n; i++) {
        int leftRest = leftSum - i * avg;
        int rightRest = (sum - leftSum - machines[i]) - (n - i - 1) * avg;
        int ops = 0;
        if (leftRest < 0 && rightRest < 0) {
            res = max(res, abs(leftRest) + abs(rightRest));
        } else {
            res = max(res, max(abs(leftRest), abs(rightRest)));
        }
        leftSum += machines[i];
    }

    return res;
}

螺旋打印矩阵——全局考虑（左上角右下角）

  • 视频：0:26:30-0:33:10

image-20220310111118618

思路及代码

  • 打印左上角和右下角区间内数字，三种情况
    • 只有一列，既打头又打尾
    • 只有一行，既打头又打
    • 普遍情况：先右再下再左再上，打头不打尾
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 {
private:
    vector<int> ans;

    void spiralOrder(vector<vector<int>>& matrix, int tC, int tR, int sC, int sR) {
        int c = tC, r = tR;
        if (tC == sC) {
            // 只有一行
            while (r != sR + 1) ans.push_back(matrix[c][r++]);
        } else if (tR == sR) {
            // 只有一列
            while (c != sC + 1) ans.push_back(matrix[c++][r]);
        } else {
            // 普遍情况
            while (r != sR) ans.push_back(matrix[c][r++]);
            while (c != sC) ans.push_back(matrix[c++][r]);
            while (r != tR) ans.push_back(matrix[c][r--]);
            while (c != tC) ans.push_back(matrix[c--][r]);
        }
    }

public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() < 1 || matrix[0].size() < 1) return {};
        int tC = 0, tR = 0, sC = matrix.size() - 1, sR = matrix[0].size() - 1;
        while (tC <= sC && tR <= sR) {
            spiralOrder(matrix, tC++, tR++, sC--, sR--);
        }

        return ans;
    }
};

矩阵旋转——宏观调度（考虑几个位置）

  • 视频：0:33:10-0:52:20

image-20220310112344747

思路及代码

  • 考虑四个角的位置相互转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        if (matrix.size() < 1 || matrix[0].size() < 1) return ;
        int m = matrix.size(), n = matrix[0].size();
        int a = 0, b = 0, c = m - 1, d = n - 1;
        while (b < d) {
            for (int i = 0; i < d - b; i++) {
                int temp = matrix[a][b + i];
                matrix[a][b + i] = matrix[c - i][b];
                matrix[c - i][b] = matrix[c][d - i];
                matrix[c][d - i] = matrix[a + i][d];
                matrix[a + i][d] = temp;
            }
            a++;
            b++;
            c--;
            d--;
        }
    }
};

zigzag——宏观调度

  • 视频：0:52:24-0:59:40

image-20220310141524427

思路及代码

  • 首先用两个点(A, B)标记起始位置
    • A只往右走，走到不能走了往下走
    • B只往下走，走到不能走了往右走
  • 每次打印两个点之间的内容
  • 用一个变量控制打印顺序（A->B or B->A）
  • 注意：A先查行再查列，B先查列再查行
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
vector<int> ans;

void printMatrix(vector<vector<int>>& arr, int aR, int aC, int bR, int bC, bool order) {
    if (order) {
        while (aR != bR + 1) {
            ans.push_back(arr[aR++][aC--]);
        }
    } else {
        while (bR != aR - 1) {
            ans.push_back(arr[bR--][bC++]);
        }
    }
}

void zigzag(vector<vector<int>>& arr) {
    if (arr.size() < 1 || arr[0].size() < 1) return ;
    int endR = arr.size() - 1, endC = arr[0].size() - 1;
    int aR = 0, aC = 0, bR = 0, bC = 0;
    bool order = false;
    while (aR != endR + 1) {
        printMatrix(arr, aR, aC, bR, bC, order);
        aR = aC == endC ? aR + 1 : aR;
        aC = aC == endC ? aC : aC + 1;
        // 如果下面两句顺序迭代，错误
        bC = bR == endR ? bC + 1 : bC;
        bR = bR == endR ? bR : bR + 1;
        order = !order;
    }
}

最少拼接次数*

  • 视频：1:04:00-1:22:05

image-20220314144955727

字符串数组TopK*

  • 视频：1:22:05-1:31:20

image-20220314145323259

补充题：自定义堆结构——可变的TopK*

  • 视频：1:31:20-2:13:19

image-20220314154029562

中级提升班5(P52)

实现栈：能够返回栈中最小元素*

  • 视频：0:03:05-0:06:30

image-20220314145920919

栈实现队列 & 队列实现栈*

  • 视频：0:06:30-0:15:05

image-20220314150124414

二维数组最小路径和——动态规划空间压缩技巧*

  • 视频：0:15:05-0:36:00

image-20220314150159015

一维接雨水*

  • 视频：0:36:00-0:55:50

image-20220314150344984

最大的左右部分最大值之差的绝对值*

  • 视频：0:55:50-1:03:00

image-20220314150504534

字符串是否互为旋转词*

  • 视频：1:03:00-1:07:15

image-20220314150655015

补充题：咖啡杯问题*

  • 视频：1:07:15-1:49:15

image-20220314151328312

相邻数字是4的倍数*

  • 视频：1:49:15-2:00:50

image-20220314151755070

中级提升班6(P53)

斐波那契数列套题——行列式*

  • 视频：0:01:40-0:39:30

image-20220314152537567

补充题：牛生产问题*

  • 视频：0:39:30-0:47:30
  • 描述：母年一年可以生一只，三年后成熟可以生产，问n年后多少年。假设牛不会死

image-20220314152929324

补充题：兔生产问题*

  • 视频：0:47:30-0:51:30
  • 描述：和上一题差不多，修改一点点。母年一年可以生两只，两年后成熟可以生产，问n年后多少年。兔子五年后会死

image-20220314153435870

符合要求的字符串：出现0的左边必有1*

  • 视频：0:54:10-1:04:20

image-20220314153655738

去掉木棍，使得任意三根不能组成三角形*

  • 视频：1:04:20-1:11:00

image-20220314153903706

背包问题：零食放法*

  • 视频：1:12:00-1:19:00

image-20220314154235741

报酬与能力：找工作*

  • 视频：1:19:00-1:30:40

image-20220314154359610

字符串转日常书写整数*

  • 视频：1:30:40-1:56:20

image-20220314154540315

中级提升班7(P54)

子目录打印问题*

  • 视频：0:01:10-0:20:00

image-20220314154901149

搜索二叉树转有序双向链表*

  • 视频：0:20:30-0:28:10

image-20220314154951850

思路及代码

  • 递归：解决以X为头的整颗树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<Node*> process(Node* node) {
    if (node == nullptr) return {nullptr, nullptr};
    vector<Node*> lNode = process(node->left);
    vector<Node*> rNode = process(node->right);
    if (lNode[1] != nullptr) {
        lNode[1]->right = node;
    }
    node->left = lNode[1];
    node->right = rNode[0];
    if (rNode[0] != nullptr) {
        rNode[0]->left = node;
    }
    
    return {lNode[0] != nullptr ? lNode[0] : node, rNode[1] != nullptr ? rNode[1] : node};
}

最大搜索二叉子树的节点个数*

  • 视频：0:30:50-1:31:20

image-20220314155126826

打分——最长连续子数组和*

  • 视频：1:34:10-1:54:35

image-20220314155310090

最大子矩阵的和*

  • 视频：1:54:35-2:08:00

image-20220314155908701

中级提升班8(P55)

最少路灯数*

  • 视频：0:01:40-0:24:10

image-20220314160107805

前序中序数组生成后序数组*

  • 视频：0:24:10-0:46:35

image-20220314160410899

数字的中/英文表达*

  • 视频：0:46:35-0:58:55

image-20220314161013469

完全二叉树的节点个数*

  • 视频：0:59:15-1:19:45

image-20220314161610108

最长上升子序列*

  • 视频：1:19:45-1:54:00

image-20220314161904107

判断区间内能被3整除的个数*

  • 视频：1:56:00-2:03:35

image-20220314162216413

中级提升班9(P56)

找出未出现在数组中的数

  • 视频：0:01:30-0:09:15

image-20220314162515486

主播晋级*

  • 视频：0:09:25-0:33:35

image-20220314162951582

参与活动的最大奖励*

  • 视频：0:37:50-0:58:40

image-20220314163220340

字符组成达标结果的数量*

  • 视频：1:00:00-1:27:50

image-20220314163700270

没有重复字符的最长子串*

  • 视频：1:28:40-1:36:40

image-20220314164203321

编辑距离问题*

  • 视频：1:40:00-2:01:10

image-20220314164801075

删除多余字符使得字典序最小*

  • 视频：2:02:00-2:14:50

image-20220314165532240

中级提升班10(P57)

字符串排序后的位置*

  • 其他都在9讲过
  • 视频：1:37:20-2:00:00

image-20220314170520383

高级进阶班1(P58)

相邻两数最大差值

  • 视频：0:01:30-0:31:50

image-20220728121201796

思路及代码

  • 假设数组中有N个数，准备N + 1个桶（为了舍弃可能性：最大差值必不可能在同一个桶内）
  • 第一次遍历，找到全局最大值mx和最小值mi
  • 第二次遍历，确定每个桶的最大值，最小值以及桶内是否有数，通过公式$(x - mi) * N / (mx - mi)$得到每个数应该在的桶
  • 第三次遍历，比较相邻桶的差值，找到答案
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
int bucket(int num, int n, int mi, int mx) {
    return (num - mi) * n / (mx - mi);
}

int maxGap(vector<int>& nums) {
    if (nums.size() < 2) return 0;
    int n = nums.size();
    int mx = nums[0], mi = nums[0];
    for (auto v : nums) {
        mx = max(mx, v);
        mi = min(mi, v);
    }
    if (mx == mi) return 0;
    vector<bool> hasNum(n + 1);
    vector<int> maxs(n + 1);
    vector<int> mins(n + 1);
	// 桶号
    int bid = 0;
    for (int i = 0; i < n; i++) {
        bid = bucket(nums[i], n, mi, mx);
        maxs[bid] = hasNum[bid] ? max(maxs[bid], nums[i]) : nums[i];
        mins[bid] = hasNum[bid] ? min(mins[bid], nums[i]) : nums[i];
        hasNum[bid] = true;
    }
    int res = 0;
    int lastMax = maxs[0];
    for (int i = 1; i <= n; i++) {
        if (hasNum[i]) {
            res = max(res, mins[i] - lastMax);
            lastMax = maxs[i];
        }
    }
    
    return res;
}

高级进阶班5（P62）

字符串公式计算

  • 视频：1:02:30-1:04:50

image-20220821123232653

不带括号（只考虑正数）

  • 不带括号，表明不需要考虑额外的优先级，即只有+-*/，因此此部分不处理负数

  • 核心：双端开口栈（deque）

  • 遍历字符串，用一个数字记录当前扫过的数字字符，遇到运算符就考虑入栈，如果栈顶是+-，直接入栈，如果栈顶是*/，弹出计算结果，再入栈

  • 最后计算栈中所有结果

  • 是下面的简化版本，代码略

带括号-递归（包打一切）

  • 带括号，表明需要考虑额外的优先级，包打一切
  • 核心：双端开口栈（deque）
  • 遍历字符串，当还有字符且字符不为)时，考虑三种情况
    • 当前字符是数字字符，累加到num上
    • 当前字符非(，即可能是运算符，或者)时，进行一次结算，即将num和当前字符入deque
    • 当前字符是(，递归去处理后面的情况，并更新此时的num和新下标
    • 最后将num将加入deque
  • 返回此处的结果与下次开始的坐标
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

class Solution {
private:
    void addNum(deque<string>& deq, int num) {
        if (!deq.empty()) {
            int cur = 0;
            string top = deq.back();
            deq.pop_back();
            if (top == "+" || top == "-") {
                deq.push_back(top);
            } else {
                cur = atoi(deq.back().c_str());
                deq.pop_back();
                num = top == "*" ? (cur * num) : (cur / num);
            }
        }
        deq.push_back(to_string(num));
    }

    int getNum(deque<string>& deq) {
        int res = 0;
        bool add = true;
        string cur;
        int num = 0;
        while (!deq.empty()) {
            cur = deq.front();
            deq.pop_front();
            if (cur == "+") {
                add = true;
            } else if (cur == "-") {
                add = false;
            } else {
                num = atoi(cur.c_str());
                res += add ? num : (-num);
            }
        }
        
        return res;
    }
    
    vector<int> process(string& s, int i) {
        int n = s.size();
        deque<string> deq;
        int num = 0;
        vector<int> cur;
        while (i < n && s[i] != ')') {
            if (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + (s[i++] - '0');
            } else if (s[i] != '(') {
                addNum(deq, num);
                deq.push_back(string(1, s[i++]));
                num = 0;
            } else {
                cur = process(s, i + 1);
                num = cur[0];
                i = cur[1] + 1;
            }
        }
        addNum(deq, num);
        
        return vector<int>{getNum(deq), i};
    }
    
public:
    int calculate(string s) {
        // 处理字符串中有多余空格的情况
        string need = "";
        for (auto& v : s) {
            if (v == ' ') continue;
            need += v;
        }
        return process(need, 0)[0];
    }
};

带括号-迭代（未考虑乘除）

  • 力扣评论区优秀的解法
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
class Solution {
public:
    int calculate(string s) {
        stack<int> stk;
        // sign表示正负
        int sign = 1, res = 0;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            char ch = s[i];
            if (isdigit(ch)) {
                long cur = ch - '0';
                while (i + 1 < n && isdigit(s[i + 1])) {
                    // 可能越界："2147483647"
                    cur = cur * 10 + s[++i] - '0';
                }
                res += sign * cur;
            } else if (ch == '+') {
                sign = 1;
            } else if (ch == '-') {
                sign = -1;
            } else if (ch == '(') {
                stk.push(res);
                res = 0;
                stk.push(sign);
                sign = 1;
            } else if (ch == ')') {
                int a = stk.top(); stk.pop();
                int b = stk.top(); stk.pop();
                res = a * res + b;
            }
        }

        return res;
    }
};

高级进阶班11(P68)

完美洗牌问题，{L1, L2, …Ln, R1. R2,…Rn}=>{R1,L1,R2,L2,…Rn,Ln}

  • 视频：0:29:00-1:04:50

image-20220305171212847

  • 要求时间复杂度$O(nlog_3n)$和空间复杂度$O(1)$

思路及代码

  • 假设下标从1开始，数组长度为$2n$，那么位于左半区的$i$位置最终要去的位置为$2i$，位于右半区的$i$位置最终要去的位置为$(i-n)*2-1$

  • 不同圈

    image-20220305172311673

  • 利用完美洗牌问题结论：当整个数组长度$M$满足$M=3^k-1，k≥1$时，不同圈的出发位置为$[1,3,9,3^{k-1}]$

  • 补充：为什么需要进行三次逆序？实现实际长度不等于$3^k-1$的数组，即先解决最接近$3^k-1$的子数组（左右部分平移逆序，时间复杂度O(k)，k为数组长度，空间复杂度O(1)）

    image-20220511100907824

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 数组总长度len，调整前位置为i，返回调整后的位置
int modifyIndex(int i, int len) {
    int n = len / 2;
    if (i <= n) {
        return 2 * i;
    }

    return 2 * (i -n) - 1;
}

// 从start位置开始，往右len的长度这一段，做下标连续推
// 出发位置一次为1,3,9...
void cycles(vector<int>& arr, int start, int len, int k) {
    // 找到每一个出发位置trigger，一共k个
    // 每一个trigger都进行下标连续推
    // 出发位置是从1开始算的,而数组下标是从0开始算的
    for (int i = 0, trigger = 1; i < k; i++, trigger *= 3) {
        int preValue = arr[trigger + start - 1];
        int cur = modifyIndex(trigger, len);
        while (cur != trigger) {
            int tmp = arr[cur + start - 1];
            arr[cur + start - 1] = preValue;
            preValue = tmp;
            cur = modifyIndex(cur, len);
        }
        arr[cur + start - 1] = preValue;
    }
}

// [L..R]做逆序调整
void myReverse(vector<int>& arr, int L, int R) {
    while (L < R) {
        int tmp = arr[L];
        arr[L++] = arr[R];
        arr[R--] = tmp;
    }
}

// [L..M]为左部分，[M+1..R]为右部分，左右两部分互换
void rotate(vector<int>& arr, int L, int M, int R) {
    myReverse(arr, L, M);
    myReverse(arr, M + 1, R);
    myReverse(arr, L, R);
}

// 在arr[L...R]上做完美洗牌问题
void shuffle(vector<int>& arr, int L, int R) {
    // 切成一块一块的解决，每一块的长度满足(3^k - 1)
    while (R - L + 1 > 0) {
        int len = R - L + 1;
        int base = 3;
        int k = 1;
        // 计算小于等于k且满足(3^k - 1)的数
        // 也就是找最大的k，满足3^k <= len + 1
        while (base <= (len + 1) / 3) {
            base *= 3;
            k++;
        }
        // 当前要解决长度为base-1的块，一半就是再除以2
        int half = (base - 1) / 2;
        // [L...R]中点位置
        int mid = (L + R) / 2;
        // 要旋转的左半部分为[L+half...mid]
        // 要旋转的右半部分为[mid+1...mid+half]
        // 注意此处下标从0开始
        rotate(arr, L + half, mid, mid + half);
        // 旋转完成后。从L开始算起，长度为base-1的部分进行下标连续推
        cycles(arr, L, base - 1, k);
        // 解决了前base-1部分，剩下的部分继续处理
        L = L + base - 1;
    }
}

// 完美洗牌问题主函数
// 数组不为空，且必须是偶数
// [a1, a2, a3, a4, a5, b1, b2, b3, b4, b5] => [a1, a2, a3, a4, b1, b2, b3, b4, a5, b5] => ... =>[b1, a1, b2, a2, b3, a3, b4, a4, b5, a5]
void shuffle(vector<int>& arr) {
    if (arr.size() != 0 && (arr.size() & 1) == 0) {
        shuffle(arr, 0, arr.size() - 1);
    }
}

扩展

给定一个数组，要求调整之后数组相邻元素满足：<=，>=，<=一直下去

image-20220511101104959

  • 思路：使用堆排进行排序（时间足够快，空间复杂度小）

    • 长度为偶数，然后使用完美洗牌算法进行排序即可

      image-20220511101510146

    • 长度为奇数，剔除第一个（排序之后最小的数）

      image-20220511101638318

最大线段重叠问题

  • 视频：1:31:40-1:57:55
  • 有个二维数组，每一个位置代表一个线段的起始和结尾位置，求最大重叠的线段数量（压点不算，即[1,2]，[2,3]结果是1），如{ {2, 5},{1, 9},{3, 10},{6, 8},{2, 4} }最长重叠包含的线段有四条（除了6,8）

image-20220727124128515

思路及代码

  • 以起点升序排序
  • 有序表存当前位置结尾（删除不符合要求的数据）
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
56
57
58
59
60
/*
 * @Author       : 955nice
 * @Date         : 2022-07-27 12:30:00
 * @version      : 1.0
 * @LastEditors  : 955nice
 * @LastEditTime : 2022-07-27 12:30:00
 * @Description  : 线段重叠的最多线段树
 * @FilePath     : /code/job/bitmap.cpp
 * Talk is cheap, Show me the code
 * @refer        : https://blog.csdn.net/no_O_ac/article/details/103174451, https://www.cnblogs.com/fnlingnzb-learner/p/9300073.html
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int maxOverlap(vector<vector<int>>& nums) {
    sort(nums.begin(), nums.end(), [](vector<int>& a, vector<int>& b) {
        return a[0] < b[0];
    });
    int res = 0;
    set<int> st;
    // 枚举以某个点为开头，重叠的线段数量
    for (auto& vec : nums) {
        int start = vec[0];
        int end = vec[1];
        // 删除会使当前元素迭代器失效，不能使用直接删除
        // for (auto v : st) {
        //     if (v >= start) break;
        //     st.erase(v);
        // }
        for (auto iter = st.begin(); iter != st.end();) {
            if (*iter >= start) break;
            // 两种方法都可以
            // iter = st.erase(iter);
            st.erase(iter++);
        }
        
        st.insert(end);
        int cur = st.size();
        res = max(res, cur);
    }

    return res;
}

int main()
{
    vector<vector<int>> nums = {
        {2, 5},
        {1, 9},
        {3, 10},
        {6, 8},
        {2, 4}
    };
    cout << maxOverlap(nums) << endl;;
    return 0;
}

扩展：最大矩形重叠问题*

  • 线段问题扩展为矩形重叠问题
  • 思路

    1. 将每一个矩形，根据底边升序排序

    2. 先处理在下方的矩形，准备一个容器，如果当前遍历到的矩形X的底边，没有超过容器中最高矩形的顶边，加入=>换句话说，删除所有顶边低于当前X的矩形，求此次答案

      • ABCD时，如下

        image-20220727125010461

      • 加入E后，如下

        image-20220727125034212

    3. 变换成线段重叠问题求解