力扣第 392 场周赛

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestMonotonicSubarray(vector<int>& nums) {
        vector<int> dp1(nums.size(), 1);
        vector<int> dp2(nums.size(), 1);
        int res = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] > nums[i-1]) dp1[i] = dp1[i-1]+1;
            else if(nums[i] < nums[i-1]) dp2[i] = dp2[i-1]+1;
            res = max(max(res, dp1[i]), dp2[i]);
        }
        return res;
    }
};

B

贪心去选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string getSmallestString(string s, int K) {
        // 计算第 a 个字母到第 b 个字母的距离
        auto dis = [&](int a, int b) 
        {
            return min((a - b + 26) % 26, (b - a + 26) % 26);
        };
        int n = s.size();
        string t;
        // 从第一个位置开始填，每个位置尽可能填入最小的字符
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < 26; j++) {
            int d = dis(j, s[i] - 'a');
            if (K >= d) {
                // 填入当前字符之后，距离不超出 K，直接填入
                K -= d;
                t.push_back(j + 'a');
                break;
            }
        }
        return t;
    }
};

C

两边排序修改即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    long long minOperationsToMakeMedianK(vector<int> &nums, int k) {
        ranges::sort(nums);
        long long ans = 0;
        int m = nums.size() / 2;
        if (nums[m] > k) 
        {
            for (int i = m; i >= 0 && nums[i] > k; i--) {
                ans += nums[i] - k;
            }
        } else {
            for (int i = m; i < nums.size() && nums[i] < k; i++) {
                ans += k - nums[i];
            }
        }
        return ans;
    }
};

D

来自 灵茶山艾府

2022 感恩勋章

由于可以讨论联通，又可以走重复边，AND 的性质是 AND 的数字越多，结果越小。最优方案是把 s 所在连通块内的边都走一遍。

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
class Solution {
    vector<int> fa, and_;

    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    };

public:
    vector<int> minimumCost(int n, vector<vector<int>> &edges, vector<vector<int>> &query) {
        fa.resize(n);
        iota(fa.begin(), fa.end(), 0);
        and_.resize(n, -1);
        for (auto &e: edges) {
            int x = find(e[0]);
            int y = find(e[1]);
            and_[y] &= e[2];
            if (x != y) {
                and_[y] &= and_[x];
                fa[x] = y;
            }
        }

        vector<int> ans;
        ans.reserve(query.size()); // 预分配空间
        for (auto &q: query) 
        {
            int s = q[0], t = q[1];
            ans.push_back(find(s) != find(t) ? -1 : and_[find(s)]);
        }
        return ans;
    }
};