LeetCode笔记：Weekly Contest 333

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

• 比赛链接：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

这一题同样没啥思路，唉，这周状态太差了，希望下周能够有所回升吧……