暑假算法日记第二天

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

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

其他:

今日总结
往期打卡

---

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

2461. 长度为 K 子数组中的最大和

跳转: 2461. 长度为 K 子数组中的最大和

问题:

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

• 子数组的长度是 k，且
• 子数组中的所有元素 各不相同 。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

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

思路:

定长滑动窗口，在元素各不相同时求和比较

复杂度:

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

代码:

class Solution:def maximumSubarraySum(self, nums: List[int], k: int) -> int:ans = cnt = 0dict_num = {}for idx,num in enumerate(nums):cnt += numif num in dict_num:dict_num[num] += 1else:dict_num[num] = 1if idx < k - 1:continueif len(dict_num) == k:ans = max(ans,cnt)temp = nums[idx - k + 1]cnt -= tempif dict_num[temp] == 1:del dict_num[temp]else:dict_num[temp] -= 1return ans

---

1423. 可获得的最大点数

跳转: 1423. 可获得的最大点数

问题:

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

思路:

可以相当于求剩余连续部分最小，连续定长滑动窗口
也可以直接一边多拿一边少拿算非连续的定长滑动窗口

复杂度:

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

代码:

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

---

1052. 爱生气的书店老板

跳转: 1052. 爱生气的书店老板

问题:

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。

思路:

求连续k分钟最大生气时顾客数，然后再加上本来就满意的顾客数

复杂度:

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

代码:

class Solution:def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:ans = cnt = n = 0for idx,num in enumerate(customers):if grumpy[idx] == 1:cnt += numelse:n += numif idx < minutes - 1:continueans = max(ans,cnt)temp = idx - minutes + 1if grumpy[temp] == 1:cnt -= customers[temp]return n + ans

---

1652. 拆炸弹

跳转:1652. 拆炸弹

问题:

你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。

为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。

• 如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
• 如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
• 如果 k == 0 ，将第 i 个数字用 0 替换。

由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。

给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！

思路:

分类讨论，不同情况下用不同的滑动窗口（前窗口/后窗口）
循环索引，需要取余，python对负索引可以不用取余

复杂度:

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

代码:

class Solution:def decrypt(self, code: List[int], k: int) -> List[int]:n = len(code)ans = [0 for _ in range(n)]if k == 0:return ansif k > 0:ans[0] = cnt = sum(code[1:k + 1])for i in range(1,n):cnt += code[(i + k) % n] - code[i]ans[i] = cntelse:ans[0] = cnt = sum(code[k:])for i in range(1,n):cnt += code[i - 1] - code[(i + n + k - 1) % n]ans[i] = cntreturn ans

---

1176. 健身计划评估

跳转: 1176. 健身计划评估

问题:

你的好友是一位健身爱好者。前段日子，他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。

他会有一份计划消耗的卡路里表，其中 calories[i] 给出了你的这位好友在第 i 天需要消耗的卡路里总量。

为了更好地评估这份计划，对于卡路里表中的每一天，你都需要计算他 「这一天以及之后的连续几天」 （共 k 天）内消耗的总卡路里 T：

• 如果 T < lower，那么这份计划相对糟糕，并失去 1 分；
• 如果 T > upper，那么这份计划相对优秀，并获得 1 分；
• 否则，这份计划普普通通，分值不做变动。

请返回统计完所有 calories.length 天后得到的总分作为评估结果。

注意：总分可能是负数。

思路:

滑动窗口求和

复杂度:

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

代码:

class Solution:def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:cnt = sum(calories[:k])ans = 1 if cnt > upper else -1 if cnt <lower else 0for i in range(k,len(calories)):cnt += calories[i] - calories[i-k]ans += 1 if cnt > upper else -1 if cnt <lower else 0return ans

---

1100. 长度为 K 的无重复字符子串

跳转: 1100. 长度为 K 的无重复字符子串

问题:

给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的 数目。

思路:

滑动窗口，维护字典求窗口集合长度

复杂度:

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

代码:

class Solution:def maxSum(self, nums: List[int], m: int, k: int) -> int:ans = cnt = 0dict_num = {}for idx,num in enumerate(nums):cnt += numif num in dict_num:dict_num[num] += 1else:dict_num[num] = 1if idx < k - 1:continueif len(dict_num) >= m:ans = max(ans,cnt)temp = nums[idx - k + 1]cnt -= tempif dict_num[temp] == 1:del dict_num[temp]else:dict_num[temp] -= 1return ans

---

1852. 每个子数组的数字种类数

跳转: 1852. 每个子数组的数字种类数

问题:

给你一个长度为 n 的整数数组 nums 与一个整数 k。你的任务是找到 nums 所有 长度为 k 的子数组中 不同 元素的数量。

返回一个数组 ans，其中 ans[i] 是对于每个索引 0 <= i < n - k，nums[i..(i + k - 1)] 中不同元素的数量。

思路:

滑动窗口，维护字典求窗口集合长度并记录

复杂度:

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

代码:

class Solution:def distinctNumbers(self, nums: List[int], k: int) -> List[int]:dict_num = {}ans = []for i,num in enumerate(nums):if num in dict_num:dict_num[num] += 1else:dict_num[num] = 1if i < k - 1:continueans.append(len(dict_num))temp = nums[i - k + 1]if dict_num[temp] == 1:del dict_num[temp]else:dict_num[temp] -= 1return ans

---

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

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

问题:

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。

思路:

求窗口大小为1的总数的0最少的窗口

复杂度:

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

代码:

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

---

2107. 分享 K 个糖果后独特口味的数量

跳转: 2107. 分享 K 个糖果后独特口味的数量

问题:

您将获得一个 从0开始的 整数数组 candies ，其中 candies[i] 表示第 i 个糖果的味道。你妈妈想让你和你妹妹分享这些糖果，给她 k 个 连续 的糖果，但你想保留尽可能多的糖果口味。
在与妹妹分享后，返回 最多 可保留的 独特 口味的糖果。

思路:

求糖最多的窗口
先获得给出前k个后剩余全部种类糖的数量字典（这里用Counter求比手写快）
再根据窗口动态维护字典求最值

复杂度:

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

代码:

# from collections import Counter
class Solution:def shareCandies(self, candies: List[int], k: int) -> int:total = Counter(candies[k:])if k == 0:return len(total)ans = len(total)for in_, out_ in zip(candies[k:], candies):total[in_] -= 1if total[in_] == 0:del total[in_]total[out_] += 1ans = max(len(total), ans)return ans

---

总结

练习了定长滑动窗口基础题目

往期打卡

暑假算法日记第一天