【LeetCode周赛】第 392 场周赛

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

3105. 最长的严格递增或递减子数组简单

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

分析：
数据量小，根据题意进行暴力枚举即可。

代码：

CPP：

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

Python：

class Solution:def longestMonotonicSubarray(self, nums: List[int]) -> int:n, ans = len(nums), 0for i, x in enumerate(nums):lema, lemi = i - 1, i - 1while lema >= 0 and nums[lema] < nums[lema + 1]:lema -= 1while lemi >= 0 and nums[lemi] > nums[lemi + 1]:lemi -= 1ans = max( i - lema, i - lemi, ans )return ans

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

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

分析：
贪心，尽可能将字符串开始的字符变得更小，最小变为 a ，如果第一个字符变为了 a 则尽可能将第二个字符变更小，以此类推。

注意距离函数的书写，小写字母表是 循环顺序排列，即 z 到 a 的距离是 1。

代码：

CPP：

class Solution {
public:string getSmallestString(string s, int k) {if(k==0) return s;function<int(char a, char b)> dist = [&] (char a, char b) -> int {int res = min(abs(a - b), min('z' - a + 1 + b - 'a', 'z' - b + 1 + a - 'a'));return res;};int n = s.size();for(int i=0;i<n;i++){if(s[i]=='a') continue;int d = dist(s[i], 'a');if(d <= k) {s[i] = 'a';k -= d;}else{s[i] -= k;k=0;}if(k==0) break;}return s;}
};

Python：

class Solution:def getSmallestString(self, s: str, k: int) -> str:def dist(a: str, b: str):res = min(abs(ord(a) - ord(b)), abs(ord('z') - ord(a) + 1 + ord(b) - ord('a')), abs(ord('z') - ord(b) + 1 + ord(a) - ord('a')))return resans, index, n = "", 0, len(s)for i,x in enumerate(s):d = dist(x, 'a')if d <= k:ans += 'a'k -= delse:ans += chr(ord(s[i]) - k)k = 0index += 1if k == 0:breakif index <= n:ans += s[index:]return ans

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

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

分析：
先对数组进行升序排序。
根据贪心思想，可以知道，如果要将数组中位数设置为k，则从中位数开始增减。并对附近的数再进行增减，操作数是最小的。

若 nums[m] < k ，继续将后续中位数之后的，小于k的值增加到 k。
若 nums[m] > k ，继续将后续中位数之前的，大于k的值减小到 k。
若 nums[m] = k ，不需要进行任何操作。

代码：
CPP：

class Solution {
public:long long minOperationsToMakeMedianK(vector<int>& nums, int k) {ranges::sort(nums);int n = nums.size(), m = n/2;long long ans = 0;bool flag = true;if(nums[m] == k) return ans;else if(nums[m] > k) flag=false; while( m>=0&&!flag&&nums[m]>k || m<n&&flag&&nums[m]<k ){ans += 1LL*abs(nums[m] - k);m += flag?1:-1;}return ans;}
};

Python：

class Solution:def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:nums = sorted(nums)n = len(nums)m = n//2ans = 0if nums[m] == k:return ansflag = Trueif nums[m] > k:flag = not flagwhile m>=0 and not flag and nums[m]>k or m<n and flag and nums[m]<k :ans += abs(nums[m] - k)m += 1 if flag else -1return ans

3108. 带权图里旅途的最小代价困难

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

分析：

AND 的性质：越多数字相与，最终结果越小

根据 AND 的性质，我们尽可能的多走能走到的路。但是 x&x = x ，因此不重复走同一路径。可以利用并查集将能到达的点归于同一连通块，再统计每一个连通快对应的路径相与的结果。

代码：

class Solution {
public:vector<int> dsu;int find_dsu(int x){if(x == dsu[x]) return x;return dsu[x] = find_dsu(dsu[x]);}void union_dsu(int x, int y){x = find_dsu(x);y = find_dsu(y);if(x!=y) dsu[x]=y;}vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {dsu = vector<int>(n);unordered_map<int, int> m;for(int i=0;i<n;i++) dsu[i] = i;for(auto e : edges) union_dsu(e[0], e[1]);for(auto e : edges){int x = find_dsu(e[0]);m.emplace(x,-1); // m[x] 没有值则初始化为-1，否则 m[x] 值不变m[x] &= e[2];}vector<int> ans;for(auto q : query){if(q[0] == q[1]){ans.push_back(0);continue;}int a=find_dsu(q[0]), b=find_dsu(q[1]);int cnt = -1;if(a==b) {cnt = m[a];}ans.push_back(cnt);}return ans;}
};

class Solution:def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:dsu = [ i for i in range(n)]m = dict()def find_dsu(x: int) -> int:nonlocal dsuif dsu[x] != x:dsu[x] = find_dsu(dsu[x])return dsu[x]def union_dsu(x: int, y: int):nonlocal dsux, y = find_dsu(x), find_dsu(y)if x != y:dsu[x] = y for [x,y,_] in edges:union_dsu(x,y)for [x,_,v] in edges:k = find_dsu(x)if k not in m:m[k] = -1m[k] &= vans = []for [x,y] in query:if x == y:ans.append(0)continuea, b = find_dsu(x), find_dsu(y)if a!=b:ans.append(-1)else:ans.append(m[a])return ans