1 动态规划

从背包问题开始：

• https://zhuanlan.zhihu.com/p/93857890
  区间dp等等：
• https://oi-wiki.org/dp/interval/

最重要的是，能够用dp数组，1到3维度一般，去表示最终结果，对于具体的题目，dp[i][j]表示什么意思，将成为解答的关键

很多动态规划都可以使用带记忆化的搜索去做

2 例题

0410splitArrayMinMax 分割出最小的子数组最大值

1 题目

https://leetcode-cn.com/problems/split-array-largest-sum/

2 解题思路

参考官方解答：https://leetcode-cn.com/problems/split-array-largest-sum/solution/fen-ge-shu-zu-de-zui-da-zhi-by-leetcode-solution/

• 1 dp: 首先搞明白动态规划的单元，注意，不仅仅是说增加一个元素，对分割造成了什么影响，而且还要考虑，不通的分割数目，本题目是分割，那么一定是分割数目以及分割对象带来的变化为dp的状态迁移， dp[i][j] means: res of: nums[:i] to be splited in j’s segments, dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1}，所以
• 2 二分查找法：这样，判断一个数字能否作为分割m个子数组的方案？应该很好判断，顺序遍历即可
  • 2.1 那么记录该数字为x，最小就是数组里的最大值，最大即为数组和，于是仅仅需要用二分法，从这个范围中找出该数字即可
  • 2.2 具体如何二分？若x过于小了，会导致分割数目太大，然后我们就知道往大处搜索，反之同理
• 3 二分法的标准写法：
  • 3.1 注意用>>代表除2，尤其是考虑负数时候有区别
  • 3.2 注意当往大地方搜，st = mid+1，往小地方则不用，不然可能导致ed漏搜索

    1 2 3 4 5 6 7 8 9 10 11 12 13

    bool lastCheck = false; while(st < ed) { x = (st + ed) >> 1; // means: floor of (st + ed) lastCheck = xIsLarge(x, nums, m); if(lastCheck) { ed = x; // when ed - st = 1, (st + ed) >> 1 == st } else { st = x + 1; } } return st;

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

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<int> preSum = { 0 };
        for(int i = 0; i < n; ++i) {
            preSum.push_back(preSum.back() + nums[i]);
        }
        // // dp[i][j] means: res of: nums[:i] to be splited in j's segments
        // // dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1}
        // vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MAX));
        
        // dp[1][1] = nums[0];
        // for(int i = 1; i <= n; ++i) {
        //     for(int j = 1; j <= min(m, i); ++j) {
        //         if(j == 1) {
        //             dp[i][1] = preSum[i] - preSum[0];
        //             continue;
        //         }
        //         int tmpMaxMin = 0;
        //         for(int k = j - 1; k < i; ++k) {
        //             tmpMaxMin = max(dp[k][j-1], preSum[i] - preSum[k]);
        //             dp[i][j] = min(dp[i][j], tmpMaxMin);
        //         }
        //     }
        // }
        // return dp[n][m];
        
        // binsearch x as the min max res
        int st = *max_element(nums.begin(), nums.end());
        int ed = preSum[n];
        int x = -1;


        bool lastCheck = false;
        while(st < ed) {
            x = (st + ed) >> 1;
            lastCheck = xIsLarge(x, nums, m);
            if(lastCheck) {
                ed = x; // when ed - st = 1, (st + ed) >> 1 == st
            } else {
                st = x + 1;
            }
        }
        
        // at last, st == ed
        return st;
    }

    bool xIsLarge(int x, vector<int>& nums, int m) {
        int cnt = 1;
        int curSum = 0;
        for(int i = 0; i < nums.size(); ++i) {
            if(curSum + nums[i] > x)  {
                ++cnt;
                curSum = nums[i];
            } else {
                curSum += nums[i];
            }
        }
        // cout << ">> x/cnt is" << x << "/" << cnt << endl;
        return cnt <= m;
    }
};

0403frogCrossRiver 青蛙过河

1 题目

https://leetcode-cn.com/problems/frog-jump/

2 解题思路

• 1 动态规划：首先明白动态规划最终是指向结果的，于是，定义dp[i][k]，为到达i的最后一跳长度为k，是否能够跳到目的地
  • 1.1 首先有疑问：那k岂不是max(stone) - min(stone)，那k就会非常大，不合理啊？错，因为每一跳长度最多增加1，然而你最多有n-1跳，于是 k <= n-1
  • 1.2 状态转移: dp[i][k] = dp[j][k] || dp[j][k-1] || dp[j][k+1]，j就是i的上一跳，那么我们可以直到，j到i，k=stone[i] - stone[j]
  • 1.3 需要注意到上面的状态转移: 因为是从j跳，必须保证: k <= j+1，因为你从第j个石头开始跳，最远长度就是j+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

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        // jump to i, and last jump dis
        vector<vector<bool>> jump(n , vector<bool>(n, false));
        jump[0][0] = true;

        // the i th jump len <= i
        for(int i = 1; i < n; ++i) {
            if(stones[i] - stones[i - 1] > i) {
                return false;
            }
        }

        // dp, from j jump to i
        bool res = false;
        for(int i = 1; i < n; ++i) {
            for(int j = 0; j < i; ++j) {
                int k = stones[i] - stones[j];
                // cout << j << " -> " << i << " 's dis: " << k << endl;
                if(k > j + 1) {
                    continue;
                }
                // cout << jump[j].size() << " / " << k + 1 << " jump[j][k] || jump[j][k-1] || jump[j][k+1] " << jump[j][k] << jump[j][k-1] << jump[j][k+1] << endl;
                jump[i][k] = jump[j][k] || jump[j][k-1] || jump[j][k+1];
                if(i == n - 1 && jump[i][k]) {
                    res = true;
                }
            }
        }
        return res;
    }
};

0488zumaGame 祖玛游戏

1 题目

https://leetcode-cn.com/problems/zuma-game/

2 解题思路

• 1 对于hand中，每次挑选一个去填补到board中，然后消除board中的球，接着用剩下的hand再选择一个，到board里中去消除，dfs去遍历即可
• 2 使用记忆化搜索 memo[board + “ “ + hand]记录了对应的board和hand的结果，为何” “是必须的？
  • 2.1 考虑以下例子：
  • 2.2 可以知道必须在中间的RR中先插入B，那么假设我们的第一次搜索从第一个字符G，第二个字符是B，开始，那么我们的memo中会有结果(若是不带空格)：memo[RRYGGYYRBRYYGGYRRGGBB]，这样当第一个字符变成B，我们会在memo发现一个失败的方法直接返回结果，导致改题变成没有结果，同时这个例子也解释了为何减枝的条件3需要在两个相同字符之间插入字符，如果带了空格，就能够绝对避免这个问题，因为：
  • memo[RRYGGYYRBRYYGGYRR GGB] 和 memo[RRYGGYYRBRYYGGYRR GGBB]就能够区分开

    “RRYGGYYRRYYGGYRR”
    
    “GGBBB”

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

class Solution {
public:
    int allBallsCnt = -1;
    map<string, int> memo;

