当前位置：首页 > news >正文

暑假算法日记第四天

news 2025/7/12 20:06:38

目标：刷完灵神专题训练算法题单

阶段目标📌：【算法题单】滑动窗口与双指针

LeetCode题目:

2953. 统计完全子字符串
1016. 子串能表示从 1 到 N 数字的二进制串

其他:

今日总结
往期打卡

2953. 统计完全子字符串

跳转: 2953. 统计完全子字符串

学习: 题解

问题:

给你一个字符串 word 和一个整数 k 。

如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串：

s 中每个字符恰好出现 k 次。
相邻字符在字母表中的顺序至多相差 2 。也就是说，s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差至多为 2 。

请你返回 word 中完全子字符串的数目。

子字符串 指的是一个字符串中一段连续非空的字符序列。

思路:

从k长的窗口开始,2k,3k长依此遍历求字典值全是k的情况计数不难想
因为相邻差至多为2，所以遍历整个数组要维护窗口相邻差最值
用分组循环从边界切开分段求能简化计算同时降低复杂度

一共26个小写字母，所以哪怕长度大于26 * k也不需要再遍历
每个字符k次除了直接遍历一遍字典还可以维护字典中值为k的数量

复杂度:

时间复杂度: $O (26 * 4 * n)$
空间复杂度: $O (26)$

代码:

class Solution:def countCompleteSubstrings(self, word: str, k: int) -> int:def f(s:list) -> int:ans = 0for size in range(1,27):    # 26个字母，所以最多不会超过26，后面的都不用算j = size * kif j > len(s):breakcnt = Counter(s[:j])count = 0for i in cnt.values():if i == k:count += 1if count == size:   # 因为和是j，所以统计cnt里的k对上size即可ans += 1for i,ch in enumerate(s[j:]):if cnt[ch] == k:count -= 1cnt[ch] = cnt.get(ch,0) + 1if cnt[ch] == k:count += 1if cnt[s[i]] == k:count -= 1cnt[s[i]] -= 1if cnt[s[i]] == k:count += 1if count == size:ans += 1return ansi = ans = 0n = len(word)while i in range(n):    # 分组循环start = ii += 1while i < n and abs(ord(word[i])-ord(word[i - 1])) <= 2:i += 1ans += f(word[start:i])return ans

1016. 子串能表示从 1 到 N 数字的二进制串

跳转: 1016. 子串能表示从 1 到 N 数字的二进制串

学习: 题解

问题:

给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回 true，否则返回 false 。

子字符串 是字符串中连续的字符序列。

思路:

对于去除前导0的二进制串，更长的串集合整体右移一位完全可以覆盖更短的串
于是可以用滑动窗口遍历最长的串集合
但由于n不一定是2的幂-1或-2，即最长的串集合一般不全，所以确保不漏，除了最长的次长的二进制串也要遍历

即以n的二进制长-1为k，在s上求 k 长和 k+1 长的滑动窗口

复杂度:

时间复杂度: $O (m)$
空间复杂度: $O (min (m, n))$

代码:

# class Solution:
#     def queryString(self, s: str, n: int) -> bool:
#         set_ = set()
#         s = list(map(int,s))
#         for i,num in enumerate(s):
#             if num == 0: continue
#             j = i + 1
#             while num <= n:
#                 set_.add(num)
#                 if j == len(s): break
#                 num = num << 1 | s[j]
#                 j += 1
#         return len(set_) == nclass Solution:def queryString(self, s: str, n: int) -> bool:if n == 1:return '1' in sm = len(s)k = n.bit_length() - 1if m < max(n - (1 << k) + k + 1, (1 << (k - 1)) + k - 1):return False# 对于长为 k 的在 [lower, upper] 内的二进制数，判断这些数 s 是否都有def check(k: int, lower: int, upper: int) -> bool:if lower > upper: return Trueseen = set()mask = (1 << (k - 1)) - 1x = int(s[:k - 1], 2)for c in s[k - 1:]:# & mask 可以去掉最高比特位，从而实现滑窗的「出」# << 1 | int(c) 即为滑窗的「入」x = ((x & mask) << 1) | int(c)if lower <= x <= upper:seen.add(x)return len(seen) == upper - lower + 1return check(k, n // 2 + 1, (1 << k) - 1) and check(k + 1, 1 << k, n)