暑假算法日記第五天

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

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

LeetCode題目:

683. K 個關閉的燈泡
2067. 等計數子串的數量
2524. 子數組的最大頻率分數
2269. 找到一個數字的 K 美麗值
1984. 學生分數的最小差值
1461. 檢查一個字符串是否包含所有長度為 K 的二進制子串
220. 存在重復元素 III

其他:

今日總結
往期打卡

683. K 個關閉的燈泡

跳轉: 683. K 個關閉的燈泡

問題:

n 個燈泡排成一行，編號從 1 到 n 。最初，所有燈泡都關閉。每天 只打開一個 燈泡，直到 n 天后所有燈泡都打開。

給你一個長度為 n 的燈泡數組 blubs ，其中 bulbs[i] = x 意味著在第 (i+1) 天，我們會把在位置 x 的燈泡打開，其中 i 從 0 開始，x 從 1 開始。

給你一個整數 k ，請返回恰好有兩個打開的燈泡，且它們中間正好有 k 個 全部關閉的 燈泡的 最小的天數 。如果不存在這種情況，返回 -1 。

思路:

定長滑動窗口順序遍歷燈泡，如果窗口內所以元素都滿足更晚點亮，就更新ans（因為是按燈泡順序，不知道天數情況，必須遍歷一遍）
如果有更早的就直接更新窗口位置重新檢查窗口

復雜度:

時間復雜度: $O (n)$
空間復雜度: $O (n)$

代碼:

class Solution(object):def kEmptySlots(self, bulbs, k):days = [0] * len(bulbs)for day, position in enumerate(bulbs, 1):days[position - 1] = dayans = float('inf')left, right = 0, k+1while right < len(days):for i in range(left + 1, right):if days[i] < days[left] or days[i] < days[right]:left, right = i, i+k+1breakelse:ans = min(ans, max(days[left], days[right]))left, right = right, right+k+1return ans if ans < float('inf') else -1

2067. 等計數子串的數量

跳轉: 2067. 等計數子串的數量

問題:

給你一個下標從 0 開始的字符串 s，只包含小寫英文字母和一個整數 count。如果 s 的子串中的每種字母在子串中恰好出現 count 次，這個子串就被稱為 等計數子串。

返回 s 中 等計數子串 的個數。

子串是字符串中連續的非空字符序列。

思路:

滑動窗口遍歷k，2k到超出字符串長度或超過26k的窗口大小即可，維護字典和字典中值為k的個數，全部為k時計數

復雜度:

時間復雜度: $O (26 ? n)$
空間復雜度: $O (k)$

代碼:

class Solution:def equalCountSubstrings(self, s: str, k: int) -> 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 ans

2524. 子數組的最大頻率分數

跳轉: 2524. 子數組的最大頻率分數

問題:

給定一個整數數組 nums 和一個正整數 k 。

數組的 頻率得分 是數組中不同值的冪次之和，并將和對 109 + 7 取模。

例如，數組 [5,4,5,7,4,4] 的頻率得分為 (43 + 52 + 71) modulo (109 + 7) = 96 。

返回 nums 中長度為 k 的 子數組 的最大頻率得分。你需要返回取模后的最大值，而不是實際值。

子數組 是一個數組的連續部分。

思路:

直接滑動窗口維護冪次和即可
可以維護指數（頻率）字典，直接對出入值冪次加減
也可以維護冪次差值列表，增冪次加入差值，降冪次直接減差值即可

復雜度:

時間復雜度: $O (n)$
空間復雜度: $O (k)$

代碼:

# class Solution:
#     def maxFrequencyScore(self, nums: List[int], k: int) -> int:
#         cnt = Counter(nums[:k])
#         MOD = 10 ** 9 + 7
#         ans = score = sum([pow(i,j) for i,j in cnt.items()]) % MOD
#         for i,num in enumerate(nums[k:]):
#             if num in cnt:
#                 score -= pow(num,cnt[num])
#                 cnt[num] += 1
#                 score += pow(num,cnt[num])
#             else: 
#                 cnt[num] = 1
#                 score += num
#             score -= pow(nums[i], cnt[nums[i]])
#             cnt[nums[i]] -= 1
#             if cnt[nums[i]] == 0:
#                 del cnt[nums[i]]
#             else:
#                 score += pow(nums[i], cnt[nums[i]])
#             score = score % MOD
#             if score < 0:
#                 score += MOD
#             ans = max(ans,score)
#         return ansclass Solution:def maxFrequencyScore(self, nums: List[int], k: int) -> int:MOD = 10 ** 9 + 7ans = score = 0st_map = {}for i, x in enumerate(nums):if x not in st_map:score += xst_map[x] = [x]else:last = st_map[x][-1]cur = last * x % MODscore += cur - lastst_map[x].append(cur)if i >= k - 1:ans = max(ans, score % MOD)x = nums[i - k + 1]st = st_map[x]score -= st.pop()if st: score += st[-1]else: del st_map[x]return ans

