app网站怎么下载/博客推广的方法与技巧

• LeetCode笔记：Weekly Contest 338
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四

• 比赛链接：https://leetcode.com/contest/weekly-contest-338/

1. 题目一

给出题目一的试题链接如下：

• 2600. K Items With the Maximum Sum

1. 解题思路

这一题思路上就是按照优先级分配就行了，先给1，再给0，剩余如果还有不足的再从-1当中补足即可。

2. 代码实现

给出python代码实现如下：

class Solution:def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:return min(numOnes, k) - max(0, k-numOnes-numZeros)

提交代码评测得到：耗时45ms，占用内存13.8MB。

2. 题目二

给出题目二的试题链接如下：

• 2601. Prime Subtraction Operation

1. 解题思路

这一题我的思路就是greedy的减去prime，从左往右，令每一个数都在保证比前一个数更大的前提下减去一个最大的质数。

如果最后操作成功了，那么命题得证，反正必然不存在一个可行的方法。

2. 代码实现

给出python代码实现如下：

@lru_cache(None)
def get_primes(n):status = [0 for _ in range(n+1)]res = []for i in range(2, n+1):if status[i] == 1:continueres.append(i)for j in range(i, n+1, i):status[j] = 1return resclass Solution:def primeSubOperation(self, nums: List[int]) -> bool:primes = get_primes(1000)pre = 0for x in nums:if x <= pre:return Falsed = x-pre-1idx = bisect.bisect_right(primes, d)-1if idx == -1:pre = xelse:pre = x - primes[idx]return True

提交代码评测得到：耗时104ms，占用内存14MB。

3. 题目三

给出题目三的试题链接如下：

• 2602. Minimum Operations to Make All Array Elements Equal

1. 解题思路

这一题就是考察一个累积数组，对于array的总数为n，然后对任意一个值x，有k个值不大于这个数，其余数均大于这个值，那么，query的结果就是：

$$q=k\times x-\sum _{i=1}^k{a}_i+\sum _{i=k+1}^n{a}_i-(n-k)\times x$$

这个表达式用累计数组是可以快速求解的，因此命题得证。

2. 代码实现

给出python代码实现如下：

class Solution:def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:n = len(nums)nums = sorted(nums)s = [0] + list(accumulate(nums))def query(q):idx = bisect.bisect_right(nums, q)return (q * idx - s[idx]) + (s[-1]-s[idx] - q*(n-idx))return [query(q) for q in queries]

提交代码评测得到：耗时969ms，占用内存41.9MB。

4. 题目四

给出题目四的试题链接如下：

• 2603. Collect Coins in a Tree

这道题算是这次比赛最难的一道题了，加上本来这周就发烧，就懒得想这道题目了，感觉图的问题都还是蛮难的，唉……