发表更新算法3 分钟读完 (大约417个字)

179. 最大数

算法内容

本文件实现 LeetCode 179「最大数」。目标是把一组非负整数重新排列，使拼接后的数字最大。

代码先将整数转换为字符串，再通过自定义比较函数排序。比较两个字符串时，本质上要判断 a + b 和 b + a 哪个更大，排序后顺序拼接即可。实现里手写了整数转字符串和较复杂的循环比较逻辑，并对全 0 的情况做了处理，避免返回多个前导 0。时间复杂度主要来自排序，为 O(n log n * L)，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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> snums;
        for(int n : nums) {
            snums.push_back(toString(n));
        }
        sort(snums.begin(), snums.end(), greater);
        string res = "";
        int len = snums.size();
        int i = 0;
        while(i < len && snums[i] == "0") {
            i++;
        }
        if(i > 0) i--;
        for(; i < len; i++) {
            res += snums[i];
        }
        return res;
    }

    string toString(int a) {
        if(a == 0) return "0";
        stack<int> sa;
        while(a != 0) {
            sa.push(a%10);
            a/=10;
        }
        string res = "";
        while(!sa.empty()) {
            res.push_back(sa.top() + '0');
            sa.pop();
        }
        return res;
    }
    
    static bool greater(string a, string b) {
        int na = a.length(), nb = b.length();
        int nc = na > nb ? nb : na;
        int i = 0,j = 0;
        int last_i = 0, last_j = 0;
        while(i < na && j < nb) {
            while(i < na && j < nb && a[i] == b[j]) {
                i++;
                j++;
            }
            if(i == na && j == nb) {
                return a > b;
            }
            if(i != na && j != nb) {
                i = last_i; j = last_j;
                break;
            } else {
                if(i == na) {
                    i = last_i;
                } else {
                    j = last_j;
                }
                last_i = i;
                last_j = j;
            }
        }
        // cout << "d " << i << " " << j << endl;
        // cout << "a " << a << " " << b << endl;
        while(i < na && j < nb) {
            // cout << "b " << a[i] << " " << b[j] << endl;
            // cout << "c " << i << " " << j << endl;
            if(a[i] > b[j]) {
                return true;
            } else if(a[i] < b[j]) {
                return false;
            }
            i++;
            j++;
        }
        return (na-i) > (nb-j);
        // return false;
    }

    void swap(int &a, int &b) {
        a = a+b;
        b = a-b;
        a = a-b;
    }
};
发表更新算法2 分钟读完 (大约258个字)

198. 打家劫舍

算法内容

本文件实现 LeetCode 198「打家劫舍」。问题要求在不能偷相邻房屋的限制下，获得最大金额。

代码采用自顶向下的记忆化搜索。maxRob(nums, i) 表示上一次选择位置为 i 后，从后续可选位置中能得到的最大收益；每次只尝试选择 i + 2 或 i + 3，用 mem[i + 2] 缓存状态结果。入口从 -2 开始，等价于还没有选择任何房屋。时间复杂度 O(n)，空间复杂度 O(n)。文件中的 main 用一组样例数据做本地验证。

算法实现

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
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<climits>
#include<set>
using namespace std;

class Solution {
public:
    int n;
    vector<int> mem;
    int rob(vector<int>& nums) {
        this->n = nums.size();
        mem = vector<int>(n+2, -1);
        return maxRob(nums, -2);
    }
    int maxRob(const vector<int>& nums, int i) {
        if(i < n && mem[i+2] != -1) return mem[i+2];
        int a = (i+2 < n ? maxRob(nums, i+2) + nums[i+2] : 0);
        int b = (i+3 < n ? maxRob(nums, i+3) + nums[i+3] : 0);
        mem[i+2] = (a > b? a : b);
        return mem[i+2];
    }
};

int main() {
    Solution s;
    vector<int> v = {226,174,214,16,218,48,153,131,128,17,157,142,88,43,37,157,43,221,191,68,206,23,225,82,54,118,111,46,80,49,245,63,25,194,72,80,143,55,209,18,55,122,65,66,177,101,63,201,172,130,103,225,142,46,86,185,62,138,212,192,125,77,223,188,99,228,90,25,193,211,84,239,119,234,85,83,123,120,131,203,219,10,82,35,120,180,249,106,37,169,225,54,103,55,166,124};
    cout << v.size() << endl;
    cout << s.rob(v) << endl;
    return 0;
}
发表更新算法3 分钟读完 (大约522个字)

