LeetCode Hot100刷题日志D7

1423. 可获得的最大点数题目描述给定一个整数数组cardPoints每次可以从数组最左边或最右边拿一张牌一共拿k张要求返回可以获得的最大点数。复盘笔记这道题表面上是从两端取牌但本质是在枚举“左边拿几张右边拿几张”的所有组合。因为一共只能拿k张所以方案一定是左边拿 0 张 右边拿 k 张 左边拿 1 张 右边拿 k-1 张 ... 左边拿 k 张 右边拿 0 张代码先假设全部从左边拿k张计算初始总分。然后每次把左边已经拿的一张牌“换成”右边的一张牌。也就是加上右边新拿的牌减去左边少拿的牌并不断更新最大得分。这道题的关键是理解cardPoints[-i]表示从右边数第i张牌cardPoints[k - i]表示当前要从左边方案中退掉的那张牌。class Solution: def maxScore(self, cardPoints: List[int], k: int) - int: ans s sum(cardPoints[:k]) for i in range(1, k 1): s cardPoints[-i] - cardPoints[k - i] ans max(ans, s) return ans面试时所用到的一段话解释本题的思想这道题我会枚举从左边拿多少张、从右边拿多少张。因为总共拿k张所以这两部分数量之和固定为k。我先计算全从左边拿k张的得分然后每次把一张左边的牌替换成一张右边的牌用当前得分更新最大值。这样可以在O(k)时间内枚举所有可能的取牌方案。2379. 得到 K 个黑块的最少涂色次数题目描述给定一个只包含W和B的字符串blocks其中W表示白色块B表示黑色块。每次操作可以把一个白色块染成黑色要求得到至少一个长度为k的连续黑色块返回最少需要染色的次数。复盘笔记这道题可以转化为在blocks中找一个长度为k的窗口使窗口里的白色块W数量最少。因为要让这个窗口全部变成黑色只需要把其中的白色块染黑即可所以窗口中有几个W就需要几次操作。可以先统计第一个长度为k的窗口中W的数量然后窗口每次向右移动一格。右边新进来的字符如果是W计数加一左边离开的字符如果是W计数减一。每形成一个窗口就更新最小值。需要注意的是当前窗口里的白色块数量和最终答案不是同一个变量。当前计数会随着窗口滑动变化而答案应该保存见过的最小白色块数量。class Solution: def minimumRecolors(self, blocks: str, k: int) - int: ans cnt_w blocks[:k].count(W) for in_, out in zip(blocks[k:], blocks): cnt_w (in_ W) - (out W) ans min(ans, cnt_w) return ans面试时所用到的一段话解释本题的思想这道题我会使用定长滑动窗口。目标是得到连续k个黑块所以我只需要找一个长度为k的区间使里面白色块数量最少。窗口中的白色块数量就是需要涂色的次数。滑动时维护当前窗口内W的数量每次右端点进入、左端点离开并用当前数量更新最小答案。2841. 几乎唯一子数组的最大和题目描述给定一个整数数组nums以及整数m和k。要求找到长度为k的子数组并且这个子数组中至少有m个不同元素返回所有满足条件的子数组中的最大元素和。复盘笔记这道题是定长滑动窗口加哈希表统计。窗口长度固定为k需要维护两个信息当前窗口的元素和以及当前窗口中不同元素的数量。元素和可以用变量s维护。不同元素数量可以用哈希表cnt维护每个元素出现的次数len(cnt)就表示当前窗口中不同元素的数量。每次右端点进入窗口时把当前数字加入窗口和并在哈希表中计数加一。当窗口长度达到k后如果len(cnt) m说明当前窗口满足条件就用窗口和更新答案。然后让左端点离开窗口更新窗口和与哈希表。class Solution: def maxSum(self, nums: List[int], m: int, k: int) - int: ans s 0 cnt defaultdict(int) for i, x in enumerate(nums): s x cnt[x] 1 left i - k 1 if left 0: continue if len(cnt) m: ans max(ans, s) out nums[left] s - out cnt[out] - 1 if cnt[out] 0: del cnt[out] return ans面试时所用到的一段话解释本题的思想这道题我会用定长滑动窗口维护长度为k的子数组同时用哈希表统计窗口内每个数字出现的次数。窗口和用于计算答案哈希表的键数量用于判断不同元素个数。当窗口长度达到k时如果不同元素数量至少为m就更新最大和。随后移除左端点元素继续滑动窗口。整体复盘总结今天这几道题依然围绕定长滑动窗口展开但每道题维护的信息略有不同。2379维护窗口中 W 的数量求最小值 2841维护窗口和 不同元素数量求最大合法窗口和 1423枚举左边拿几张、右边拿几张本质也是固定数量 k 的选择滑动窗口题最重要的是明确三个问题1. 窗口长度是多少 2. 窗口里要维护什么信息 3. 窗口形成后答案在什么时候更新今天的收获是看到“连续k个”“长度为k的子数组”“从两端一共取k个”这类描述时要优先考虑固定窗口或者固定数量枚举。关键不是死记模板而是把题目转化成每次只让一个元素进来、一个元素出去并维护窗口中的有效信息。