暑假算法日记第三天

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

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

LeetCode题目:

3439. 重新安排会议得到最多空余时间 I
2134. 最少交换次数来组合所有的 1 II
1297. 子串的最大出现次数
2653. 滑动子数组的美丽值
1888. 使二进制字符串字符交替的最少反转次数
567. 字符串的排列
438. 找到字符串中所有字母异位词
30. 串联所有单词的子串
2156. 查找给定哈希值的子串

其他:

今日总结
往期打卡

学习: 灵神：教你解决定长滑窗！

3439. 重新安排会议得到最多空余时间 I

跳转: 3439. 重新安排会议得到最多空余时间 I

问题:

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的最长连续空余时间。

移动前后所有会议之间的相对顺序需要保持不变，而且会议时间也需要保持互不重叠。

请你返回重新安排会议以后，可以得到的最大空余时间。

注意，会议不能安排到整个活动的时间以外。

思路:

可以看作凑最大间隙，找间隙数组k+1长窗口能凑的最大值

复杂度:

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

代码:

class Solution:def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:gaps = [startTime[0]]for i in range(1,len(startTime)):gaps.append(startTime[i] - endTime[i - 1])gaps.append(eventTime - endTime[-1])ans = cnt = sum(gaps[:k + 1])for i in range(k + 1,len(gaps)):cnt += gaps[i] - gaps[i - k - 1]ans = max(ans,cnt)return ans

2134. 最少交换次数来组合所有的 1 II

跳转: 2134. 最少交换次数来组合所有的 1 II

问题:

交换定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。

环形数组是一个数组，可以认为 第一个 元素和 最后一个 元素相邻。

给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

思路:

环形可以拼接一遍除最后一元素的头部获得（不会走到两圈以上）

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (1)$

代码:

class Solution:def minSwaps(self, nums: List[int]) -> int:k = sum(nums)new_nums = nums + nums[:k]ans = cnt = sum(nums[:k])for i in range(k,len(new_nums)):cnt += new_nums[i] - new_nums[i - k]ans = max(ans,cnt)return k - ans

1297. 子串的最大出现次数

跳转: 1297. 子串的最大出现次数

问题:

给你一个字符串 s ，请你返回满足以下条件且出现次数最大的任意子串的出现次数：

子串中不同字母的数目必须小于等于 maxLetters 。
子串的长度必须大于等于 minSize 且小于等于 maxSize 。

思路:

因为比minSize大的情况出现次数最大也必然有长为minSize的子串，所以直接看minSize就行
条件更新的滑动窗口，set(sub_s)可以直接去重

复杂度:

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

代码:

# class Solution:
#     def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
#         dict_cnt = {}
#         sub = s[:minSize]
#         dict_num = Counter(sub)
#         ans = 0
#         if len(dict_num) <= maxLetters:
#             ans = 1
#             dict_cnt[sub] = 1
#         for i in range(minSize, len(s)):
#             sub = sub[1:] + s[i]
#             temp = s[i - minSize]
#             dict_num[s[i]] = dict_num.get(s[i], 0) + 1
#             dict_num[temp] -= 1
#             if dict_num[temp] == 0:
#                 del dict_num[temp]
#             if len(dict_num) > maxLetters:
#                 continue
#             dict_cnt[sub] = dict_cnt.get(sub, 0) + 1
#             ans = max(ans, dict_cnt[sub])
#         return ans
class Solution:def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:ans = 0n = len(s)cnt = defaultdict(int)for i in range(n - minSize + 1):sub_s = s[i: i + minSize]cnt[sub_s] += 1if cnt[sub_s] > ans and len(set(sub_s)) <= maxLetters:ans = cnt[sub_s]return ans

2653. 滑动子数组的美丽值

跳转:2653. 滑动子数组的美丽值

问题:

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是负数，那么美丽值为第 x 小的数，否则美丽值为 0 。

请你返回一个包含 n - k + 1 个整数的数组，依次表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。

子数组指的是数组中一段连续非空的元素序列。

思路:

主要是求第x小，可以用SortedList，也可以用哈希（这题 $- 50 <= n u m s [i] <= 50$ ）

复杂度:

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

代码:

class Solution:def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:cnt = [0] * 101for i in nums[:k - 1]:cnt[i] += 1ans = [0] * (len(nums) - k + 1)for i in range(k - 1,len(nums)):cnt[nums[i]] += 1temp = 0for j in range(-50,0):if cnt[j] > 0:temp += cnt[j]if temp >= x:ans[i - k + 1] = jbreakcnt[nums[i - k + 1]] -= 1return ans

1888. 使二进制字符串字符交替的最少反转次数