2049. 统计最高分的节点数目

算法内容

本文件实现 LeetCode 2049「统计最高分的节点数目」。题目要求删除每个节点后，计算剩余各连通块大小的乘积，并统计最高分节点数量。

第一版使用 unordered_map<int, vector<int>> 建树，先通过 DFS 计算每个节点子树大小，再枚举节点计算分数：父侧连通块大小为 n - size[i]，每个子树连通块大小为对应子节点的 size。SolutionBetter 针对二叉树性质，用 vector<pair<int, int>> 保存左右孩子，避免 map 和动态 vector 带来的额外开销。整体时间复杂度 O(n)，空间复杂度 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
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<climits>
#include<set>
using namespace std;

class Solution {
public:
    template<class T>
    void printVec(const vector<T> &v, const string& head = "") {
        if(head != "") {
            cout << head << ": ";
        }
        for (T i : v) {
            cout << i << " ";
        }
        cout << "\n";
    }
    vector<int> size;
    vector<int> parents;
    unordered_map<int, vector<int>> children;
    int n;
    long long max = LONG_LONG_MIN;
    int maxn = 0;
    int countHighestScoreNodes(vector<int>& parents) {
        int n = parents.size();
        this->parents = parents;
        this->size = vector<int>(n, 1);
        this->n = n;
        for(int i = 0; i < n; i++) {
            getG(i);
        }
        getSize(0);
        for(int i = 0; i < n; i++) {
            calScore(i);
        }
        return maxn;

    }


    int getSize(int root) {
        int childNum = children[root].size();
        if(childNum == 0) {
            size[root] = 1;
        } else if(childNum == 1) {
            size[root] += getSize(children[root][0]);
        } else {
            size[root] += getSize(children[root][0]) + getSize(children[root][1]);
        }
        return size[root];
    }

    void calScore(int i) {
        int parent = parents[i];
        long long res = (parent == -1) ? 1 : (size[0] - size[i]);
        vector<int>& childi = children[i];
        for(int child : childi) {
            res *= size[child];
        }
        if(res > max) {
            max = res;
            maxn = 1;
        } else if(res == max) {
            maxn++;
        }
    }

    void getG(int i) {
        int parent = parents[i];
        if(parent == -1) {
            return;
        } else {
            children[parent].push_back(i);
        }
    }
};

int main() {
    Solution s;
    vector<int> v = {-1,2,0,2,0};
    cout << s.countHighestScoreNodes(v) << endl;
    return 0;
}

class SolutionBetter {
    //不使用map和set
public:
    vector<int> parents;
    vector<pair<int, int>> children;
    vector<int> size;
    int n;
    long long max = LONG_LONG_MIN;
    int maxn = 0;
    int countHighestScoreNodes(vector<int>& parents) {
        int n = parents.size();
        this->parents = parents;
        this->children = vector<pair<int, int>>(n, {-1,-1});
        this->size = vector<int>(n, 1);
        this->n = n;
        for(int i = 0; i < n; i++) {
            int parent = parents[i];
            if(parent == -1) {
                continue;
            } else {
                if(children[parent].first == -1) {
                    children[parent].first = i;
                } else {
                    children[parent].second = i;
                }
            }
        }
        getSize(0);
        for(int i = 0; i < n; i++) {
            int parent = parents[i];
            long long res = (parent == -1) ? 1 : (size[0] - size[i]);
            pair<int, int>& childi = children[i];
            res *= childi.first != -1 ? size[childi.first] : 1;
            res *= childi.second != -1 ? size[childi.second] : 1;
            if(res > max) {
                max = res;
                maxn = 1;
            } else if(res == max) {
                maxn++;
            }
        }
        return maxn;

    }


    int getSize(int root) {
        pair<int, int> child = children[root];
        int a = 0, b = 0;
        if(child.first != -1) {
            a = getSize(child.first);
        }
        if(child.second != -1) {
            b = getSize(child.second);
        }
        size[root] = 1 + a + b;
        return size[root];
    }
};

