LeetCode笔记：Weekly Contest 356

• 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-j+1else: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$个排列下的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)], key=lambda x: (len(x), x))return res[0]

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

4. 题目四

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

• 2801. Count Stepping Numbers in Range

1. 解题思路

这一题同样思路上还是很清晰的，就是实现上多少有点繁琐。

思路上其实就是将问题进行一下拆分，要找出$[a,b]$范围内的所有符合条件的数，那么只需要分别找到不大于$b$和$a-1$的符合条件的数，然后两者相减即可。

因此问题本质上就变成了求不大于$n$的一个stepping number，然后要求这个数，我们只需要用一个动态规划即可，就是写起来需要注意两个点：

1. 当前的数是否已经有一个开始了
2. 当前的数是否可以允许超过原数$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, pre+1, True, True)else:if 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)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] = "9"i -= 1num[i] = str(int(num[i]) - 1)res = "".join(num).lstrip("0")return res if res != "" else "0"def 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。