笺札

2024. 考试的最大困扰度 🎯 问题描述（来源于LeetCode） 描述： 一位老师正在出一场判断题测试，其中每道题的答案都是 ‘T’ (真) 或 ‘F’ (假)。 给你一个字符串 answerKey，其中 answerKey[i] 是第 i 题的正确答案。 同时给你一个整数 k，表示你最多可以执行 k 次操作。 每次操作你可以将任意一题的答案从 ‘T’ 改为 ‘F’，或者从 ‘F’ 改为 ‘T’。 请你返回在不超过 k 次操作的情况下，最大连续 ‘T’ 或者 ‘F’ 的数目。 说明： 这是一个不定长滑动窗口问题。 题目要求最大化连续相同字符的长度，这意味着我们需要找到一个子串，其中少数派字符的数量不超过 k（因为我们可以把少数派改成多数派）。 策略：分别计算“将 ‘F’ 改为 ‘T’”和“将 ‘T’ 改为 ‘F’”两种情况下的最大长度，取最大值。 示例： 示例 1： 1234输入：answerKey = "TTFF", k = 2输出：4解释：我们可以将两个 'F' 都变成 'T'，得到...

576. 出界的路径数 🎯 问题描述（来源于LeetCode） 描述：给定一个 m x n 的网格，一个球最初位于位置 (startRow, startColumn)。球可以移动，每次移动可以向四个方向（上、下、左、右）之一移动一个单元格。如果球移出网格边界，就无法再移动。 给定最大移动次数 maxMove。求出从 (startRow, startColumn) 出发，在不超过 maxMove 次移动内，有多少种路径能让球出界。 说明： 球在出界后即停止。 答案可能很大，请对 109+710^9 + 7109+7 取模。 1<=m,n<=501 <= m, n <= 501<=m,n<=50 0<=maxMove<=500 <= maxMove <= 500<=maxMove<=50 示例： 示例 1： 123输入: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0输出: 6解释: 有6种路径能让球在2步内出界。 示例 2：...

2090. K 半径子数组的平均值 🎯 问题描述（来源于LeetCode） 描述：给你一个下标从 0 开始的数组 nums，对于每个下标 i，计算以 i 为中心且半径为 k 的子数组的平均值（向下取整）。如果不存在这样的子数组，则答案为 -1。 说明： 半径为 k 的子数组：指长度为 2k+12k+12k+1 的连续子序列，中心点为 i。 如果下标 i 的左右两边无法容纳 k 个元素（即数组边界处），则无法形成子数组，结果为 -1。 示例 1： 12345678输入：nums = [7,4,3,9,1,8,5,2,6], k = 3输出：[-1,-1,-1,5,4,4,-1,-1,-1]解释：只有下标 3, 4, 5 能作为中心点形成长度为 7 的子数组。avgs[3] = (7+4+3+9+1+8+5) // 7 = 37 // 7 = 5````- **示例 2**： 输入：nums = [100000], k = 0 输出：[100000] 解释： 当 k=0 时，半径为 0，子数组长度为 1，直接返回原值。 123456## 💻 解题思路### 思路1：定长滑...

1423. 可获得的最大点数 🎯 问题描述（来源于LeetCode） 描述： 几张卡牌排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。 每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。 你的点数就是你拿到手中的所有卡牌的点数之和。 返回可以获得的最大点数。 说明： 这是一个典型的**“逆向思维 + 滑动窗口”**问题。 从两端取 k 个元素使得和最大，等价于在数组中间保留 n-k 个连续元素使得和最小。 最大得分 = 数组总和 - 中间连续子数组的最小和。 示例： 示例 1： 123456输入：cardPoints = [1,2,3,4,5,6,1], k = 3输出：12解释：最优策略是从右端取 3 张牌 (1, 6, 5)，和为 12。逆向思考：数组总和 28。我们要保留 n-k = 4 张牌在中间。中间连续 4 张牌的最小和是 [4,5,6,1] = 16，则得分 28-16=12。 示例 2： 12345输入：cardPoints = [9,7,7,9,7,7,9], k = ...

1343. 大小为 K 且平均值大于等于阈值的子数组数目 🎯 问题描述（来源于LeetCode） 描述：给你一个整数数组 arr 和两个整数 k 和 threshold。请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。 说明： 子数组是数组中连续的元素序列。 为了方便计算，我们将“平均值 ≥\ge≥ 阈值”转化为“总和 ≥\ge≥ 阈值 ×\times× 长度”，避免浮点数运算。 示例： 示例 1： 1234输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4输出：3解释：满足条件的子数组有 [2,5,5], [5,5,5] 和 [5,5,8]。它们的平均值分别为 4, 5, 6，均大于等于 4。 示例 2： 123输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5输出：6解释：所有长度为 3 的子数组的平均值均大于 5。 💻 解题思路 思路1：定长滑动窗口 思路1：代码实现 12345678910111213...