发表更新算法2 分钟读完 (大约343个字)

2055. 蜡烛之间的盘子

算法内容

本文件实现 LeetCode 2055「蜡烛之间的盘子」。目标是对多个区间查询，统计区间内两根蜡烛之间的盘子数量。

代码预处理三个数组：v 为盘子数量前缀和，left[i] 表示位置 i 左侧最近蜡烛下标，right[i] 表示位置 i 右侧最近蜡烛下标。对于查询 [l, r]，先找到 right[l] 和 left[r] 作为区间内最靠内的两根蜡烛，如果左蜡烛在右蜡烛左侧，就用前缀和相减得到盘子数。预处理 O(n)，每次查询 O(1)，总复杂度 O(n + q)。

算法实现

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
#include<vector>
#include<iostream>
#include<stack>

using namespace std;


class Solution {
public:
    vector<int> platesBetweenCandles(string s, const vector<vector<int>>& queries) {
        int len = s.length();
        vector<int> v(len, 0);
        vector<int> left(len, -1);
        vector<int> right(len, len);
        v[0] = s[0] == '*' ? 1 : 0; 
        int lastLeft = s[0] == '|' ? 0 : -1;
        left[0] = lastLeft;
        for(int i = 1; i < len; i++) {
            int x = s[i] == '*' ? 1 : 0;
            v[i] = v[i-1] + x;
            if(s[i] == '|') {
                lastLeft = i;
            }
            left[i] = lastLeft;
        }
        int lastRight = s[len-1] == '|' ? len-1 : len;
        for(int i = len-2; i >= 0; i--) {
            if(s[i] == '|') {
                lastRight = i;
            }
            right[i] = lastRight;
        }
        vector<int> ans;
        len = queries.size();
        for(int i = 0; i < len; i++) {
            int diff = 0;
            printf("%d, %d\n", right[queries[i][0]], left[queries[i][1]]);
            printf("%d, %d\n", v[right[queries[i][0]]], v[left[queries[i][1]]]);
            if(right[queries[i][0]] < left[queries[i][1]]) {
                diff = v[left[queries[i][1]]] - v[right[queries[i][0]]];
            }
            ans.push_back(diff);
        }
        return ans;
    }
};

int main() {
    Solution s;
    string str = "***|**|*****|**||**|*";
    vector<int> res = s.platesBetweenCandles(str, {{1,17},{4,5},{14,17},{5,11},{15,16}});
    int len = res.size();
    for(int i = 0; i < len; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}
发表更新算法2 分钟读完 (大约269个字)

207. 课程表

算法内容

本文件实现 LeetCode 207「课程表」。问题可以转化为判断有向图中是否存在环。

代码使用拓扑排序。m 数组统计每门课的入度，g 存储从先修课程指向后续课程的邻接表。先把所有入度为 0 的课程入栈，然后不断弹出课程并降低后继节点入度；当某个后继入度降为 0 时继续入栈。最后如果存在未访问课程，说明图中有环，无法完成所有课程。时间复杂度 O(V + E)，空间复杂度 O(V + E)。

算法实现

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
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> m(numCourses, 0);
        vector<bool> visited(numCourses, false);
        unordered_map<int, vector<int>> g;
        for(vector<int>& p:prerequisites) {
            m[p[0]]++;
            g[p[1]].push_back(p[0]);
        }
        bool find = true;
        stack<int> s;
        for(int i = 0; i < numCourses; i++) {
            if(m[i] == 0) {
                s.push(i);
                visited[i] = true;
            }
        }
        while(!s.empty()) {
            int pos = s.top();
            s.pop();
            vector<int> arcs = g[pos];
            for(int arc : arcs) {
                m[arc]--;
                if(m[arc] == 0) {
                    s.push(arc);
                    visited[arc] = true;
                }
            }
        }
        for(bool visit:visited) {
            if(!visit) {
                return false;
            }
        }
        return true;
    }
};
发表更新算法4 分钟读完 (大约560个字)

399. 除法求值

算法内容

本文件实现 LeetCode 399「除法求值」。方程 a / b = value 可以看作带权有向图中的两条边：a -> b 权重为 value，b -> a 权重为倒数。

