LeetCode第 392 场周赛

有生之年第一场 LeetCode周赛，y神 就带我 AK 了，何其荣幸！
泪目…

100264. 最长的严格递增或递减子数组

模拟即可

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

class Solution {
public:
    int longestMonotonicSubarray(vector<int> &nums) {
        int n = nums.size();
        int ans = 1;
        int l = 0, r = l + 1;
        int c = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                c++;
                ans = max(c,ans);
            } else {
                c = 1;
            }
        }
        c = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                c++;
                ans = max(c,ans);
            } else {
                c = 1;
            }
        }
        return ans;
    }
};

int main() {
    Solution s;
//    vector<int> nums = {1, 4, 3, 3, 2};
//    vector<int> nums = {3, 3, 3, 3};
//    vector<int> nums = {1, 4, 3, 3, 2};
    cout << s.longestMonotonicSubarray(nums) << endl;
    return 0;
}

100242. 满足距离约束且字典序最小的字符串

模拟即可

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
// distance(s1, s2)
// calc min dis s1[i] s2[i]
// distance("ab", "cd") == 4
// distance("a", "z") == 1
// 你可以对字符串 s 执行 任意次 操作。在每次操作中，可以将 s 中的一个字母 改变 为 任意 其他小写英文字母。
// 可以得到的 字典序最小 的字符串 t ，且满足 distance(s, t) <= k

class Solution {
public:
    pair<int, char> c(char &c1, int k) {
        char cc;
        int dis = 0;
        if (c1 - 'a' < 'z' - c1 + 1) {
            dis = c1 - 'a';
            cc = c1 - dis;
        } else {
            dis = 'z' - c1 + 1;
            cc = (c1 - 'a' + dis) % 26 + 'a';
        }
        if (k >= dis) {
            return make_pair(dis, cc);

        } else {
            // all k
            if (c1 + k < c1 - k) {
                cc = c1 + k;
                dis = k;
            } else {
                cc = c1 - k;
                dis = k;
            }
            return make_pair(dis, cc);
        }
    }

    string getSmallestString(string s, int k) {
        for (auto &it: s) {
            // using min cost to
            auto [kk, cc] = c(it, k);
            k -= kk;
            it = cc;
            if (k == 0) { break; }
        }
        return s;
    }
};

int main() {
    Solution s;
//    cout << s.getSmallestString("zbbz", 3) << endl;
//    cout << s.getSmallestString("xaxcd", 4) << endl;
//    cout << s.getSmallestString("lol", 0) << endl;
    //"rn"
    //9
    // r s t u v w x y z a
    cout << s.getSmallestString("rn", 9) << endl;
    return 0;
}

3107. 使数组中位数等于 K 的最少操作数

排序，分类讨论，都是把前面或者后面堆成 k，这样中位数就是 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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class Solution {
public:
    long long minOperationsToMakeMedianK(vector<int> &nums, int k) {
        sort(nums.begin(), nums.end());
        int mid = nums.size() / 2;
        long long ans = 0;
        if (k == nums[mid]) {
            return 0;
        }
        if (k > nums[mid]) {
            for (int i = mid; i < nums.size(); ++i) {
                if (nums[i] < k) {
                    ans += k - nums[i];
                }
            }
        } else {
            for (int i = mid; i >= 0; --i) {
                if (nums[i] > k) {
                    ans += nums[i] - k;
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution s;
    vector<int> nums{2, 5, 6, 8, 5};
    cout << s.minOperationsToMakeMedianK(nums, 4) << endl;

    return 0;
}

100244. 带权图里旅途的最小代价

并查集
因为任何一个集合的与和一定是最小值，所以可以维护一个集合的最小值

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
class UnionFind {
public:
    vector<int> fa;
    vector<int> faMin;
    vector<int> faAnd;

    UnionFind(int n) : fa(n), faMin(n, INT_MAX), faAnd(n, INT_MAX) {
        iota(fa.begin(), fa.end(), 0); // Fill fa with 0 to n-1
    }

    int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    void merge(int from, int to, int val) {
        int x = find(from), y = find(to);
        if (x == y) {
            faAnd[x] &= val;
            faMin[x] = min(faMin[x], val);
            return;
        }
        fa[x] = y;
        faAnd[y] = faAnd[x] & faAnd[y] & val;
        faMin[y] = min({faMin[x], faMin[y], val});
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        UnionFind uf(n);
        for (auto& e : edges) {
            uf.merge(e[0], e[1], e[2]);
        }

        vector<int> ans(queries.size());
        for (size_t i = 0; i < queries.size(); ++i) {
            int x = queries[i][0], y = queries[i][1];

            if (x == y) {
                ans[i] = 0;
                continue;
            }
            if (!uf.same(x, y)) {
                ans[i] = -1;
                continue;
            }
            int f = uf.find(x);
            ans[i] = min(uf.faMin[f], uf.faAnd[f]);
        }
        return ans;
    }
};

int main() {
    Solution s;
    vector<vector<int>> edges{{0, 1, 7},
                              {1, 3, 7},
                              {1, 2, 1}};
    vector<vector<int>> query{{0, 3},
                              {3, 4}};
    vector<int> ans = s.minimumCost(5, edges, query);
    for (auto it: ans) {
        cout << it << ' ';
    }

    return 0;
}