网站怎么做支付,非凡软件站,网络营销平台排名,水果网站策划书LeetCode笔记#xff1a;Weekly Contest 356 1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接#xff1a;https://leetcode.com/contest/weekly-contest-356/
1. 题目一…LeetCode笔记Weekly Contest 356 1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接https://leetcode.com/contest/weekly-contest-356/
1. 题目一
给出题目一的试题链接如下
2798. Number of Employees Who Met the Target
1. 解题思路
这一题思路上还是很直接的就是排序之后找到第一个不小于target的值所在的index即可。
2. 代码实现
给出python代码实现如下
class Solution:def numberOfEmployeesWhoMetTarget(self, hours: List[int], target: int) - int:hours sorted(hours)idx bisect.bisect_left(hours, target)return len(hours) - idx提交代码评测得到耗时48ms占用内存16MB。
2. 题目二
给出题目二的试题链接如下
2799. Count Complete Subarrays in an Array
1. 解题思路
这一题思路上就是一个滑动窗口将左窗口从左往右遍历然后在每一个位置寻找最小的右窗口位置使得其涵盖所有的元素此时后续所有的位置都能满足。然后我们将所有的答案加总即可。
2. 代码实现
给出python代码实现如下
class Solution:def countCompleteSubarrays(self, nums: List[int]) - int:n, m len(nums), len(set(nums))cnt {}i, j 0, 0res 0while i n:while j n and len(cnt) m:if nums[j] not in cnt:cnt[nums[j]] 1else:cnt[nums[j]] 1j 1if len(cnt) m:res n-j1else:breakcnt[nums[i]] - 1if cnt[nums[i]] 0:cnt.pop(nums[i])i 1return res提交代码评测得到耗时89ms占用内存16.6MB。
3. 题目三
给出题目三的试题链接如下
2800. Shortest String That Contains Three Strings
1. 解题思路
这一题我的思路多少还是有点暴力因为总共只有三个string因此我就直接考虑了全部的 3 ! 6 3!6 3!6个排列下的string的结果然后取出其中的最短结果即可。
2. 代码实现
给出python代码实现如下
class Solution:def minimumString(self, a: str, b: str, c: str) - str:lru_cache(None)def concat(s1, s2):if s1.find(s2) ! -1:return s1n, m len(s1), len(s2)l min(n, m)while l 0 and s1[-l:] ! s2[:l]:l - 1return s1 s2[l:]def fn(s1, s2, s3):s concat(s1, s2)return concat(s, s3)res sorted([fn(a,b,c), fn(a,c,b), fn(b,a,c), fn(b,c,a), fn(c,a,b), fn(c,b,a)], keylambda x: (len(x), x))return res[0]提交代码评测得到耗时212ms占用内存16.5MB。
4. 题目四
给出题目四的试题链接如下
2801. Count Stepping Numbers in Range
1. 解题思路
这一题同样思路上还是很清晰的就是实现上多少有点繁琐。
思路上其实就是将问题进行一下拆分要找出 [ a , b ] [a,b] [a,b]范围内的所有符合条件的数那么只需要分别找到不大于 b b b和 a − 1 a-1 a−1的符合条件的数然后两者相减即可。
因此问题本质上就变成了求不大于 n n n的一个stepping number然后要求这个数我们只需要用一个动态规划即可就是写起来需要注意两个点
当前的数是否已经有一个开始了当前的数是否可以允许超过原数 n n n当中的同位的数了
具体实现上多少有点繁琐大家自己看代码吧感觉就是细节想清楚就行……
2. 代码实现
给出python代码实现如下
MOD 10**9 7class Solution:lru_cache(None)def count_stepping_number(self, num):if num 0:return 1n len(num)lru_cache(None)def dp(k, pre, have_start, allow_bigger):if k 0:return 1res 0if have_start:if allow_bigger:if pre ! 9:res dp(k-1, pre1, True, True)else:if pre1 int(num[n-k]):res dp(k-1, pre1, True, True)elif pre1 int(num[n-k]):res dp(k-1, pre1, True, False)if allow_bigger:if pre ! 0:res dp(k-1, pre-1, True, True)else:if 0 pre-1 int(num[n-k]):res dp(k-1, pre-1, True, True)elif pre-1 int(num[n-k]):res dp(k-1, pre-1, True, False)else:res dp(k-1, pre, False, True)if k n:for i in range(1, int(num[0])):res dp(k-1, i, True, True)res dp(k-1, int(num[0]), True, False)else:for i in range(1, 10):res dp(k-1, i, True, True)return res % MODres dp(len(num), 0, False, False)return resdef minus_one(self, num):num [ch for ch in num]i len(num) - 1while num[i] 0:num[i] 9i - 1num[i] str(int(num[i]) - 1)res .join(num).lstrip(0)return res if res ! else 0def countSteppingNumbers(self, low: str, high: str) - int:low self.minus_one(low)res self.count_stepping_number(high) - self.count_stepping_number(low)res (res MOD) % MODreturn res提交代码评测得到耗时326ms占用内存21.5MB。