代码先构建变量名到节点索引的映射，并为每个变量维护相邻节点和边权。查询时，如果变量不存在返回 -1；如果起点终点相同返回 1；否则从起点做图搜索，沿路径累计乘积，找到目标节点时返回路径权重乘积。构图复杂度 O(E)，单次查询最坏 O(V + E)。文件中还包含打印图结构和本地测试的辅助代码。

算法实现

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


#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>

using namespace std;

struct GraphNode {
    string name;
    vector<GraphNode*> children;
    unordered_map<string, double> values;

    void addChildren(GraphNode* node, double val) {
        children.push_back(node);
        values[node->name] = val;
    }
    GraphNode(string name0): name(name0) {}
};

class Solution {
public:
    unordered_map<string, int> index;
    vector<GraphNode*> g;
    int len;
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int equationNum = equations.size();
        int count = 0;
        for(int i = 0; i < equationNum; i++) {
            string node1Name = equations[i][0],node2Name = equations[i][1];
            double value1 = values[i], value2 = 1/values[i];
            GraphNode *node1, *node2;
            if(index.count(node1Name) == 0) {
                node1 = new GraphNode(node1Name);
                index[node1Name] = count++;
                g.push_back(node1);
            } else {
                node1 = g[index[node1Name]];
            }
            if(index.count(node2Name) == 0) {
                node2 = new GraphNode(node2Name);
                index[node2Name] = count++;
                g.push_back(node2);
            } else {
                node2 = g[index[node2Name]];
            }
            
            node1->addChildren(node2, value1);
            node2->addChildren(node1, value2);
        }
        printG();
        len = g.size();
        vector<double> res;
        for(auto query : queries) {
            res.push_back(search(query[0], query[1]));
        }
        return res;
    }

    void printG() {
        for(auto node : g) {
            cout << node->name << ": ";
            int size = node->children.size();
            for(int i = 0; i < size; i++) {
                cout << "(" << node->children[i]->name << " | " << node->values[node->children[i]->name] << "), ";
            }
            cout << endl;
        }
        
    }

    double search(const string& s, const string& e) {
        // printf("%s -> %s\n", s.c_str(), e.c_str());
        if(index.count(e) == 0 || index.count(s) == 0) return -1.0;
        int target = index[e];
        int start = index[s];
        if(start == target) return 1.0;
        vector<bool> visited(len, false);
        stack<pair<int, double>> q;
        q.push(pair<int, double>(start, 1.0));
        visited[start] = true;
        double res = 1.0;
        while(!q.empty()) {
            int nodeIndex = q.top().first;
            double val = q.top().second;
            res *= val;
            GraphNode* node = g[nodeIndex];
            bool add = false;
            // printf("node %s\n", node->name.c_str());
            q.pop();
            for(GraphNode* child : node->children) {
                int childIndex = index[child->name];
                if(childIndex == target) {
                    return res * node->values[child->name];
                } else if(!visited[childIndex]) {
                    q.push(pair<int, double>(childIndex, node->values[child->name]));
                    visited[childIndex] = true;
                    add = true;
                }
            }
            if(!add) {
                res /= val;
            }
        }
        return -1.0;
    }
};

template<class T>
void printVec(const vector<T> &v, const string& head = "")
{
    if(head != "") {
        cout << head << ": ";
    }
    for (T i : v)
    {
        cout << i << " ";
    }
    cout << "\n";
}
int main() {
    Solution s;
    vector<vector<string>> equations = {{"a","e"},{"b","e"}};
    vector<double> values = {4.0,3.0};
    vector<vector<string>> queries = {{"a","b"},{"e","e"},{"x","x"}};
    vector<double> res = s.calcEquation(equations, values, queries);
    printVec<double>(res, "result = ");
    return 0;
}
发表更新算法4 分钟读完 (大约581个字)

546. 移除盒子

算法内容

本文件尝试解决 LeetCode 546「移除盒子」。题目要求每次移除一段连续同色盒子并获得长度平方分数，求最大总分。