2269. 找到一個數字的 K 美麗值

跳轉:2269. 找到一個數字的 K 美麗值

問題:

一個整數 num 的 k 美麗值定義為 num 中符合以下條件的 子字符串 數目：

子字符串長度為 k 。
子字符串能整除 num 。

給你整數 num 和 k ，請你返回 num 的 k 美麗值。

注意：

允許有前綴 0 。
0 不能整除任何值。

一個 子字符串 是一個字符串里的連續一段字符序列。

思路:

滑動窗口維護好子數組的值即可，十進制出入和維護二進制值出入思路差不多
減去頭數乘 $10^{k-1}$ 后乘10，再加尾數即可

復雜度:

時間復雜度: $O (n)$
空間復雜度: $O (n)$

代碼:

class Solution:def divisorSubstrings(self, num: int, k: int) -> int:nums = list(map(int,str(num)))ans = cnt = 0kp = pow(10,k - 1)for i,x in enumerate(nums):cnt = cnt * 10 + xif i < k - 1:continueif cnt > 0 and num // cnt == num / cnt:ans += 1cnt -= kp * nums[i - k + 1]return ans

1984. 學生分數的最小差值

跳轉: 1984. 學生分數的最小差值

問題:

給你一個 下標從 0 開始 的整數數組 nums ，其中 nums[i] 表示第 i 名學生的分數。另給你一個整數 k 。

從數組中選出任意 k 名學生的分數，使這 k 個分數間 最高分 和 最低分 的差值達到 最小化 。

返回可能的 最小差值 。

思路:

排個序一個個差值找就行（盡可能讓最低分最高分靠近，即排序后序列中k長窗口的首尾），窗口大小為k的滑動窗口

復雜度:

時間復雜度: $O (n l o g n)$
空間復雜度: $O (1)$

代碼:

class Solution:def minimumDifference(self, nums: List[int], k: int) -> int:if k == 1:return 0nums = sorted(nums)ans = nums[k - 1] - nums[0]for i in range(k,len(nums)):ans = min(nums[i] - nums[i - k + 1],ans)return ans

1461. 檢查一個字符串是否包含所有長度為 K 的二進制子串

跳轉: 1461. 檢查一個字符串是否包含所有長度為 K 的二進制子串

問題:

給你一個二進制字符串 s 和一個整數 k 。如果所有長度為 k 的二進制字符串都是 s 的子串，請返回 true ，否則請返回 false 。

思路:

滑動窗口往集合里塞窗口值，最后看看數量是不是最大值+1（算上0）
通過移位運算維護窗口值

復雜度:

時間復雜度: $O (n)$
空間復雜度: $O (n)$

代碼:

class Solution:def hasAllCodes(self, s: str, k: int) -> bool:m = len(s)upper = (1 << k) - 1mask = (1 << k - 1) - 1if m < (k + mask):return Falsenums = list(map(int, s[k:]))x = int(s[:k], 2)num_set = {x}for num in nums:x = ((x & mask) << 1) + numnum_set.add(x)return len(num_set) == upper + 1

220. 存在重復元素 III

跳轉: 220. 存在重復元素 III

問題:

給你一個整數數組 nums 和兩個整數 indexDiff 和 valueDiff 。

找出滿足下述條件的下標對 (i, j)：

i != j,
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff

如果存在，返回 true *；*否則，返回 false 。

思路:

順序遍歷，滑動窗口（可以看作固定i），判斷最值是否在范圍內，在直接返回True，遍歷完返回False
排序整個窗口獲得最值，這里使用排序列表

復雜度:

時間復雜度: $O (n l o g k)$
空間復雜度: $O (n)$

代碼:

#         from sortedcontainers import SortedListclass Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:window = SortedList()for i in range(len(nums)):# len(window) == kif i > k:window.remove(nums[i - 1 - k])window.add(nums[i])idx = bisect.bisect_left(window, nums[i])if idx > 0 and abs(window[idx] - window[idx-1]) <= t:return Trueif idx < len(window) - 1 and abs(window[idx+1] - window[idx]) <= t:return Truereturn False