目標?：刷完靈神專題訓練算法題單

階段目標📌：【算法題單】滑動窗口與雙指針

其他:

今日總結
往期打卡

---

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 長的滑動窗口

• 區間 $[2^k,n]$ 內的二進制數的長度均為 $k+1$，這有 $n?2^k+1$ 個，所以應滿足 $m\ge k+1+(n?2^k+1?1)=n?2^k+k+1$ 。
• 區間 $[2^{k?1},2^k?1]$ 內的二進制數的長度均為 k，這有 $2^{k?1}$ 個，所以應滿足 $m\ge k+(2^{k?1}?1)=2^{k?1}+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(k + 1 + (n - (1 << k)), k + (1 << k - 1) - 1):return Falsedef check(k: int, lower: int, upper: int) -> bool:if lower > upper:return Trueif k == 1:return "1" in sseen = set()bits = list(map(int, s[k - 1 :]))num = int(s[: k - 1], 2)mask = (1 << k - 1) - 1# 滑動窗口只找k長的二進制值即可for i in bits:num = ((num & mask) << 1) + iif lower <= num <= upper:seen.add(num)return len(seen) == upper - lower + 1# return check(k + 1, 1 << k, n) and check(k, 1 << k - 1, (1 << k) - 1)# 可以進一步縮小范圍，不必計算全部的2^{k-1}到2^k-1,因為會和2^k到n有重復# return check(k + 1, 1 << k, n) and check(k, (n >> 1) + 1, (1 << k) - 1)# 實測用 n//2 性能更優return check(k + 1, 1 << k, n) and check(k, n // 2 + 1, (1 << k) - 1)

---

總結

繼續練習定長滑動窗口，學習了分組循環和python二進制操作

往期打卡

暑假算法日記第三天

暑假算法日記第二天

暑假算法日記第一天