leetcode解题思路分析（一百二十六）1038 - 1044 题

1038. 从二叉搜索树到更大和树
      给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

二叉搜索树的中序遍历是从小到大排序的，如果先右后左则刚好满足题意，递归之

/**
 * 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 
{
    int nTotal;
public:
    TreeNode* bstToGst(TreeNode* root) 
    {
        nTotal = 0;
        ChangeVal(root);
        return root;
    }

private:
    void ChangeVal(TreeNode* pNode)
    {
        if (pNode == NULL) return;

        ChangeVal(pNode->right);

        pNode->val += nTotal;
        nTotal = pNode->val;

        ChangeVal(pNode->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

1039. 多边形三角剖分的最低得分
      你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。
      假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

只递归会带来大量的重复计算导致栈溢出，采用一个数组存储可以起到剪枝作用。

class Solution {
public:
    int memo[55][55];
    int dfs(const vector<int>& values, int l, int r)  // 从第 l 点到第  r 个点所形成的三角形的最小面积
    {
        if (r - l + 1 < 3)
            return 0;
        
        if (memo[l][r])
            return memo[l][r];
        
        int res = 0x3f3f3f3f;

        for (int k = l+1; k < r; k++)
        {
            res = min(res,  values[l] * values[k] *values[r] + dfs(values, l, k) + dfs(values, k, r));
        }
        memo[l][r] = res;
        return res;

    }

    int minScoreTriangulation(vector<int>& values) {
        memset(memo, 0, sizeof(memo));
        return dfs(values, 0, values.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

·1040. 移动石子直到连续 II
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。

最关键的是理解题意：每次移动只能动端点，但是端点移动只能插在内部，如果是端点插成端点是不可以的。因此先求出最大可移动空间，之后每次移动一步，这就是最大移动次数。而最小移动次数，则是采用滑动空间找到当前已满足连续的最大区间，然后努力靠进去即可。

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(),stones.end());
        int n = stones.size();
        int mx = stones[n - 1] - stones[0] + 1 - n;
        mx -= min(stones[n-1]-stones[n-2] - 1, stones[1]-stones[0] -1);
        int mi = mx;
        int i = 0;
        int j = 0;
        for(i = 0; i < n; ++i)
        {
            while(j + 1 < n && stones[j + 1] - stones[i] + 1 <= n)
                ++j;
            int cost = n - (j - i + 1);
            if(j - i + 1 == n - 1 && stones[j] - stones[i] + 1 == n - 1)
                cost = 2;
            mi = min(mi, cost);
        }
        return vector<int>{mi, mx};
    }
};


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

1041. 困于环中的机器人
      只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

一轮执行结束后，方向与初始方向一致（向北），并且不是位于初始地点（0，0），那么将永远不会循环；否则，一定会产生循环

class Solution {
public:
    bool isRobotBounded(string instructions) {
        vector<pair<int, int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int face = 0, x = 0, y = 0;
        for (int i = 0; i < instructions.size(); ++i) {
            if (instructions[i] == 'L') {
                face--;
            }
            else if (instructions[i] == 'R') {
                face++;
            }
            else {
                if (face < 0) {
                    face = 4 + (face % 4);
                }
                x += dir[face % 4].first;
                y += dir[face % 4].second;
            }
        }
        return (x == 0 && y == 0) || (face % 4 != 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

1042. 不邻接植花
      有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中，你打算种下四种花之一。另外，所有花园 最多 有 3 条路径可以进入或离开.你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。以数组形式返回 任一 可行的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1、2、3、4 表示。保证存在答案。

这里其实就是回溯的一个特例：因为题意保证了不会重复，所以没有试错的说法，只要遍历一遍基本就完事了。

class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>>node2nodes(n+1);
        for(int i=0;i<paths.size();i++){
            int node1=paths[i][0],node2=paths[i][1];
            node2nodes[node1].push_back(node2);
            node2nodes[node2].push_back(node1);
        }
        vector<int>ans;
        for(int i=1;i<=n;i++){
            auto &nextNodes=node2nodes[i];
            for(int flower=1;flower<=4;flower++){
                bool flag=false;
                for(auto&nextNode:nextNodes){
                    if(nextNode-1>=ans.size())continue;
                    if(ans[nextNode-1]==flower){
                        flag=true;
                        break;
                    }
                }
                if(flag==false){
                    ans.push_back(flower);
                    break;
                }
                
            }
        }
        return ans;
    }
};


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

1043. 分隔数组以得到最大和
      给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。返回将数组分隔变换后能够得到的元素最大和。

因为只能拆分子数组，所以用动态规划比较合理。当长度小于k的时候，dp可以直接乘最大值，当大于k的时候，需要考虑当前i和前面结合、不结合各种情况，需要用一个循环来取最大值才可

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n=arr.size();
        vector<int>dp(n,0);
        int curMax=arr[0];
        dp[0]=curMax;
        for(int i=1;i<k;i++){
            curMax=max(curMax,arr[i]);
            dp[i]=curMax*(i+1);
        }
        for(int i=k;i<n;i++){
            for(int j=i-k;j<i;j++){
                dp[i]=max(dp[i],dp[j]+*max_element(arr.begin()+j+1,arr.begin()+i+1)*(i-j));
            }
        }
        return dp[n-1];

    }
};

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

1044. 最长重复子串
      给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

二分查找 + Rabin-Karp 字符串编码

typedef pair<long long, long long> pll;
class Solution {
public:
    long long pow(int a, int m, int mod) {
        long long ans = 1;
        long long contribute = a;
        while (m > 0) {
            if (m % 2 == 1) {
                ans = ans * contribute % mod;
                if (ans < 0) {
                    ans += mod;
                }
            }
            contribute = contribute * contribute % mod;
            if (contribute < 0) {
                contribute += mod;
            }
            m /= 2;
        }
        return ans;
    }

    int check(const vector<int> & arr, int m, int a1, int a2, int mod1, int mod2) {
        int n = arr.size();
        long long aL1 = pow(a1, m, mod1);
        long long aL2 = pow(a2, m, mod2);
        long long h1 = 0, h2 = 0;
        for (int i = 0; i < m; ++i) {
            h1 = (h1 * a1 % mod1 + arr[i]) % mod1;
            h2 = (h2 * a2 % mod2 + arr[i]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }
        }
        // 存储一个编码组合是否出现过
        set<pll> seen;
        seen.emplace(h1, h2);
        for (int start = 1; start <= n - m; ++start) {
            h1 = (h1 * a1 % mod1 - arr[start - 1] * aL1 % mod1 + arr[start + m - 1]) % mod1;
            h2 = (h2 * a2 % mod2 - arr[start - 1] * aL2 % mod2 + arr[start + m - 1]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }

            // 如果重复，则返回重复串的起点
            if (seen.count(make_pair(h1, h2))) {
                return start;
            }
            seen.emplace(h1, h2);
        }
        // 没有重复，则返回-1
        return -1;
    }

    string longestDupSubstring(string s) {
        srand((unsigned)time(NULL));
        // 生成两个进制
        int a1 = random()%75 + 26;
        int a2 = random()%75 + 26;

        // 生成两个模
        int mod1 = random()%(INT_MAX - 1000000006) + 1000000006;
        int mod2 = random()%(INT_MAX - 1000000006) + 1000000006;
        int n = s.size();
        // 先对所有字符进行编码
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            arr[i] = s[i] - 'a';
        }
        // 二分查找的范围是[1, n-1]
        int l = 1, r = n - 1;
        int length = 0, start = -1;
        while (l <= r) {
            int m = l + (r - l + 1) / 2;
            int idx = check(arr, m, a1, a2, mod1, mod2);
            if (idx != -1) {
                // 有重复子串，移动左边界
                l = m + 1;
                length = m;
                start = idx;
            } else {
                // 无重复子串，移动右边界
                r = m - 1;
            }
        }
        return start != -1 ? s.substr(start, length) : "";
    }
};

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