代码先把连续相同颜色压缩成链表节点，每个节点记录颜色和连续数量；随后根据某种启发式规则选择颜色进行删除，并在删除后合并相邻同色段。这个实现更像一次贪心尝试：优先选取剩余数量差值较小的颜色，而不是经典题解中的区间动态规划。因此它有助于理解压缩连续段和链表合并操作，但不能保证得到全局最优解。标准解法通常使用三维 DP dp[l][r][k] 表示区间和右侧同色累积数量。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<climits>
using namespace std;
struct Node {
    int n, cur;
    Node* next;
    Node(int n0, int cur0) : n(n0), cur(cur0) {
        next = nullptr;
    }
};

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        Node* head = new Node(0,0);
        Node* move = head;
        int i = 0;
        int len = boxes.size();
        int total[101] = {0};
        while(i < len) {
            int cur = boxes[i];
            int n = 0;
            while(i < len && cur == boxes[i]) {
                n++;
                i++;
                total[cur]++;
            }
            move->next = new Node(n, cur);
            move = move->next;
        }

        
        int min = INT_MAX;
        int minn = INT_MAX;
        int maxt = INT_MIN;
        int minBox = 0;
        move = head;
        while(move->next != nullptr) {
            int diff = total[move->next->cur] - move->next->n;
            if(min > diff) {
                maxt = total[move->next->cur];
                min = diff;
                minBox = move->next->cur;
                minn = move->next->n;
            } else if(min == diff) {
                if(maxt < total[move->cur]) {
                    maxt = total[move->next->cur];
                    min = diff;
                    minBox = move->next->cur;
                    minn = move->next->n;
                } else if(maxt == total[move->cur]) {
                    if(minn > move->n) {
                        min = diff;
                        maxt = total[move->cur];
                        minBox = move->cur;
                        minn = move->n;
                    }
                }
            }
            move = move->next;
        }
        cout << "minbox = " << minBox << endl;
        int res = 0;
        while(head->next != nullptr) {
            move = head;
            int newMin = INT_MAX;
            int newMinn = INT_MAX;
            int newMinNode = 0;
            int maxt = INT_MIN;
            while(move != nullptr && move->next != nullptr) {
                if(move->next->cur == minBox) {
                    Node* node = move->next;
                    move->next = node->next;
                    if(move->next != nullptr && move->cur == move->next->cur) {
                        move->n += move->next->n;
                        move->next = move->next->next;
                    }
                    res += node->n * node->n;
                } else {
                    move=move->next;
                }
                if(move == nullptr) break;
                int diff = total[move->cur] - move->n;
                cout << "diff : " << move->cur << " = " << diff << endl;
                if(newMin > diff) {
                    newMin = diff;
                    maxt = total[move->cur];
                    newMinNode = move->cur;
                    newMinn = move->n;
                } else if(newMin == diff) {
                    if(maxt < total[move->cur]) {
                        newMin = diff;
                        maxt = total[move->cur];
                        newMinNode = move->cur;
                        newMinn = move->n;
                    } else if(maxt == total[move->cur]) {
                        if(newMinn > move->n) {
                            newMin = diff;
                            maxt = total[move->cur];
                            newMinNode = move->cur;
                            newMinn = move->n;
                        }
                    }
                }
                
            }
            minBox = newMinNode;
            cout << "minbox = " << minBox << endl;
        }
        return res;
    }
};

int main() {
    Solution s;
    vector<int> v = {5,8,3,8,4,8,5,7,4,2};
    int res = 18;
    int ret = s.removeBoxes(v);
    cout << "ret = " << ret << " res = " << res << " " << (res == ret) << endl;
    return 0;
}


发表更新算法2 分钟读完 (大约305个字)

669. 修剪二叉搜索树

算法内容

本文件实现 LeetCode 669「修剪二叉搜索树」。目标是删除 BST 中所有不在 [low, high] 范围内的节点，并保持剩余结构仍为二叉搜索树。

代码利用 BST 性质：如果当前根值大于 high，合法节点只可能在左子树；如果当前根值小于 low，合法节点只可能在右子树。find(TreeNode** root) 通过二级指针直接修改父节点指向，先把当前根调整到合法范围，再递归修剪左右子树。每个节点最多访问一次，时间复杂度 O(n)，递归空间复杂度 O(h)。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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) {}
};