    int findMinStep(string board, string hand) {
        // simulate this game
        int res = 0;
        allBallsCnt = hand.size();
        res = bfs(board, hand);
        return res == INT_MAX ? -1 : res;
    }
    int bfs(string board, string hand) {
        // space mustn't be eliminated! it's neutig!
        if(memo.find(board + " " + hand) != memo.end()) {
            return memo[board + " " + hand];
        }

        if(0 == board.size()) {
            return allBallsCnt - hand.size();
        }
        if(0 == hand.size()) {
            return INT_MAX;
        }

        int useRes = INT_MAX;
        string lastTarBallStr = "";
        for(int k = 0; k < hand.size(); ++k) {
            string nextHand = hand.substr(0, k) + hand.substr(k + 1);
            string tarBallStr = hand.substr(k, 1);

            // case1: cut the same ball
            if(tarBallStr == lastTarBallStr) {
                continue;
            }

            // use this char, find put pos
            for(int i = 0; i <= board.size(); ++i) {
                // case2: only insert at the start of str with same chars
                if(i > 0 && board[i - 1] == hand[k]) {
                    continue;
                }

                // case3: only put when cur is equal current || when cur is not equal to two continuous same chars
                if(i < board.size() && board[i] == hand[k] || \
                i > 0 && board[i] == board[i-1] && hand[k] != board[i-1]) {
                    string tmpBoard1 = board;
                    tmpBoard1.insert(i, tarBallStr);
                    // reduce repeat balls
                    reduceRepeat(tmpBoard1);

                    // put to tarBall left and right
                    int lRes = bfs(tmpBoard1, nextHand);

                    useRes = min(lRes, useRes);
                }
            }
            
            lastTarBallStr = tarBallStr;
        }
        memo[board + " " + hand] = useRes;
        return useRes;
    }

    inline void reduceRepeat(string& board) {
        int idx = 0;
        // cout << "reducing " << board << endl;
        while(board.length() > 0 && idx < board.length()) {
            int st = idx, cur = st;
            char head = board[st];
            while(++cur < board.length() && board[cur] == head) {
            }
            if(cur - st >= 3) {
                board.erase(st, cur - st);
                idx = 0;
            } else {
                idx = cur;
            }
        }
        // cout << "after redu " << board << endl;
    }

};

0552checkRecord 学生出勤记录

1 题目

https://leetcode-cn.com/problems/student-attendance-record-ii/

2 解题思路

• 1 初步思路 dp[i][j]作为直到i天，以j为出勤记录的所有记录数，但是会发现无法处理连续的L的情况
• 2 更改，采用官方题解思路： dp[i][j]为以连续j个l为结尾的记录数，首先只考虑PL，但是此方法不行，因为，A可以隔断两个L，所以，如果先算出所有PL的方法，然后将A插入，那么结果一定会比用A去隔断两个L少。
• 3 官方接单： dp[i][j][k]是含有j个A的k个L为结尾的记录数

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

class Solution {
public:

    int bigInt = 1000000007;
    int checkRecord(int n) {
        if(n <= 2) {
            return n == 1 ? 3 : 8;
        }
        
        // we can use A to interrupt the LLL, so we calculate A after only PL
        // // n's day without 'A'
        // vector<vector<long long>> dp(n + 1, vector<long long>(3, 0));
        
        // // dp[i][j], j means end with n's L
        // dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0;


        // for(int i = 2; i <= n; ++i) {
        //     // end with p
        //     dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
            
        //     // ent with l
        //     dp[i][1] = (dp[i - 1][0]) % bigInt;

        //     // end with ll
        //     dp[i][2] = dp[i - 1][1] % bigInt;
        //     cout << i << " th: P/L: " << dp[i][1] << " " << dp[i][0] << endl;
        // }

        // // when there is a A:
        // long long res = 0;
        // res += ((dp[n][0] + dp[n][1]) % bigInt + dp[n][2]) % bigInt;
        // res += (((dp[n-1][0] + dp[n-1][1]) % bigInt + dp[n-1][2]) % bigInt * n) % bigInt;
       

        // n's day without 'A'
        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(2, vector<long long>(3, 0)));
        
        // dp[i][j], j means end with n's L
        dp[0][0][0] = 1;

        for(int i = 1; i <= n; ++i) {
            // end with p
            for(int j = 0; j < 2; ++j) {
                for(int k = 0; k <= 2; ++k) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % bigInt;
                }
            }

            // end with a
            for(int k = 0; k <= 2; ++k) {
                dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][k]) % bigInt;
            }
            
            // ent with l
            for(int j = 0; j < 2; ++j) {
                for(int k = 1; k <= 2; ++k) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k-1]) % bigInt;
                }
            }
        }

        int res = 0;

        for(int j = 0; j < 2; ++j) {
            for(int k = 0; k < 3; ++k) {
                res = (res + dp[n][j][k]) % bigInt;
            }
        }


        return res;
    }
};

0600countUncontinous1 不含连续1的非负整数

1 题目

https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/

2 解题思路

