[LeetCode周赛复盘] 第 376 场周赛20231217

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

一、本周周赛总结

• 原题我调了半天，太傻了。。
• T1 模拟。
• T2 捞币翻译，排序贪心模拟。
• T3 中位数定理+模拟/二分。
• T4 中位数定理+滑窗。

100149. 找出缺失和重复的数字

2. 思路分析

按题意模拟即可。

3. 代码实现

class Solution:def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:n = len(grid)b = set(range(1,n*n+1))cnt = Counter()for row in grid:for v in row:b.discard(v)cnt[v]+=1if cnt[v] == 2:a = vreturn [a, b.pop()]

100161. 划分数组并满足最大差限制

100161. 划分数组并满足最大差限制

1. 题目描述

2. 思路分析

翻译害人不浅，根本就不是子数组，原文是Divide the array into one or more arrays of size 3 satisfying the following conditions:

• 其实是分组，不要求连续，类似与子序列但可以重排。
• 那么排序贪心模拟即可，相邻的三个必须同组。

3. 代码实现

class Solution:def divideArray(self, nums: List[int], k: int) -> List[List[int]]:nums.sort()ret = []for i in range(0, len(nums), 3):if nums[i + 2] - nums[i] > k:return []ret.append(nums[i:i + 3])return ret

100151. 使数组成为等数数组的最小代价

100151. 使数组成为等数数组的最小代价

1. 题目描述

2. 思路分析

• 中位数定理。要让数组里的数都变成同一个数，总距离最小，那么就是变成中位数。
• 显然可以找到离中位数最近的那个回文数即可。
• 题目限制<1e9才是中位数，因此我们可以枚举中位数的一半，打表预处理所有中位数。然后在这个表里二分。

---

• 另外，由于两个回文数间距最大只有1e4级别，其实可以直接从中位数开始暴力向两边扩展。

3. 代码实现

biao=list(range(1,10))
for i in range(10**4):s = str(i)p = int(s + s[::-1])if p < 10**9:biao.append(p)for j in range(10):p = int(s +str(j)+ s[::-1])if p < 10**9:biao.append(p)
biao = sorted(set(biao))class Solution:def minimumCost(self, nums: List[int]) -> int:n = len(nums)nums.sort()pre = [0] + list(accumulate(nums))def f(x):p = bisect_left(nums,x)s = 0if p > 0:s += x*p - pre[p-1+1] + pre[0] if p < n:s += pre[n] - pre[p] - x*(n-p)return s ans = infp = bisect_left(biao,nums[(n-1)//2])if p:ans = f(biao[p-1])if p < len(biao):ans = min(ans,f(biao[p]))return ans        

class Solution {public int[][] divideArray(int[] nums, int k) {Arrays.sort(nums);List<int[]> ret = new ArrayList<>();for (int i = 0; i < nums.length; i += 3) {if (i + 2 < nums.length && nums[i + 2] - nums[i] > k) {return new int[][]{}; }int[] subArray = Arrays.copyOfRange(nums, i, Math.min(i + 3, nums.length));ret.add(subArray);}return ret.toArray(new int[0][]);}
}

100123. 执行操作使频率分数最大

[100123. 执行操作使频率分数最大

2. 思路分析

• 我可真菜啊，华子原题调这半天。
• 应用中位数定理+滑窗。
• 枚举右端点，左端点向左不合法的情况下，下一个右端点也必不合法，左端点可以右移。

3. 代码实现

class Solution:def maxFrequencyScore(self, nums: List[int], k: int) -> int:if k == 0:return max(Counter(nums).values())nums.sort()pre = [0] + list(accumulate(nums))n = len(nums)def f(l,r):mid = (l+r)//2p = nums[mid]*(mid-l+1) - (pre[mid+1] - pre[l])   + pre[r+1] - pre[mid] - nums[mid] * (r-mid+1)            return p <= kl = ans = 0for r in range(n):while not f(l,r):l += 1ans = max(ans, r - l + 1)return ans    

参考链接

这篇关于[LeetCode周赛复盘] 第 376 场周赛20231217的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---