#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    int low, high;
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        this->low = low;
        this->high = high;
        find(&root);
        return root;
    }

    bool valid(const int& i) {
        return i>= low && i <= high;
    }

    void find(TreeNode** root) {
        while((*root) != nullptr && !valid((*root)->val)){
            if((*root)->val > high) {
                *root = (*root)->left;
            } else if((*root)->val < low) {
                *root = (*root)->right;
            }
        }
        if((*root) == nullptr) return;
        if((*root)->left != nullptr) {
            find(&((*root)->left));
        }
        if((*root)->right != nullptr) {
            find(&((*root)->right));
        }
    }
};
发表更新算法2 分钟读完 (大约269个字)

798. 得分最高的最小轮调

算法内容

本文件实现 LeetCode 798「得分最高的最小轮调」。旋转后，如果元素值不大于它的新下标，该元素得 1 分，要求返回得分最高且下标最小的旋转值。

代码使用差分数组记录每个元素在哪些旋转区间内可以得分。对位置 i 的元素 nums[i]，计算它得分的旋转区间 [low, high)，在差分数组中做区间加一；当区间跨过 0 时额外给 diff[0] 加一。最后对差分数组求前缀和，得到每个旋转值的总分，并保留第一次出现的最大值位置。时间复杂度 O(n)，空间复杂度 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
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    int bestRotation(vector<int>& nums) {
        int len = nums.size();
        vector<int> diff(len, 0);
        for(int i = 0; i < len; i++) {
            int low = (i+1)%len, high = (len + i - nums[i] + 1) % len;
            diff[low]++;
            diff[high]--;
            if(low >= high) {
                diff[0]++;
            }
        }
        int max = 0;
        int cur = 0;
        int pos = 0;
        for(int i = 0; i < len; i++) {
            cur += diff[i];
            if(max < cur) {
                pos = i;
                max = cur;
            }
        }
        return pos;
    }
};
发表更新算法2 分钟读完 (大约362个字)

KY191 矩阵幂

算法内容

本文件实现牛客 KY191「矩阵幂」的一个基础版本。程序读取矩阵阶数 n 和幂次 k，再读取 n 阶矩阵并输出矩阵的 k 次幂。

mul 完成普通矩阵乘法，并把结果写回第一个矩阵；matPow 根据 pow 的取值执行固定次数的乘法。当前实现只显式处理 1 到 5 次幂，适合题目幂次范围较小或练习矩阵乘法流程的场景。矩阵乘法单次时间复杂度 O(n^3)。如果 k 更大，通常需要改为快速幂，将复杂度优化为 O(n^3 log k)。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<unordered_map>

using namespace std;

void mul(vector<vector<int>>& a, const vector<vector<int>> b, int n) {
    for(int i = 0; i < n; i++) {
        vector<int> ta;
        for(int j  = 0; j < n; j++) {
            int m = 0;
            for(int k = 0; k < n; k++) {
                m += a[i][k] * b[k][j];
            }
            ta.push_back(m);
        }
        a[i] = ta;
    }
}

void matPow(int n, vector<vector<int>>& res, const vector<vector<int>>& arr, int pow) {
    switch(pow) {
        case 1:
            break;
        case 2:
            mul(res, arr, n);
            break;
        case 3:
            mul(res, arr, n);
            mul(res, arr, n);
            break;
        case 4:
            mul(res, arr, n);
            mul(res, res, n);
            break;
        case 5:
            mul(res, arr, n);
            mul(res, res, n);
            mul(res, arr, n);
            break;
    }
}
int main() {
    int n, k;
    while(scanf("%d%d", &n, &k) != EOF){
        vector<vector<int>> arr(n, vector<int>(n, 0));
        vector<vector<int>> res(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int t;
                scanf("%d", &t);
                res[i][j] = t;
                arr[i][j] = t;
            }
        }
        matPow(n, res, arr, k);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n-1; j++) {
                printf("%d ", res[i][j]);
            }
            printf("%d\n", res[i][n-1]);
        }
        
    }
    return 0;
}


关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码6
Android车载1
Android面试查漏补缺2
C#9
C/C++1
CSharp9
Flutter1
Java基础 字节码2
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery6
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法69
×