• 1 解题思路：
  • 1.1 很显然的动态规划，首先考虑问题： 给你一个二进制数字a = 2^n，判断从0到a有多少个数字不含有连续的两个1？动态规划即可：
    • dp[len][0] = dp[len - 1][1] + dp[len - 1][0];
    • dp[len][1] = dp[len - 1][0];
    • 其中dp[len][0]表示长度为len然后以0开始的二进制数字的集合中，含有多少个不连续为1的数字
  • 1.2 有了上述的思考，那么对于1024，32这种数字的解答就很显而易见了，比如32 = 100000，那么答案就是：首先假设最高位为0，然后res += dp[5][0] + dp[5][1]，这是所有： 0xxxx和1xxxx组成的答案，但是32是6位数字，还需要加上32本身即可
  • 1.3 更近一步，对于a = 101010 和 b = 110000 这样的呢？
    • 以每一个1对结果的贡献来思考，从高位到低位这样去思考：
    • 首先拿a来说，我们看最高位，和32一样的解法，接下来我们找到下一个1，那么就是变成，找以前缀为10，后缀为 0xxx 的有多少种，那么动态规划直接找出来就行，那么为什么不是1xxx，因为1xxx加上前缀10可能就大于a了，就超出了范围，那么我们接着找到下一个1，也就是前缀为1010，找0x有多少种，然后最后找不到1，看看a本身是否合理加上即可
    • 对于b，首先第一个1对最终结果的贡献都是和32一样的，那么第二个1呢？很显然，遇到了连续的第二个1，意味着后面的1对答案都不会有贡献，因为以11为前缀的都是不合法的，所以仅仅需要考虑，将第二个连续的1变成0，以10为前缀，xxxx有多少中方案，很简单，就是 dp[4][0] + dp[4][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
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

class Solution {
public:
    int findIntegers(int n) {
        int tmp = n;
        int bit = -1;
        vector<int> bits = {};

        while(tmp > 0) {
            bits.push_back(tmp & 1);
            tmp = tmp >> 1;
        }

        int k = bits.size();
        vector<vector<int>> dp(k, vector<int>(2, 0));

        if(k <= 1) {
            return 2;
        }

        dp[0][0] = 1; // mainly for the last bit is 1
        dp[0][1] = 0;

        dp[1][0] = 1;
        dp[1][1] = 1;

        for(int len = 2; len <= k - 1; ++len){
            dp[len][0] = dp[len - 1][1] + dp[len - 1][0];
            dp[len][1] = dp[len - 1][0];
            // cout << "dp " << len << "/0,1 = " << dp[len][0] << "," << dp[len][1] << endl;
        }

        int lastOneBitIdx = k - 1;

        // assume the biggest bit starts with 0
        int res = dp[lastOneBitIdx][0] + dp[lastOneBitIdx][1];
        // cout << "assume biggest bit = 0's res : " << res << endl;

        bool mySelfOk = true;
        while(lastOneBitIdx > 0) {
            int nextOneBitIdx = lastOneBitIdx - 1;
            cout << ">> last/next: " << lastOneBitIdx << "/" << nextOneBitIdx << endl;
            cout << "bits[next] " << bits[nextOneBitIdx] << endl;

            // find next one bit
            while(bits[nextOneBitIdx] != 1) {
                cout << "not 1 bit: " << nextOneBitIdx << endl;
                -- nextOneBitIdx;
                if(nextOneBitIdx == -1) {
                    return res + mySelfOk;
                }
            }

            cout << "last/next: " << lastOneBitIdx << "/" << nextOneBitIdx << endl;
            if(lastOneBitIdx - nextOneBitIdx < 2) {
                // view the bits[nextOneBitIdx] as 0
                res += dp[nextOneBitIdx][0] + dp[nextOneBitIdx][1];
                mySelfOk = false;
 
                // cout << "+ dp " << nextOneBitIdx << "," << 0 << " break!!!" << endl;
                break;
            } else {
                // view the bits[nextOneBitIdx] as 0
                res += dp[nextOneBitIdx][0] + dp[nextOneBitIdx][1];
                lastOneBitIdx = nextOneBitIdx;
                // cout << "+ dp " << nextOneBitIdx << "," << 0 << endl;
                // cout << "lastOneBitIdx is " << lastOneBitIdx << endl;
                // cout << "curRes = " << res;

            }
        }

        cout << "me ok: " << mySelfOk << endl;

        return res + mySelfOk;
    }
};

1 欧拉图基本概念：

圈：任选图中一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径称为圈。

欧拉路径：通过图中所有边一次且仅一次遍历所有顶点的路径称为欧拉(Euler)路径；

欧拉回路：通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路；

欧拉图：具有欧拉回路的图称为欧拉图；

半欧拉图：有欧拉路径但没有欧拉回路的图称为半欧拉图。

欧拉图与半欧拉图的判定：

G是欧拉图 ⇔ G中所有顶点的度均为偶数 ⇔ G是若干个边不重的圈的并。

G是半欧拉图 ⇔ G中恰有两个奇数度顶点。

• 2 hierholzer算法

  • 2.1 dfs，当一个节点没邻居了
  • 2.2 将节点入栈reversePath
  • 2.3 dfs完成，reversePath则为逆序栈

• 3 例子：
  

从0开始的话，那么
访问栈为：0 -> 1 -> 2 -> 0, 此时reversePath可以将访问栈里的0弹出加入，则reversePath = [0, 2]
此时访问栈为： 0-> 1 ，接着访问3，4,然后弹出4，3，1，0
则 reversPath = [0,2,4,3,1,0]，然后逆序则为：
0 1 3 4 2 0，为目标的eular path

2 一句话总结hierhozer算法: dfs后续遍历节点的逆序为eular路径

1 深度优先遍历

最常见的优化：

• 1 记忆化搜索： 使用hash记录遍历起点对应的值，然后直接从hash中获得，避免重复计算

• 2 常见算法：
  对于欧拉图和半欧拉图算欧拉路径：hierholzer算法

2 例子

0332HierholzerToFindEulerPath 找欧拉路径

1 题目

https://leetcode-cn.com/problems/reconstruct-itinerary/

2 解题思路

hierholzer算法参考：https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/
https://blog.csdn.net/qq_34292517/article/details/105463522?utm_medium=distribute.pc_relevant.none-task-blog-2defaultbaidujs_title~default-0.pc_relevant_default&spm=1001.2101.3001.4242.1&utm_relevant_index=3

• 1 自己的思路：
  • 1.1 主要是使用hierholzer算法找到欧拉路径，由于需要字典序，那么我们邻接表则使用优先队列来存储
• 2 hierholzer算法
  • 2.1 dfs，当一个节点没邻居了(因为每访问一条边就删除一条边)
  • 2.2 将节点入栈reversePath
  • 2.3 dfs完成，reversePath则为逆序栈
• 3 欧拉图等等理解：参考上述第二篇文章

  基本概念

圈：任选图中一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径称为圈。

欧拉路径：通过图中所有边一次且仅一次遍历所有顶点的路径称为欧拉(Euler)路径；

欧拉回路：通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路；

欧拉图：具有欧拉回路的图称为欧拉图；

半欧拉图：有欧拉路径但没有欧拉回路的图称为半欧拉图。

欧拉图与半欧拉图的判定：

G是欧拉图 ⇔ G中所有顶点的度均为偶数 ⇔ G是若干个边不重的圈的并。

G是半欧拉图 ⇔ G中恰有两个奇数度顶点。

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

class Solution {
public:
    
    int edgeNums = -1;
    int nodeNums = -1;
    unordered_map<string, int> nodes;
    unordered_map<int, string> toStr;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        // map str to int according to dictionary order
        set<string, std::less<string>> airports;
        for(auto& vec : tickets) {
            airports.insert(vec[0]);
            airports.insert(vec[1]);
        }

        int i = 0;
        for(auto& str : airports) {
            toStr[i] = str;
            nodes[str] = i++;
        }
        
        // construct the adj table
        int nodeNums = airports.size();
        int edgeNums = tickets.size();
        // vector<vector<int>> table(nodeNums, vector<int>(0));
        vector<priority_queue<int, vector<int>, greater<int>>> table(nodeNums, priority_queue<int, vector<int>, greater<int>>());
        for(auto& vec : tickets) {
            table[nodes[vec[0]]].push(nodes[vec[1]]);
        }

        vector<string> strRes;
        vector<priority_queue<int, vector<int>, greater<int>>> tableTmp(table);
        vector<int> res;
        dfs(nodes["JFK"], tableTmp, res);
        reverse(res.begin(), res.end());
        for(auto& node : res) {
            strRes.push_back(toStr[node]);
        }

        return strRes;
    }

    // 
    void dfs(int st, vector<priority_queue<int, vector<int>, greater<int>>>& map, vector<int>& res) {
        
        while(!map[st].empty()) {
            int nextSt = map[st].top();
            map[st].pop();
            // cout << "from to: " << toStr[st] << " -> " << toStr[nextSt] << endl;
            dfs(nextSt, map, res);
        }
        res.emplace_back(st);
    }
};

0753crackSafe 破解保险箱(变形欧拉路)

1 题目

https://leetcode-cn.com/problems/freedom-trail/
https://leetcode-cn.com/problems/reconstruct-itinerary/

2 解题思路

• 1 对于 n = 3, k = 3, 我们的图的节点为(k ^ (n-1)个)： 00, 01, …, 22, 然后每个节点都有k个边，这样一共是k^n个边
  • 1.1 那么如何认为走过一条边就是尝试一次密码呢？
  • 1.2 比如: 00的邻接顶点为0,1,2, 那么当dfs访问从00节点到其邻接点分别组成的边为000，001，002，则他们对应的下一跳就为: 00,01,02，也就是取当前dfs访问得到的边的后n-1位
