暑假算法日记第五天

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

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

其他:

今日总结
往期打卡

---

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\ast 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(nlogn)$
• 空间复杂度: $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(nlogk)$
• 空间复杂度: $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

---

总结

结束定长滑动窗口专题

往期打卡

暑假算法日记第四天

暑假算法日记第三天

暑假算法日记第二天

暑假算法日记第一天