暑假算法日記第三天

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

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

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]