第 392 场 LeetCode 周赛题解

本文主要是介绍第 392 场 LeetCode 周赛题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

模拟：实现可以只求最长严格递增子数组即可

class Solution {public:int longestIncrementsubarray(vector<int> &nums) {int n = nums.size();int res = 1;for (int i = 0, j = 0; i < n; i = ++j) {while (j + 1 < n && nums[j + 1] > nums[j])j++;res = max(res, j - i + 1);}return res;}int longestMonotonicSubarray(vector<int> &nums) {int res = longestIncrementsubarray(nums);reverse(nums.begin(), nums.end());res = max(res, longestIncrementsubarray(nums));return res;}
};

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

贪心：尽可能将先前面的字符变小

class Solution {public:string getSmallestString(string s, int k) {for (int i = 0; i < s.size() && k; i++) {if (s[i] != 'a') {//s[i]可以变小int d = min(k, min(s[i] - 'a', 26 - (s[i] - 'a')));//s[i]的操作数k -= d;s[i] = min(s[i] - d, 'a' + (s[i] - 'a' + d) % 26);}}return s;}
};

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

排序+模拟：先将数组排序，设中位数的下标为 $mi d$ ， $n u m s [mi d]$ 需要 $∣ k - n u m s [mi d] ∣$ 次操作变为 $k$ 。顺序枚举 $n u m s [mi d + 1, n u m . s i ze () - 1]$ ，若 $n u m s [i]$ 比 $n u m s [i - 1]$ 小，则将 $n u m s [i]$ 变为 $n u m s [i - 1]$ 。逆序枚举 $n u m s [0, mi d - 1]$ ，若 $n u m s [i]$ 比 $n u m s [i + 1]$ 大，则将 $n u m s [i]$ 变为 $n u m s [i + 1]$ 。

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

D 带权图里旅途的最小代价

脑筋急转弯+并查集：先用并查集维护哪些节点在同一个连通分支，在同一分支的 $s_i$ 和 $t_i$ 的最小代价即为所在连通分支上所有边的按位与。

class Solution {public:vector<int> p;vector<int> cost;int find(int x) {//查找x所在分支的根节点if (p[x] == x)return x;return p[x] = find(p[x]);}void comb(int x, int y) {//合并x和y所在的分支int xx = find(x);int yy = find(y);if (xx != yy)p[yy] = xx;}vector<int> minimumCost(int n, vector<vector<int>> &edges, vector<vector<int>> &query) {p.resize(n);iota(p.begin(), p.end(), 0);//初始化：每个节点为一个分支for (auto &edge : edges)comb(edge[0], edge[1]);cost = vector<int>(n, (1 << 30) - 1);for (auto &edge : edges) {int root = find(edge[0]);cost[root] = cost[root] & edge[2];}vector<int> res;for (auto &q : query) {int r1 = find(q[0]), r2 = find(q[1]);if (r1 != r2)res.push_back(-1);elseres.push_back(cost[r1]);}return res;}
};