暑假算法日记第四天

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

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

其他:

今日总结
往期打卡

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\ast 4\ast n)$
• 空间复杂度: $O(26)$

代码:

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



class Solution:
    def queryString(self, s: str, n: int) -> bool:
        if n == 1:
            return '1' in s

        m = len(s)
        k = n.bit_length() - 1
        if 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 True
            seen = set()
            mask = (1 << (k - 1)) - 1
            x = 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 + 1

        return check(k, n // 2 + 1, (1 << k) - 1) and check(k + 1, 1 << k, n)

总结

继续练习定长滑动窗口，学习了分组循环和python二进制操作

往期打卡

暑假算法日记第三天

暑假算法日记第二天

暑假算法日记第一天