结果与总结
这里是式酱～(∠・ω< )⌒☆
手速场久违的上一次大分，有幸再进了一次国服前十（还是板子题最适合我），好像可以重回前100了，希望不要被re掉。T1T2是简单的暴力，T3是一个比较简单的思维题，T4则是板子抽查题，如果有对应的板子这题做起来会非常迅速，如果是第一次做的话还是挺坐牢的（官方好像很喜欢出这种板子题，两个月前才考过，强烈建议补起来）。
6917. 满足目标工作时长的员工数目
水题，遍历扫一遍即可。
class Solution:
def numberOfEmployeesWhoMetTarget(self, hours: List[int], target: int) -> int:
return sum(x >= target for x in hours)6900. 统计完全子数组的数目
暴力的做法，先固定左端点，然后模拟往集合里面加数字即可，当集合长度等于整个数组不同元素的数目时，无需接着遍历，后面的子数组都满足答案要求。
时间复杂度
class Solution:
def countCompleteSubarrays(self, nums: List[int]) -> int:
n = len(nums)
le = len(set(nums))
ans = 0
for i in range(n):
s = set()
for j in range(i,n):
s.add(nums[j])
if len(s) == le:
ans += n - j
break
return ans思考复杂度更低的做法，滑动窗口的做法，固定右端点，尽可能大的把左端点移动，答案的贡献个数就是左边移动的长度。时间复杂度
class Solution:
def countCompleteSubarrays(self, nums: List[int]) -> int:
n = len(nums)
l,ans = 0,0
le = len(set(nums))
c = Counter()
for r in range(n):
c[nums[r]] += 1
while c[nums[l]] > 1:
c[nums[l]] -= 1
l += 1
if len(c) == le:
ans += l + 1
return ans6918. 包含三个字符串的最短字符串
很直观的一个想法，暴力找出最优拼接的所有结果，返回满足答案的那一个即可。
思考一个字符串拼接操作，让s1和s2都成为返回字符串s的子字符串（s1在前s2在后）。
当满足s2 in s1时，直接返回s1，否则我们考虑在s1后面添加字符满足s2是s的子字符串，暴力比对s1的后缀和s2的前缀，找到最长的公共部分，再往后添加剩余s2的字符即可。（这样拼接满足题意长度最小的优先级）
abca cabb 前后缀公共部分ca 拼接成abcabb长度最短
如果答案只要求返回字典序最小的一个，直接贪心按顺序拼接排序后的字符串即可，但是题意需要优先返回长度最小的，abc三个字符串最多只能组合出6种拼接方式，直接暴力枚举出来，然后找出长度最小字典序最小的即可。
时间复杂度
class Solution:
def minimumString(self, a: str, b: str, c: str) -> str:
def merge(s1,s2):
# 如果s2包含在s1里面那么就不需要拼在后面了
if s2 in s1:
return s1
# 靠后缀拼起来
for l in range(min(len(s1),len(s2)),0,-1):
if s1[-l:] == s2[:l]:
return s1[:-l] + s2
return s1 + s2
abc = merge(merge(a,b),c)
acb = merge(merge(a,c),b)
bac = merge(merge(b,a),c)
bca = merge(merge(b,c),a)
cab = merge(merge(c,a),b)
cba = merge(merge(c,b),a)
# 返回长度最小再字典序最小
return min([abc,acb,bac,bca,cab,cba],key=lambda x:(len(x),x))精简一下，排列的枚举可以调用库函数permutation。
class Solution:
def minimumString(self, a: str, b: str, c: str) -> str:
from itertools import permutations
def merge(s1,s2):
if s2 in s1:
return s1
for l in range(min(len(s1),len(s2)),0,-1):
if s1[-l:] == s2[:l]:
return s1[:-l] + s2
return s1 + s2
return min((merge(merge(x,y),z) for x,y,z in permutations([a,b,c],3)),key = lambda x:(len(x),x))算法的瓶颈在于字符串前后缀的暴力比对，用KMP求前后缀最长公共部分可以优化该算法。
时间复杂度
class Solution:
def minimumString(self, a: str, b: str, c: str) -> str:
from itertools import permutations
def merge(s1, s2):
if s2 in s1:
return s1
s = s2 + "#" + s1
# KMP
next = [0] * len(s)
for i in range(1, len(s)):
j = next[i - 1]
while j > 0 and s[i] != s[j]:
j = next[j - 1]
if s[i] == s[j]:
j += 1
next[i] = j
return s1 + s2[next[-1]:]
return min((merge(merge(x, y), z) for x, y, z in permutations([a, b, c], 3)), key=lambda x: (len(x), x))6957. 统计范围内的步进数字数目
数位dp板子抽查,348场周赛的T4才考过。
可以参考灵神大大的题解，如果把板子弄清楚了，那么这个题是可以秒杀的。
需要注意的地方是数字前导零之后的第一个数字是不需要判断条件的，用is_num判断前面是否都是前导零，如果不是再进行pre的比较。
时间复杂度
class Solution:
def countSteppingNumbers(self, low: str, high: str) -> int:
Mod = 10 ** 9 + 7
s1 = str(high)
s2 = str(low)
# 把s1和s2通过补0补到一样长，就可以一起计算了
s2 = '0' * (len(s1) - len(s2)) + s2
@cache
def f(i: int, pre: int, is_up_limit: bool, is_down_limit, is_num: bool) -> int:
if i == len(s1):
return 1
res = 0
up = int(s1[i]) if is_up_limit else 9
down = int(s2[i]) if is_down_limit else 0
for d in range(down, up + 1): # 枚举要填入的数字 d
if not is_num or d - pre in (-1, 1):
res += f(i + 1, d, is_up_limit and d == up, is_down_limit and d == down,
is_num or d > 0)
return res % Mod
return f(0, 0, True, True, False)写在最后