跳转:1888. 使二进制字符串字符交替的最少反转次数

问题:

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

类型 1 ：删除 字符串 s 的第一个字符并将它添加到字符串结尾。
类型 2 ：选择 字符串 s 中任意一个字符并将该字符反转，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成交替字符串的前提下， 类型 2 的最少操作次数。

我们称一个字符串是交替的，需要满足任意相邻字符都不同。

比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

思路:

奇偶余数都一致或者都不一致两种情况取最小，因为可以把头部移到尾部，两种情况顺序也无所谓，所以可以直接拼接求滑动窗口一致或不一致的最小值反转

复杂度:

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

代码:

class Solution:def minFlips(self, s: str) -> int:s_new = [0] * (len(s) * 2 - 1)for i, ch in enumerate(s + s[:-1]):if int(ch) == i % 2:s_new[i] = 0else:s_new[i] = 1cnt = sum(s_new[: len(s)])ans = cnt if cnt <= len(s) / 2 else len(s) - cntfor i in range(len(s), len(s_new)):cnt += s_new[i] - s_new[i - len(s)]ans = min(ans, cnt if cnt <= len(s) / 2 else len(s) - cnt)return ans

567. 字符串的排列

跳转: 567. 字符串的排列

问题:

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

思路:

直接比较哈希表或字典（map）判断子串相等，滑动窗口更新字母出入

复杂度:

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

代码:

class Solution:def checkInclusion(self, s1: str, s2: str) -> bool:target_dict = Counter(s1)k = len(s1)s_dict = Counter(s2[:k])if target_dict == s_dict:return Truefor i in range(k,len(s2)):s_dict[s2[i]] = s_dict.get(s2[i],0) + 1s_dict[s2[i - k]] -= 1if s_dict[s2[i - k]] == 0:del s_dict[s2[i - k]]if target_dict == s_dict:return Truereturn False

438. 找到字符串中所有字母异位词

跳转: 438. 找到字符串中所有字母异位词

问题:

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

思路:

直接比较哈希表或字典（map）判断子串相等，滑动窗口更新字母出入，不同的是要记录全部索引

复杂度:

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

代码:

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:ans = []target_dict = Counter(p)s_dict = Counter(s[:len(p) - 1])for i,num in enumerate(s[len(p) - 1:]):s_dict[num] = s_dict.get(num,0) + 1if s_dict == target_dict:ans.append(i)s_dict[s[i]] -= 1if s_dict[s[i]] == 0:del s_dict[s[i]]return ans

30. 串联所有单词的子串

跳转: 30. 串联所有单词的子串

问题:

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

思路:

需要一次记一个单词，但需要找全子串，所以0到单词长-1都要找
滑动窗口维护字典即可

复杂度:

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

代码:

class Solution:def findSubstring(self, s: str, words: List[str]) -> List[int]:m = len(words[0])target_dict = Counter(words)k = m * (len(words) - 1)ans = []for j in range(m):s_dict = {}for i in range(j,len(s),m):s_dict[s[i:i + m]] = s_dict.get(s[i:i+m],0) + 1if i < k:continueif target_dict == s_dict:ans.append(i - k)s_dict[s[i - k:i- k + m]] -= 1if s_dict[s[i - k:i- k + m]] == 0:del s_dict[s[i - k:i- k + m]]return ans

2156. 查找给定哈希值的子串

跳转: 2156. 查找给定哈希值的子串

问题:

给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：

hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.

其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val('a') = 1 到 val('z') = 26 。

给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。请你返回 s 中 第一个 长度为 k 的子串 sub ，满足 hash(sub, power, modulo) == hashValue 。

测试数据保证一定存在至少一个这样的子串。

子串定义为一个字符串中连续非空字符组成的序列。

思路:

可以看到后k-1项可以提一个公因子power，所以要倒着算。且需要注意不要搞出负数
ord(num) - ord("a") + 1 可以用 ord(num) &31 替代（前面11，即96会被掩去）

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (1)$

代码:

class Solution:def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:powers = [1] * kfor i in range(1, k):powers[i] = powers[i - 1] * power % modulocnt = 0for i, num in enumerate(s[-k:]):cnt = (cnt + (ord(num) - ord("a") + 1) * powers[i]) % moduloans = len(s) - k if cnt == hashValue else 0kp = powers[-1] * power % modulofor i in range(len(s) - k - 1, -1, -1):cnt = (cnt * power+ (ord(s[i]) - ord("a") + 1)- (ord(s[i + k]) - ord("a") + 1) * kp) % moduloif cnt == hashValue:ans = ireturn s[ans : ans + k]