荆州网站建设公司,销售平台app,哪里有专门做gif的网站,工信部网站备案登录LeetCode笔记#xff1a;Weekly Contest 333 1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 比赛链接#xff1a;https://leetcode.com/contest/weekly-contest-333
1. 题目一
给出题目一的试题链接如下…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] 1return 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(idx1, status)else:return (dp(idx1, status) cnt[x] * dp(idx1, 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
这一题同样没啥思路唉这周状态太差了希望下周能够有所回升吧……
