网站建设优化服务机构seo门户网站建设方案
- LeetCode笔记：Weekly Contest 333
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 题目一
- 比赛链接：https://leetcode.com/contest/weekly-contest-333
1. 题目一
给出题目一的试题链接如下：
- 2570. Merge Two 2D Arrays by Summing Values
1. 解题思路
这一题我们只需要按照题目组合一下即可，用一个字典可以快速实现。
2. 代码实现
给出python代码实现如下：
class Solution:def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:s = defaultdict(int)for idx, v in nums1:s[idx] += vfor idx, v in nums2:s[idx] += v res = sorted([[k, v] for k, v in s.items()])return res
提交代码评测得到：耗时63ms，占用内存14.1MB。
2. 题目二
给出题目二的试题链接如下：
- 2571. Minimum Operations to Reduce an Integer to 0
1. 解题思路
这一题其实就是个迭代算法，我们将其转换为二进制数，那么只需要依次考察即可。
显然，末尾的0都可以忽略不计，剩下的对于末尾是1的情况，就只有两种情况，加一或者减一，我们分别考察这两者的最小值即可。
2. 代码实现
给出python代码实现如下：
class Solution:def minOperations(self, n: int) -> int:n = bin(n)[2:]@lru_cache(None)def dp(n):n = n.rstrip("0")if n == "1":return 1nxt = n.rstrip("1")nxt = "1" if nxt == "" else nxt[:-1] + "1"return 1 + min(dp(n[:-1]), dp(nxt))res = dp(n)return res
提交代码评测得到：耗时31ms，占用内存14.1MB。
3. 题目三
给出题目三的试题链接如下：
- 2572. Count the Number of Square-Free Subsets
1. 解题思路
这一题由于数字均不大于30，因此，我们首先用一个Counter来获取数组中出现过的数字以及其对应的频率，然后只需要考察这些数即可。
显然，如果某些数字可以被4、9或者25整除，那么这些数一定不可以被使用，我们可以先把这些数排除。
然后，我们考察30以下的全部质数，要想不出现平方数，那么质数最多只能被取到一次，因此，我们就可以快速地用一个动态规划搞定了。
最后，比较特殊的是，如果数组中存在有1，那么不但他们的任意组合都可以和其他数的组合一起存在，且即使其他数都不取，只要有至少一个1存在，也是一种可行的构建，这个需要单独考察一下。
2. 代码实现
给出python代码实现如下：
class Solution:def squareFreeSubsets(self, nums: List[int]) -> int:MOD = 10**9 + 7primes = [2,3,5,7,11,13,17,19,23,29]cnt = Counter(nums)keys = [x for x in cnt.keys() if x != 1 and x % 4 != 0 and x % 9 != 0 and x % 25 != 0]n = len(keys)def get_status(num):res = 0for p in primes:res = (res << 1) if num % p != 0 else (res << 1) + 1return resn = len(keys)@lru_cache(None)def dp(idx, status):if idx == n:return 0 if status == 0 else 1x = keys[idx]digits = get_status(x)if digits & status > 0:return dp(idx+1, status)else:return (dp(idx+1, status) + cnt[x] * dp(idx+1, status | digits)) % MODres = dp(0, 0)dup = 1for _ in range(cnt[1]):dup = (dup * 2) % MODres = (dup * res + dup-1) % MODreturn res
提交代码评测得到：耗时133ms，占用内存19.2MB。
4. 题目四
给出题目四的试题链接如下：
- 2573. Find the String with LCP
这一题同样没啥思路，唉，这周状态太差了，希望下周能够有所回升吧……