• 2 hierholzer算法
  • 2.0 选择一个节点开始dfs
  • 2.1 当一个节点没邻居了
  • 2.2 将节点入栈reversePath
  • 2.3 dfs完成，reversePath则为逆序栈

    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

    class Solution { public: int n = -1; int k = -1; vector<char> kVec; string crackSafe(int n, int k) { // since for each bit, there a k's possiblity // so the final str's length = k^n // consider a G, vertices are {0, 1, ..., k-1} // for each edge: vi -> vj(vi could equal vj), // there shall be n-1's such same edge // we just need a way to walk through the G // try hierholzer algo if(1 == n) { string tmpRes = ""; for(int i = 0; i < k; ++i) { tmpRes.push_back(i + '0'); } return tmpRes; } this->k = k; this->n = n; for(int i = 0; i < k; ++i) { kVec.push_back(i + '0'); } unordered_set<string> seen; unordered_map<string, vector<char>> graph; buildGraph("", n - 1, graph); string stStr(n-1, '0'); string res = ""; hierholzer(stStr, graph, res, seen); // when n=3, k=3, we start from "00" node, so we add reverse of "00" to the end of the res, cause hierholzer produce a reverse eular path (start from "00", end to "00") res += stStr; return res; } void buildGraph(string tmp, int leftBitNum, unordered_map<string, vector<char>>& graph) { if(0 == leftBitNum) { // cout << "len: " << leftBitNum << "finish node: " << tmp << endl; graph[tmp] = kVec; return; } for(int st = 0; st < k; ++st) { buildGraph(tmp + kVec[st], leftBitNum-1, graph); } } void hierholzer( string st, unordered_map<string, vector<char>>& graph, string& res, unordered_set<string>& seen) { // cout << "doing : " << st << endl; bool hasOut = false; for(int edIdx = 0; edIdx < k; ++edIdx) { string curEdge(st); curEdge.push_back(graph[st][edIdx]); if(seen.count(curEdge)) { continue; } hasOut = true; string nextSt = curEdge.substr(1); // cout << "st -> nextSt: " << st << " -> " << nextSt << endl; seen.insert(curEdge); // cout << "see edge: " << curEdge << endl; hierholzer(nextSt, graph, res, seen); // post order res.push_back(graph[st][edIdx]); // hierholzer } } };

0514wayOfFreedom 自由之路

1 题目

https://leetcode-cn.com/problems/freedom-trail/

2 解题思路

• 1 首先考虑到，key中的每一个字符，环的所有同种字符的所有位置都是遍历的可能
  • 1.1 于是使用dfs去尝试对于key的一个字符的每个位置即可，然后讲每个位置得到的结果比较取一个最小值
  • 1.2 1.1中提到的算法肯定是有问题的，比如key： abc， 然后ring: aaabbbccc
    • 会出现哪种情况呢？ ring中a的三个位置都会搜索，然后对于剩下的key和ring bc以及bbbccc会由于a有三个位置而搜索了三遍，所以需要记忆化搜索
  • 1.3 使用memo[i][j]记录： key[i:]和ring[j:]对应的最小步数即可
• 2 经过1的思考，也较为容易知道，本题目，动态规划也能做
• 3 写代码的教训，由于我将dfsmemo写好，然后调用dfs的地方也改了，但是依然超时？
  • 3.1 因为dfsmemo递归调用不是自身，而是dfs函数，所以务必及时清理不需要的代码

    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

    class Solution { public: int ringLen = -1; int keyLen = -1; int findRotateSteps(string ring, string key) { unordered_map<char, vector<int>> ringMap; ringLen = ring.length(); keyLen = key.length(); int pos = 0; for(auto& c : ring) { if(0 == ringMap.count(c)) { vector<int> tmp = {pos}; ringMap[c] = tmp; } else { ringMap[c].push_back(pos); } ++pos; } vector<vector<int>> memo(keyLen, vector<int>(ringLen, INT_MAX)); return dfsMemo(0, 0, ringMap, key, memo); } // no memo dfs, too slow int dfs(int tar, int markPos, unordered_map<char, vector<int>>& ringMap, string& key) { if(tar == key.length()) { return 0; } int minStep = INT_MAX; // for cur key char, try ervery possible way on the ring for(auto tarPos : ringMap[key[tar]]) { int curStep = minDis(tarPos, markPos); // rotate curStep += 1; // write minStep = min( minStep, dfs(tar + 1, tarPos, ringMap, key) + curStep ); } return minStep; } // memo version int dfsMemo(int tar, int markPos, unordered_map<char, vector<int>>& ringMap, string& key, vector<vector<int>>& memo) { if(tar == key.length()) { return 0; } if(INT_MAX != memo[tar][markPos]) { return memo[tar][markPos]; } // for cur key char, try ervery possible way on the ring for(auto tarPos : ringMap[key[tar]]) { int curStep = minDis(tarPos, markPos); // rotate curStep += 1; // write memo[tar][markPos] = min( memo[tar][markPos], dfsMemo(tar + 1, tarPos, ringMap, key, memo) + curStep ); } // cout << "memo ing: " << tar << ", " << markPos << ": " << memo[tar][markPos] << endl; return memo[tar][markPos]; } int minDis(int tarPos, int markPos) { int gt = max(tarPos, markPos); int lt = min(tarPos, markPos); return min(gt - lt, lt + ringLen - gt); } };

0968minCameraCover 监控二叉树

1 题目

https://leetcode-cn.com/problems/binary-tree-cameras/submissions/

2 解题思路

• 1 首先得在思考的过程中，理解改题目的本质就是，
  • 1.1 在dfs的过程中，在每个节点可以放置或者不放置相机，重要的是，如何去体现放置还是不放置相机
  • 1.2 如何提现呢？很简单，比如root放置，然后你想让它的两个子节点都不放置，那么直接递归调用两个子节点的后代即可，具体看代码即可
  • 1.3 那么对于每个节点，有几种放置相机的可能呢？
    • 一共三种，要么root，要么left，要么right，然后取最小代价即可，这里以选择left子节点仔细说明：

      1 2 3 4 5 6 7 8 9 10 11 12 13

      // choosing: right int tmpRightCover = min( // r的监控器对r的两个子节点都有监控作用，于是直接去计算两个子节点的子节点 1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_l), min( // r的监控器对r的两个子节点中的右孩子有监控作用，于是计算方式变为算右孩子两个子节点加上左侧节点 // partly ignore, will not put cam on r_rr, may on r_r 1 + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_rl) + minCameraCover(r_l), // r的监控器对r的两个子节点中的左孩子有监控作用，于是计算方式变为算左孩子两个子节点加上右侧节点 // partly ignore, will not put cam on r_rl, may on r_l 1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rr) + minCameraCover(r_l) ) );

• 2 优化思路：
  • 2.1 同一层递归里面，相同函数名不要反复出现，用临时变量存储以加速
  • 2.2 使用hash存储对应的节点的最小监控值，如果能在hash命中就不用反复计算
  • 2.3 优先计算小规模，然后计算大规模
• 3 关于为什么需要hash来避免反复计算：
  • 3.1 看例子：
    [0,null,0,null,0,null,0,null,0,null,0,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,0,null,null,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null]
  • 3.2 也就是单链表，你会发现，到达第4个节点，可以有两种监控方式，那么说明第4个节点的计算会重复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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

/**
 * 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 {
public:
    int level = 0;
    unordered_map<TreeNode* , int> memo;
    int minCameraCover(TreeNode* root) {
        ++level;
        if(nullptr == root) {
            return 0;
        }

        if(nullptr == root->left && nullptr == root->right) {
            return 1;
        }
        
        // dp:
        TreeNode* r_l = root->left;
        TreeNode* r_r = root->right;

        TreeNode* r_ll = getL(r_l);
        TreeNode* r_lr = getR(r_l);
        TreeNode* r_rl = getL(r_r);
        TreeNode* r_rr = getR(r_r);

        TreeNode* r_lll = getL(r_ll);
        TreeNode* r_llr = getR(r_ll);
        TreeNode* r_lrl = getL(r_lr);
        TreeNode* r_lrr = getR(r_lr);
        TreeNode* r_rll = getL(r_rl);
        TreeNode* r_rlr = getR(r_rl);
        TreeNode* r_rrl = getL(r_rr);
        TreeNode* r_rrr = getR(r_rr);
 
        int cover_r_lll = getFromMemo(r_lll);
        int cover_r_llr = getFromMemo(r_llr);
        int cover_r_lrl = getFromMemo(r_lrl);
        int cover_r_lrr = getFromMemo(r_lrr);
        int cover_r_rll = getFromMemo(r_rll);
        int cover_r_rlr = getFromMemo(r_rlr);
        int cover_r_rrl = getFromMemo(r_rrl);
        int cover_r_rrr = getFromMemo(r_rrr);

        int cover_r_ll = getFromMemo(r_ll);
        int cover_r_lr = getFromMemo(r_lr);
        int cover_r_rl = getFromMemo(r_rl);
        int cover_r_rr = getFromMemo(r_rr);

        int cover_r_l = getFromMemo(r_l);
        int cover_r_r = getFromMemo(r_r);

        // // choosing: root
        // int tmpRootCover = min(
        //     // min(
        //         // do not ignore
        //     1 + minCameraCover(r_ll) + minCameraCover(r_lr) + minCameraCover(r_rl) + minCameraCover(r_rr),
        //         // 1 + minCameraCover(r_l) + minCameraCover(r_r)
        //     // ),
        //     // partly ignore root choosen
        //     min(
        //         1 + minCameraCover(r_ll) + minCameraCover(r_lr) + minCameraCover(r_r), 
        //         1 + minCameraCover(r_rl) + minCameraCover(r_rr) + minCameraCover(r_l)
        //     )
        // );

        int tmpRootCover = min(
            1 + cover_r_ll + cover_r_lr + cover_r_rl + cover_r_rr,
            min(
                1 + cover_r_ll + cover_r_lr + cover_r_r,
                1 + cover_r_rl + cover_r_rr + cover_r_l
            )
        );

        // // choosing: right 
        // int tmpRightCover = min(
        //     // don't ignore, will not put cam on r_rl, r_rr
        //     1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_l),
        //     min(
        //         // partly ignore, will not put cam on r_rr, may on r_r
        //         1 + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_rl) + minCameraCover(r_l),
        //         // partly ignore, will not put cam on r_rl, may on r_l
        //         1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rr) + minCameraCover(r_l)
        //     )
        // );

        int tmpRightCover = min(
            1 + cover_r_rll + cover_r_rlr + cover_r_rrl + cover_r_rrr + cover_r_l,
            min(
                1 + cover_r_rrl + cover_r_rrr + cover_r_rl + cover_r_l,
                1 + cover_r_rll + cover_r_rlr + cover_r_rr +  cover_r_l
            )
        );

        // // choosing: left
        // int tmpLeftCover = min(
        //     1 + minCameraCover(r_lll) + minCameraCover(r_llr) + minCameraCover(r_lrl) + minCameraCover(r_lrr) + minCameraCover(r_r),
        //     min(
        //         1 + minCameraCover(r_ll) + minCameraCover(r_lrl) + minCameraCover(r_lrr) + minCameraCover(r_r),
        //         1 + minCameraCover(r_lr) + minCameraCover(r_lll) + minCameraCover(r_llr)  + minCameraCover(r_r)
        //     )
        // );
        int tmpLeftCover = min(
            1 + cover_r_lll + cover_r_llr + cover_r_lrl + cover_r_lrr + cover_r_r,
            min(
                1 + cover_r_ll + cover_r_lrl + cover_r_lrr + cover_r_r,
                1 + cover_r_lr + cover_r_lll + cover_r_llr + cover_r_r
            )
        );

        return min(tmpRootCover, min(tmpLeftCover, tmpRightCover));
    }

    TreeNode* getR(TreeNode* root) {
        if(nullptr == root) {
            return nullptr;
        } else {
            return root->right;
        }
    }
    TreeNode* getL(TreeNode* root) {
        if(nullptr == root) {
            return nullptr;
        } else {
            return root->left;
        }
    }

    int getFromMemo(TreeNode* root) {
        if(memo.end() == memo.find(root)) {
            memo[root] = minCameraCover(root);
        } 
        return memo[root];
    }
        
};

四种基础排序

• 归并排序
• 堆排序
• 快速排序
• 桶排序

1 题目：

https://leetcode-cn.com/problems/sort-an-array/

2 解题思路：

• 1 分别详细解释 快速排序，归并排序，堆排序
  • 1.1 快速排序
    • 算法核心：选择一个数字，然后将比他大的都移动到他左边，比他小的都是右边，然后分别对左侧区域和右侧区域递归执行即可
    • 速度和稳定性：在单调情况下达到最坏，为O(n**2)，不稳定的原因，中枢元素会和最后一个比他小的数字交换位置(以此将左侧分为比他小的，右侧比他大的)；
  • 1.2 归并排序
    • 算法核心：切分成左右两部分，然后对于左右两部分分别执行算法本身，知道之剩下2个以及1个元素，返回后合并即可
    • 速度稳定性：速度稳定，元素之间次序稳定
  • 1.3 堆排序：
    • 算法核心：首先建立一个大根堆，之后第i次将大根堆的top移动到nums的nums[n-i]处，而后将nums[0:n-i-1]重新排列成大根堆，一次选出一个最大元素排在末尾，可以看出这里主要代价在于将maxHeapfiy(nums[0:n-i-1])
    • 速度稳定性：速度稳定，元素之间次序不稳定，因为对于7,5,5 你会发现一开始将最后的5移动到了第一个，打乱了次序
    • 图解参考：https://zhuanlan.zhihu.com/p/124885051
  • 1.4 使用桶排序
    • 1.4.1 根据最大最小值算桶的大小
    • 1.4.2 将桶排列好，将每个值放入(桶内部插入排序)
    • 1.4.3 将所有的值从桶里取出来，然后形成排序后的数组
    • 平均时间复杂度o(n + k)，最烂：o(n**2)，为稳定排序
    • 空间复杂度o(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // quick sort, most bad when it is sorted o(n**2), not stable
        // quickSort(0, nums.size() - 1, nums); 

        // merge sort, stable
        // mergeSort(0, nums.size() - 1, nums);

        // heap sort, not stable
        head_sort(0, nums.size() - 1, nums);
        return nums;
    }

    void head_sort(int st, int ed, vector<int>& nums) {
        // init
        buildMaxHeap(nums);

        // everytime select max and put to end and call maxHeapify
        int len = nums.size();
        for(int ed = len - 1; ed >= 0; --ed) {
            swap(st, ed, nums);
            // nums[ed:] is sorted
            maxHeapify(st, ed - 1, nums);
        }
    }

    void buildMaxHeap(vector<int>& nums) {
        // start from the last dad node, till all dad node be the max heap root
        int len = nums.size();
        for(int dad = len / 2 - 1; dad >= 0; --dad) {
            maxHeapify(dad, len - 1, nums);
        }
    }

    void maxHeapify(int st, int ed, vector<int>& nums) {
        if(ed <= st) {
            return;
        }

        while(st <= ed) {
            // cmp the st and its lChild and rChild and decide which side to descend
            int lChild = st * 2 + 1;
            int rChild = st * 2 + 2;
            // cout << "l/r: " << lChild << " " << rChild << endl;
            if(lChild > ed) {
                return;
            } else if(rChild > ed) {
                if(nums[st] < nums[lChild]) {
                    swap(st, lChild, nums);
                }
                return;
            }
            if(nums[st] >= nums[lChild] && nums[st] >= nums[rChild]) {
                return;
            } else {
                if(nums[lChild] > nums[rChild]) {
                    swap(st, lChild, nums);
                    st = lChild;
                } else {
                    swap(st, rChild, nums);
                    st = rChild;
                }
            }
        }
    }

    void mergeSort(int st, int ed, vector<int>& nums) {
        // sort when |st - ed| <= 1
        if(ed - st == 1) {
            if(nums[ed] < nums[st]) {
                swap(ed, st, nums);
            }
            return;
        } else if(ed == st) {
            return;
        }
        int mid = (st + ed) / 2;
        cout << mid << endl;
        mergeSort(st, mid, nums);
        mergeSort(mid + 1, ed, nums);
        
        // merge
        int curL = 0;
        int curR = 0;
        vector<int> tmpL(nums.begin() + st, nums.begin() + mid + 1);
        vector<int> tmpR(nums.begin() + mid + 1, nums.begin() + ed + 1);

        for(int i = st; i <= ed; ++i) {
            if(curL == mid - st + 1) {
                // cout << "using R to fullly fill from " << curR << endl;
                for(; curR < ed - mid; ++curR) {
                    nums[i++] = tmpR[curR];
                }
                break;
            } else if(curR == ed - mid) {
                // cout << "using L to fullly fill from " << curL << endl;
                for(; curL < mid - st + 1; ++curL) {
                    nums[i++] = tmpL[curL];
                }
                break;
            } else if(tmpL[curL] < tmpR[curR]) {
                nums[i] = tmpL[curL++];
                // cout << "using L: " << nums[i] << endl;
            } else {
                nums[i] = tmpR[curR++];
                // cout << "using R: " << nums[i] << endl;
            }
        }
    }

    void quickSort(int st, int ed, vector<int>& nums) {
        if(st >= ed) {
            return;
        }
        
        int newPivot = partition(st, ed, nums);
        quickSort(st, newPivot-1, nums);
        quickSort(newPivot + 1, ed, nums);
    }

    int partition(int st, int ed, vector<int>& nums) {
        // put 'smaller than st' to left, others right
        int r = ed;
        int l = st;
        // st is the first blank place
        int pivot = nums[st];
        while(l < r){
            // r form right to left
            while(r > l && nums[r] > pivot) {
                r--;
            }
            nums[l] = nums[r];

            // l form left to right
            while(l < r && nums[l] <= pivot) {
                l++;
            }
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }

    void swap(int& a, int& b, vector<int>& nums) {
        // cout << "swaping! " << a << " " << b << endl;
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    void print(vector<int>& nums) {
        for(auto& i : nums) {
            cout << i << " ";
        }
        cout << "\n";
    }
};

0164maxGap 最大间距

1 题目

https://leetcode-cn.com/problems/maximum-gap/

2 解题思路

• 1 使用桶排序
  • 1.1 平均时间复杂度o(n + k)，最烂：o(n**2)
  • 1.2 空间复杂度o(n)
• 2 桶排序算
  • 2.1 根据最大最小值算桶的大小
  • 2.2 将桶排列好，将每个值放入(桶内部插入排序)
  • 2.3 将所有的值从桶里取出来，然后形成排序后的数组

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

class Solution {
public:
    int len = -1;
    int maximumGap(vector<int>& nums) {
        len = nums.size();
        if(len <= 1) {
            return 0;
        }
        // bucket sort
        bucketSort(nums);

        // getMaxGap
        int gap = INT_MIN;
        int last = nums[0];
        for(auto i : nums) {
            gap = max(i - last, gap);
            last = i;
        } 
        return gap;
    }

    void bucketSort(vector<int>& nums) {
        int maxNum = *max_element(nums.begin(), nums.end());
        int bucketSize = maxNum / len + 1;
        int bucketNum = len + 1;
        vector<list<int>> buckets(bucketNum, list<int>(0));

        // put to buckets
        for(int i = 0; i < len; ++i) {
            insertSort(buckets[nums[i] / bucketSize], nums[i]);
        }
        
        // merge
        int idx = 0;
        for(auto& l : buckets) {
            for(auto num : l) {
                nums[idx++] = num;
            }
        }
    }
    
    void insertSort(std::list<int>& l, int num) {
        for(list<int>::iterator it = l.begin(); it != l.end(); ++it) {
            if(*it > num) {
                l.insert(it, num);
                return;
            }
        }

        l.push_back(num);
    }
};

Item 2: 用 consts, enums 和 inlines 取代 #defines

使用define的缺陷：

• 1 预处理器盲目多次拷贝替换宏名，导致产生更多的代码 -> 使用const常量解决
• 2 宏函数的嵌套需要打上括号 -> 使用内连函数达到相同的性能解决

使用enum替换const的用例：

1
2
3
4
5
6
7
8

class GamePlayer {
private:
 enum { NumTurns = 5 }; // "the enum hack" - makes
 // NumTurns a symbolic name for
5
 int scores[NumTurns]; // fine
 ...
};

优点有其二：

• 1 避免常量的指针和引用被取走
  首先，the enum hack
  的行为在几个方面上更像一个 #define 而不是 const，而有时这正是你
  所需要的。例如：可以合法地取得一个 const 的 address（地址），
  但不能合法地取得一个 enum 的 address（地址），这正像同样不能
  合法地取得一个 #define 的 address（地址）。如果你不希望人们得
  到你的 integral constants（整型族常量）的 pointer（指针）或
  reference（引用），enum（枚举）就是强制约束这一点的好方法。
• 2 被模板元编程大量使用，属于实用主义

总结：

a. 对于 simple constants（简单常量），用 const objects（const 对
象）或 enums（枚举）取代 #defines。

b. 对于 function-like macros（类似函数的宏），用 inline
functions（内联函数）取代 #defines

Item 3: 只要可能就用 const

1 const用于指针，迭代器：

• 1 用于指针：
  如果 const 出现在星号左边，则指针 pointed to（指向）的内容为 constant（常量）；
  如果 const 出现在星号右边，则 pointer itself（指针自身）为
  constant（常量）；如果 const 出现在星号两边，则两者都为
  constant（常量）。

  1 2 3 4 5 6 7 8 9 10 11 12

  char greeting[] = "Hello"; char *p = greeting; // non-const pointer, // non-const data const char *p = greeting; // non-const pointer, // const data char * const p = greeting; // const pointer, // non-const data const char * const p = greeting; // const pointer, // const data void f1(const Widget *pw); // f1 takes a pointer to a // constant Widget object void f2(Widget const *pw); // so does f2

• 2 用于迭代器：
  声明一个iterator 为 const 就类似于声明一个 pointer（指针）为 const（也就是说，声明一个 T* const pointer（指针））：不能将这个 iterator 指向另外一件不同的东西，但是它所指向的东西本身可以变化。
  若需要iterator指向的东西不能变，使用const_iterator即可

  1 2 3 4 5 6 7 8 9 10 11 12 13

  std::vector<int> vec; ... const std::vector<int>::iterator iter = // iter acts like a T* const vec.begin(); *iter = 10; // OK, changes what iter points to ++iter; // error! iter is const std::vector<int>::const_iterator cIter = // cIter acts like a const T* vec.begin(); *cIter = 10; // error! *cIter is const ++cIter; // fine, changes cIter

  2 用于函数

• 1 返回值和传参是const
  避免了=和==的错误

  1 2 3 4 5 6 7 8 9

  class Rational { ... }; const Rational operator*(const Rational& lhs, const Rational& rhs); Rational a, b, c; ... (a * b) = c; // invoke operator= on the // result of a*b! if (a * b = c) ... // oops, meant to do a comparison!

  参数在不会被改变的时候就应该传入const

• 2 const member functions（const 成员函数）
  有两个原因：

  • 2.1 它使一个 class（类）的 interface（接口）更容易被理
    解。知道哪个函数可以改变 object（对象）而哪个不可以是很重要
    的。
  • 2.2 它们可以和 const objects（对象）一起工作。因为，书写
    高效代码有一个很重要的方面，就像 Item 20 所解释的，提升一个
    C++ 程序的性能的基本方法就是 pass objects by reference-to const（以传引用给 const 的方式传递一个对象）。

具体看如下代码：

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

class TextBlock {
public:
 ...
 const char& operator[](std::size_t position) const // operator[]
for
 { return text[position]; } // const objects

 char& operator[](std::size_t position) // operator[]
for
 { return text[position]; } // non-const objects

private:
 std::string text;
};
// ------------------- 1 -----------------------
TextBlock tb("Hello");
std::cout << tb[0]; // calls non-const
 // TextBlock::operator[]
const TextBlock ctb("World");
std::cout << ctb[0]; // calls const
TextBlock::operator[]

// -------------------- 2 ----------------------
void print(const TextBlock& ctb) // in this function, ctb is
const
{
 std::cout << ctb[0]; // calls const TextBlock::operator[]
 ...
}
// --------------------- 3 ---------------------
std::cout << tb[0]; // fine — reading a
 // non-const TextBlock
tb[0] = 'x'; // fine — writing a
 // non-const TextBlock
std::cout << ctb[0]; // fine — reading a
 // const TextBlock
ctb[0] = 'x'; // error! — writing a
 // const TextBlock

3 const的二进制常量性和逻辑常量性

bitwise（二进制位）const 派别坚持认为，一个 member function（成
员函数），当且仅当它不改变 object（对象）的任何 data
members（数据成员）（static（静态的）除外），也就是说如果不改
变 object（对象）内的任何 bits（二进制位），则这个 member
function（成员函数）就是 const。bitwise constness（二进制位常量
性）的一个好处是比较容易监测违例：编译器只需要寻找对 data
members（数据成员）的 assignments（赋值）。实际上，bitwise
constness（二进制位常量性）就是 C++ 对 constness（常量性）的
定义，一个 const member function（成员函数）不被允许改变调用它
的 object（对象）的任何 non-static data members（非静态数据成
员）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class CTextBlock {
public:
 ...
 char& operator[](std::size_t position) const // inappropriate
(but bitwise
 { return pText[position]; } // const)
declaration of
 // operator[]
private:
 char *pText;
};
// ----------------------------------------------
const CTextBlock cctb("Hello"); // declare constant object
char *pc = &cctb[0]; // call the const operator[]to get a
 // pointer to cctb's data
*pc = 'J'; // cctb now has the value "Jello"

上述过程中：你用一个 particular value（确定值）创建一个
constant object（常量对象），然后你只是用它调用了 const member
functions（成员函数），但是你还是改变了它的值！
这就引出了 logical constness（逻辑常量性）的概念。这一理论的信
徒认为：一个 const member function（成员函数）可能会改变调用它
的 object（对象）中的一些 bits（二进制位），但是只能用客户无法
察觉的方法。例如，你的 CTextBlock class（类）在需要的时候可以
储存文本块的长度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class CTextBlock {
public:
 ...
 std::size_t length() const;
private:
 char *pText;
 // 可以解脱的代码
 // mutable std::size_t textLength; // these data members may
 // mutable bool lengthIsValid; // always be modified, even
in
 std::size_t textLength; // last calculated length of
textblock
 bool lengthIsValid; // whether length is currently
valid
};
std::size_t CTextBlock::length() const
{
 if (!lengthIsValid) {
 textLength = std::strlen(pText); // error! can't assign to textLength
 lengthIsValid = true; // and lengthIsValid in a const
 } // member function
 return textLength;
}

上述代码会由于成员函数length()后面跟了一个const使得编译器保证了类的二进制常量性，那么想要修复这个问题，则只用mutable将其从中解脱。

4 const和non-const函数有相同实现的单向调用

为避免代码重复，则non版本调用const版本，具体例子如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class TextBlock {
public:
 ...
 const char& operator[](std::size_t position) const // same as
before
 {
 ...
 ...
 ...
 return text[position];
 }
 char& operator[](std::size_t position) // now just calls
const op[]
 {
 return
 const_cast<char&>( // cast away const on
 // op[]'s return type;
 static_cast<const TextBlock&>(*this)[position] // add const to *this's type;  // call const version of op[]  
 ); }
...
};

cosnt_cast去掉const属性，然后用static_cast将this转为const去调用对应的const函数。
而不能用const成员函数去调用非const版本的是因为需要将cosnt的this转为non-const的this，会导致值发生改变，这就导致const成员函数失去本身意义。

总结：

将某些东西声明为 const 有助于编译器发现使用错误。const 能
被用于任何 scope（范围）中的 object（对象），用于 function
parameters（函数参数）和 return types（返回类型），用于整
个 member functions（成员函数）。

编译器坚持 bitwise constness（二进制位常量性），但是你应该
用 conceptual constness（概念上的常量性）来编程。

当 const 和 non-const member functions（成员函数）具有本质
上相同的实现的时候，使用 non-const 版本调用 const 版本可以
避免 code duplication（代码重复）。

1 有序集合

泛指set, map, pirority_queue等能够按照key进行排序，然后使用lower_bound和upper_bound来进行log(n)复杂度查询的基础数据结构
(注意priority_queue仅能够在堆顶进行操作)
示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

        set<int, std::less<int>> spareServers;
<被作者省略>
            // request distribute, find the server
            int tarServer = -1;
            auto itr = spareServers.lower_bound(arrivalIdx % k);
            // cout << "trying to find: " << arrivalIdx % k << endl;
            if(itr != spareServers.end()) {
                tarServer = *itr;
                // cout << "find tar1: " << tarServer << endl;
            } else { // search from the start just like search like a cycle
                tarServer = *spareServers.lower_bound(0);
                // cout << "find tar2: " << tarServer << endl;
            }

2 具体示例

0363maxSumSubMatrix 最大子区域和

1 题目：

https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/

2 解题思路：

• 1 普通思路：一维前缀和，按行计算前缀和，使用m x n的矩阵存储，然后计算矩形区域，则只需要O(m)的计算复杂度
• 2 优化：二维前缀和，pre[i][j]存储的是0，0到i，j处的矩形区域和，那么计算方式为：

  preMat2[i+1][j+1] = preMat2[i][j+1] + preMat2[i+1][j] - preMat2[i][j] + matrix[i][j];

• 3 使用二位前缀和去计算子区域的和，搜索子区域的方式：
  • 3.1 对于每个子区域的上下边界搜索左右边界，上下左边界搜索复杂度为o(n^2), 而后搜索左右边界，对于每一个右边界O(n)，搜索左边界，什么样的左边界？left满足sum(up, down, 0, right) - k <= sum(up, down, 0, left), 也就是在[0, right]的范围内找到最小的大于sum(up, down, 0, right) - k的left，在遍历的过程中使用set存所有的sum(up, down, 0, right), 在这个set里面找left，使用lower_bound函数，只需要log(n)复杂度，于是总复杂度为 o(m^2 * nlog(n))
  • 3.2 上述核心思想： 本来需要找right和left的对子，但是现在借助k，找left就变成在right的历史中搜索即可
    • 3.2.1 原来思想：sum(up, down, 0, right) - sum(up, down, 0, left) <= k
    • 3.2.2 新的思想：sum(up, down, 0, right) - k <= sum(up, down, 0, left)

      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

      class Solution { public: static constexpr int matLen = 102; vector<vector<int>> preMat; // 2d prefix sum int m = -1; int n = -1; int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { // cal 2d prefix sum m = matrix.size(); n = matrix[0].size(); preMat.resize(m+1, vector<int>(n+1, 0)); for(int i = 0; i < m; ++i){ for(int j = 0; j < n; ++j){ preMat[i+1][j+1] = preMat[i][j+1] + preMat[i+1][j] - preMat[i][j] + matrix[i][j]; // cout << preMat[i+1][j+1] << endl; } } // for each up and down, find max l,r int res = INT_MIN; for(int d = 0; d < m; ++d) { for(int u = d; u >= 0; --u) { set<int> lSet = {0}; for(int r = 0; r < n; ++r) { int sumRight = sumRegion(u, d, 0, r); set<int>::iterator lbPtr = lSet.lower_bound(sumRight - k); lSet.insert(sumRight); if(lbPtr != lSet.end()) { res = max(res, sumRight - *lbPtr); } } } } return res; } int sumRegion(int up, int down, int left, int right) { return preMat[down+1][right+1] - preMat[down+1][left] - preMat[up][right+1] - preMat[up][left]; } };

0699fallingSquares 掉落的方块

1 题目：

https://leetcode-cn.com/problems/falling-squares/

2 解题思路：

• 1 普通思路：使用一维数组模拟每个位置方块高度，复杂度为o(N^2)，由于N很大，所以会超时
• 2 优化：使用坐标压缩，将所有方块的边界存储在2000以内（因为一共就1000个方块），然后更新高度就按照2000以内去更新即可

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

  class Solution { public: vector<int> fallingSquares(vector<vector<int>>& positions) { // coordinate compression set<int, std::less<int>> coords; for(vector<int>& coord : positions) { coords.insert(coord[0]); coords.insert(coord[0] + coord[1] - 1); } unordered_map<int, int> borderToIdx; int t = 0; for(auto& i : coords) { borderToIdx[i] = t++; } // cal heights vector<int> heights(t); vector<int> res; int curHeightest = INT_MIN; for(vector<int>& square : positions) { int l = borderToIdx[square[0]]; int r = borderToIdx[square[0] + square[1] - 1]; int h = square[1]; int updatedHeight = update(l, r, h, heights); curHeightest = max(curHeightest, updatedHeight); res.emplace_back(curHeightest); } return res; } // update and return updated height of [l, r] int update(int l, int r, int h, vector<int>& heights) { int oldHeight = INT_MIN; for(int i = l; i <= r; ++i) { oldHeight = max(oldHeight, heights[i]); } int newHeight = INT_MIN; for(int i = l; i <= r; ++i) { heights[i] = oldHeight + h; } return oldHeight + h; } };

0715 Range 模块 rangeModule

1 题目：

https://leetcode-cn.com/problems/range-module/

2 解题思路：

• 1 普通思路：使用map记录这些离散的区间
  • 1.1 添加、删除： 遍历map，看map的每一个区间和当前区间的关系，这样处理最为合适
  • 1.2 查询：使用upper_bound查询到第一个（左侧）比目标的left小的区间，然后看目标的left和right是否在map对应的区间内部

    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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144

    class RangeModule { public: map<int, int, std::less<int>> intervals; RangeModule() { } void addRange(int left, int right) { if(intervals.size() == 0) { intervals[left] = right; print(); return ; } for(auto it = intervals.begin(); it != intervals.end(); ++it) { if(it->first >= left) { if(it->first > right) { continue; } while(it != intervals.end() && it->second <= right) { it = intervals.erase(it); } if(it == intervals.end()){ intervals[left] = right; } else { if(it->first <= right) { int newRight = it->second; intervals.erase(it); intervals[left] = newRight; }else { intervals[left] = right; } } print(); return; } else { // it->first < left if(it->second < left) { continue; } int newLeft = it->first; while(it != intervals.end() && it->second <= right) { it = intervals.erase(it); } if(it == intervals.end()){ intervals[newLeft] = right; } else { if(it->first <= right) { int newRight = it->second; intervals.erase(it); intervals[newLeft] = newRight; }else { intervals[newLeft] = right; } } print(); return; } } intervals[left] = right; print(); } bool queryRange(int left, int right) { if(intervals.empty()) { return false; } auto lBig = intervals.upper_bound(left); if(lBig != intervals.begin()) { --lBig; return lBig->second >= right; } else { return false; } return false; } void removeRange(int left, int right) { // for(auto it = intervals.begin(); it != intervals.end(); ++it) { // for(int i = 0) // } auto lBig = intervals.lower_bound(left); int newLeft = 0; if(lBig != intervals.begin()) { // cout << "d1.5" << endl; --lBig; if(right < lBig->second) { intervals[right] = lBig->second; intervals[lBig->first] = left; print(); return ; } else { // cout << "d2" << endl; if(lBig->second > left) { // cout << "d2.5" << endl; intervals[lBig->first] = left; } } ++lBig; while (lBig != intervals.end() && lBig->second < right) { lBig = intervals.erase(lBig); } if(lBig != intervals.end()) { if(lBig->first < right) { int secondRight = lBig->second; intervals.erase(lBig); intervals[right] = secondRight; } } } else { while (lBig != intervals.end() && lBig->second < right) { lBig = intervals.erase(lBig); } if(lBig != intervals.end()) { if(lBig->first < right) { int secondRight = lBig->second; intervals.erase(lBig); intervals[right] = secondRight; } } } print(); } void print() { // cout << "-----st-----" << endl; // for(auto it = intervals.begin(); it != intervals.end(); ++it) { // cout << it->first << " " << it->second << endl; // } // cout << "-----ed-----" << endl; } }; /** * Your RangeModule object will be instantiated and called as such: * RangeModule* obj = new RangeModule(); * obj->addRange(left,right); * bool param_2 = obj->queryRange(left,right); * obj->removeRange(left,right); */

0850. 矩形面积 II

1 题目：

https://leetcode-cn.com/problems/rectangle-area-ii/solution

2 解题思路：

• 1 参考官方思路的扫描线：https://leetcode-cn.com/problems/rectangle-area-ii/solution/ju-xing-mian-ji-ii-by-leetcode/
• 2 总结过程：
  • 2.1 将一个矩形看成x1,x2,y1,ST; x1,x2,y2,ED;的两条线
  • 2.2 而后用active记录还没有遇到ED的那些矩形的第一个扫描线集合，每回新来了一根线，则将active中的所有线和当前线计算对应面面积加起来
  • 2.3 当active中遇到了矩形的ED，则将active中对应的矩形的ST删除

    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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

    class Solution { public: static constexpr long long bigPrime = 1000000007; int rectangleArea(vector<vector<int>>& rectangles) { // lines int ST = 0; int ED = 1; vector<vector<int>> lines; for(auto& vec : rectangles) { lines.emplace_back(vector<int>{vec[0], vec[2], vec[1], ST}); lines.emplace_back(vector<int>{vec[0], vec[2], vec[3], ED}); } // sort the lines by the y sort(lines.begin(), lines.end(), [](vector<int>& a, vector<int>& b) { return a[2] < b[2]; }); // scan the lines vector<vector<int>> actives; long long res = 0; int lastY = lines[0][2]; for(auto& line : lines) { int curY = line[2], type = line[3], x1 = line[0], x2 = line[1]; int width = 0; int actX = -1; // actives: those opend lines, sorted by y for(auto& act : actives) { // cout << "act: " << act[0] << " " << act[1] << endl; actX = max(actX, act[0]); width += max(act[1] - actX, 0); actX = max(actX, act[1]); } res += static_cast<long long>(width) * (curY - lastY) % bigPrime; // cout << "w: " << width << endl; // add new actives if(type == ST) { actives.emplace_back(vector<int>{x1, x2, curY, type}); // cout << "insert x1,2: " << x1 << " " << x2 << endl; // sort the opend lines of the started points sort(actives.begin(), actives.end(), [](vector<int>& line1, vector<int>& line2) { return line1[0] < line2[0]; }); } else { // find the active and rm it for(int i = 0; i < actives.size(); ++i) { if(actives[i][0] == x1 && actives[i][1] == x2) { actives.erase(actives.begin() + i); // cout << "earse x1,2: " << x1 << " " << x2 << endl; break; } } } lastY = curY; } return res % bigPrime; } vector<vector<int>> getSkyLine(vector<vector<int>>& buildings) { function<bool(pair<int, int>&, pair<int, int>&)> cmp = [](pair<int, int>& a, pair<int, int>& b) { return a.second < b.second; }; // <rightBound, height> priority_queue<pair<int, int>, vector<pair<int, int>>, function<bool(pair<int, int>&, pair<int, int>&)> > queue(cmp); vector<int> bounds; vector<vector<int>> res; int n = buildings.size(); for(int i = 0; i < n; ++i) { bounds.emplace_back(buildings[i][0]); bounds.emplace_back(buildings[i][1]); } sort(bounds.begin(), bounds.end(), std::less<int>()); // std::cout << "c1" << endl; int j = 0; for(auto& curBound : bounds) { // std::cout << "c " << j << endl; // push buildings lefter than curBound until one righter meet while(j < buildings.size() && curBound >= buildings[j][0]) { queue.push(make_pair(buildings[j][1], buildings[j][2])); ++j; } // std::cout << "c " << "adf" << endl; // pop out those rec unrelevant while(!queue.empty() && curBound >= queue.top().first) { queue.pop(); } int curBoundHeight = queue.empty() ? 0 : queue.top().second; // if(res.size() == 0 || res.back()[1] != curBoundHeight) { // res.emplace_back(vector<int>{curBound, curBoundHeight}); // } if(res.size() == 0 || res.back()[1] != curBoundHeight) { res.emplace_back(vector<int>{curBound, curBoundHeight}); } } return res; } void print(vector<vector<int>>& vec) { for(auto& v : vec) { for(auto& i : v) { cout << i << " "; } cout << endl; } } };