发表更新算法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;
}


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

decltypetest

算法内容

本文件是 C++ decltype、引用折叠和数组形参退化的学习代码。

f 对比 decltype(++i)、decltype(i++) 和 decltype(&i) 的推导结果：前置自增表达式得到左值引用类型，后置自增表达式得到值类型，取地址得到指针类型。f1 观察数组作为函数参数时会退化为指针。f2 则通过左值引用、右值引用和 move 展示引用变量在 decltype 中的类型保持规则。这个文件重点不是算法题，而是验证 C++ 类型推导行为。

算法实现

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
#include<iostream>
#include<iomanip>
using namespace std;


int i = 0;
void f(decltype(++i) a, decltype(i++) b, decltype(&i) c) {
    a++;
    b++;
    (*c)++;
}
int arr[5] = {0};
void f1(decltype(arr) a) {
    cout << ios::hex << a << " " << a+1 <<  endl;
}

int &j = i;
int &n = j;
int &&k = move(i);
int &&m  = move(k);
void f2(decltype(j) a, decltype(k) b, decltype(m) c, decltype(n) d) {
    a++;
    b++;
    c++;
    d++;
    cout << a << " " << b << " " << c << " " << d << endl;

}

int main() {
    int a = 0, b = 0,c = 0, d = 0;
    f(a, b, &c);
    cout << a << " " << b << " " << c <<  endl;
    int brr[6] = {0};
    f1(brr);
    f2(a,move(b),move(c),d);
    cout << a << " " << b << " " << c << " " << d << endl;
    return 0;
}
发表更新算法2 分钟读完 (大约323个字)

k-min 第 k 小元素查找

算法内容

本文件实现基于快速选择思想的第 k 小元素查找。输入阶段会先用布尔数组去重，再在去重后的数组中查找第 k 小值。

partition 使用类似快速排序的双指针划分，把基准元素放到最终位置；searchK 根据基准位置和目标下标 k 的关系，只递归进入包含目标的半边区间，而不是完整排序。平均时间复杂度为 O(n)，最坏情况下为 O(n^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
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int partition(vector<int>& v, int l, int r) {
    int i = l;
    while(l<r) {
        while(r > l && v[r] >= v[i]) {
            r--;
        }
        swap(v[i], v[r]);
        i = r;
        while(r > l && v[l] <= v[i]) {
            l++;
        }
        swap(v[i], v[l]);
        i = l;
    }
    return i;
}

void searchK(vector<int>& v, int k, int l, int r) {
    //partition
    int n = partition(v,l,r);
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl<< n;
    cout << endl;
    //search
    if(n > k) {
        searchK(v, k, l, n-1);
    } else if(n < k) {
        searchK(v, k, n+1, r);
    }
}
int main() {
    int n,k;
    cin >> n;
    vector<int> v;
    vector<bool> has(1001, false);
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if(!has[x]) {
            has[x] = true;
            v.push_back(x);
        }
    }
    cin >> k;
    k--;
    searchK(v, k, 0, v.size()-1);
    cout << v[k];
    return 0;
}
发表更新算法2 分钟读完 (大约303个字)

d-进制反转素数

算法内容

本文件实现素数判断和进制反转判断。程序持续读取 n 和进制 d，判断 n 是否为素数，以及 n 在 d 进制下反转后的数是否也为素数。

initPrimes 预生成前 MAX_PRIME 个素数；isPrime 在素数表中二分查找目标数；reverse 按 d 进制逐位取余并重新累积，得到反转后的数。主循环输出 Yes 或 No。这个写法适合数值范围受控的题目；如果输入可能超过预生成素数表覆盖范围，则需要改成按平方根试除或扩大素数表。

算法实现

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
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

int reverse(int n, int d) {
    int res = 0;
    while(n != 0) {
        res *= d;
        res += n % d;
        n /= d;
    }
    return res;
}

const int MAX_PRIME = 10000;
int primes[MAX_PRIME] = {0};
int primeCount = 0;
void initPrimes() {
    primes[0] = 2;
    primes[1] = 3;
    primeCount = 2;
    for(int i = 5; primeCount < MAX_PRIME; i+=2) {
        primes[primeCount] = i;
        primeCount++;
        for(int j = 0; j < primeCount && primes[j]*primes[j] <= i; j++) {
            if(i%primes[j] == 0) {
                primeCount--;
                break;
            }
        }
    }
}

bool isPrime(int n) {
    int l = 0, r = primeCount;
    while(l <= r) {
        int mid = (r-l)/2 + l;
        if(primes[mid] == n) return true;
        else if(primes[mid] > n) r = mid-1;
        else l = mid+1;
    }
    return false;
}

int main() {
    int n, d;
    initPrimes();
    while(cin >> n >> d) {
        if(isPrime(n) && isPrime(reverse(n, d))) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}
发表更新算法2 分钟读完 (大约249个字)

C++ 析构函数中delete this

算法内容

本文件是 C++ 对象传值、指针对象生命周期和析构行为的学习代码。

代码定义类 A 和结构体 B，并尝试通过函数传值修改对象副本。main 中使用 new A 创建堆对象，再通过 delete a 触发析构。需要特别注意：A 的析构函数内部又执行 delete this，这会导致递归析构或重复释放，是未定义行为。这个例子可以作为理解对象生命周期风险的反面案例：析构函数里通常不应该 delete this。

算法实现

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
#include<iostream>
using namespace std;
class A {
    public:
    int a;
    int b;
    A(int a0, int b0) : a(a0), b(b0) {}
    ~A() {
        cout << "delete this" << endl;
        delete this;
    }
};

struct B
{
    int a;
    int b;
    B(int a0, int b0) : a(a0), b(b0) {}
};

void f1(A a, B b) {
    a.a = 5, a.b = 6;
    b.a = 5, b.b = 6;
}

int main() {
    A *a = new A(1,2);
    B b(1,2);
    // f1(a, b);
    cout << a->a << " " << a->b << endl;
    // cout << b.a << " " << b.b << endl;
    delete a;
    return 0;
}
发表更新算法1 分钟读完 (大约174个字)

多继承

算法内容

本文件演示 C++ 多继承和纯虚函数实现。

A 和 B 都是包含纯虚函数的抽象基类，C 同时继承二者，并分别实现 afun 和 bfun。main 创建 C 的对象后调用两个接口，输出对应返回值。这个例子用于观察一个派生类如何同时满足多个抽象接口，以及多继承下虚函数调用的基本形式。

算法实现

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 A {
    public:
    virtual int afun() = 0;
};

class B {
    public:
    virtual int bfun() = 0;
};

class C : public A, public B {
    public:
    virtual int afun() {
        return 0;
    }
    virtual int bfun() {
        return 1;
    }

};

#include<iostream>
using namespace std;

int main() {
    C c;
    int a = c.afun();
    int b = c.bfun();

    cout << a << b << endl;
    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
×