暑假算法日记第三天

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

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

其他:

今日总结
往期打卡

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

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 = 0
        n = len(s)
        cnt = defaultdict(int)
        for i in range(n - minSize + 1):
            sub_s = s[i: i + minSize]
            cnt[sub_s] += 1
            if 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<=nums[i]<=50$ ）

复杂度:

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

代码:

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        cnt = [0] * 101
        for i in nums[:k - 1]:
            cnt[i] += 1
        ans = [0] * (len(nums) - k + 1)
        for i in range(k - 1,len(nums)):
            cnt[nums[i]] += 1
            temp = 0
            for j in range(-50,0):
                if cnt[j] > 0:
                    temp += cnt[j]
                if temp >= x:
                    ans[i - k + 1] = j
                    break
            cnt[nums[i - k + 1]] -= 1
        return 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] = 0
            else:
                s_new[i] = 1
        cnt = sum(s_new[: len(s)])
        ans = cnt if cnt <= len(s) / 2 else len(s) - cnt

        for 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 True
        for i in range(k,len(s2)):
            s_dict[s2[i]] = s_dict.get(s2[i],0) + 1
            s_dict[s2[i - k]] -= 1
            if s_dict[s2[i - k]] == 0:
                del s_dict[s2[i - k]]
            if target_dict == s_dict:
                return True
        return 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) + 1
            if s_dict == target_dict:
                ans.append(i)
            s_dict[s[i]] -= 1
            if 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) + 1
                if i < k:
                    continue
                if target_dict == s_dict:
                    ans.append(i - k)
                s_dict[s[i - k:i- k + m]] -= 1
                if 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] * k
        for i in range(1, k):
            powers[i] = powers[i - 1] * power % modulo
        cnt = 0
        for i, num in enumerate(s[-k:]):
            cnt = (cnt + (ord(num) - ord("a") + 1) * powers[i]) % modulo

        ans = len(s) - k if cnt == hashValue else 0
        kp = powers[-1] * power % modulo
        for 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
            ) % modulo
            if cnt == hashValue:
                ans = i
        return s[ans : ans + k]

总结

今天继续练习了题单中定长滑动窗口系列的题目

往期打卡

暑假算法日记第二天

暑假算法日记第一天