2461. 定长且至少包含M个不同元素的子数组最大和 🎯 问题描述（来源于LeetCode） 描述：给你一个整数数组 nums 和两个正整数 m 和 k。请你找出长度为 k 且至少包含 m 个不同元素的子数组的最大和。 说明： 子数组是数组中连续的元素序列 如果不存在满足条件的子数组，则返回 0 示例： 示例 1： 1234输入：nums = [2,1,3], m = 2, k = 2输出：4解释：长度为 2 的子数组有 [2,1] 和 [1,3]，它们都包含至少 2 个不同元素。[2,1] 的和为 3，[1,3] 的和为 4，因此返回 4。 示例 2： 123输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3输出：0解释：所有长度为 3 的子数组最多只包含 2 个不同元素，因此不存在满足条件的子数组。 💻 解题思路 思路1：定长滑动窗口 + 哈希表 思路1：代码实现 123456789101112131415161718192021222324252627282930313233class Solution: def ...

1456. 定长子串中元音的最大数目-LeetCode 🎯 问题描述（来源于LeetCode） 描述：给你一个字符串 s 和一个整数 k，请你找出 s 中的最长子串，该子串包含的元音字母数不超过 k 个。返回这个子串的长度。 说明： 元音字母为 ‘a’, ‘e’, ‘i’, ‘o’, ‘u’（仅小写） 子串是字符串中连续的字符序列 1<=s.length<=1051 <= s.length <= 10^51<=s.length<=105 1<=k<=s.length1 <= k <= s.length1<=k<=s.length 示例： 示例 1： 123输入：s = "abciiidef", k = 3输出：3解释：子串 "iii" 包含 3 个元音字母 - **示例 2**： 123输入：s = "aeiou", k = 2输出：2解释：任何长度为 2 的子串都包含 2 个元音字母 - **示例 3**： 123输入：s = ...

2379. 得到 K 个黑块的最少涂色次数 🎯 问题描述（来源于LeetCode） 描述：给你一个长度为 n 的二进制字符串 blocks，它由字符 ‘B’（黑）和 ‘W’（白）组成。你需要从中找到一个长度为 k 的子字符串，并将其中所有的 ‘W’ 涂成 ‘B’。请你返回得到一个包含 至少 k 个连续 ‘B’ 的子字符串所需的最少涂色次数。 说明： 涂色次数：即子字符串中 ‘W’ 字符的数量。 目标：寻找长度为 k 的窗口中，‘W’ 数量最少的那个窗口。 示例 1： 1234567输入：blocks = "WBBWWBBWBW", k = 7输出：3解释：一种得到 7 个连续黑块的方案是把下标 [0, 6] 的字符重新涂色。在这种方案下，有 3 个 'W' 需要涂成黑色。````- **示例 2**： 输入：blocks = “WBWBBBW”, k = 2 输出：0 解释：无需涂色，因为已经有 “BB” 子字符串了。 12345678910111213141516171819202122232425262728293031323...

3. 无重复字符的最长子串 🎯 问题描述（来源于LeetCode） 描述： 给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。 说明： 子串：字符串中一段连续非空的字符序列。 核心逻辑：使用滑动窗口维护一个“无重复字符”的区间。当遇到重复字符时，收缩左边界，直到窗口内再次满足无重复条件。 示例： 示例 1： 123输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2： 123输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3： 1234输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 💻 解题思路 思路1：不定长滑动窗口...

53. 最大子数组和-LeetCode 🎯 问题描述（来源于LeetCode） 描述：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 说明： 子数组是数组中的一个连续部分。 示例： 示例 1： 123输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6。 示例 2： 12输入：nums = [1]输出：1 💻 解题思路 思路1：动态规划 (Kadane算法) 核心思想： 这道题的关键在于**“局部最优”导致“全局最优”。 我们不需要关心整个数组怎么切分，只需要关注：“如果我要以当前位置 i 结尾，我能得到的最大和是多少？”** 状态定义：dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。 贪心策略（状态转移）： 当我们走到 nums[i] 时，我们面临两个选择： 加入前面的队伍：如果前面的 dp[i-1] 是正数（有利可图），那就加上它。 另起炉灶：如果前面的 dp[i-1] 是负数（它是...