力扣hot100--＞滑动窗口、贪心

你好呀，欢迎来到 Dong雨 的技术小栈 🌱

在这里，我们一同探索代码的奥秘，感受技术的魅力 ✨。

👉 我的小世界：Dong雨

📌 分享我的学习旅程
🛠️ 提供贴心的实用工具
💡 记录每一个灵感火花

🌟✨ Hello，探索技术的你，这里是本篇的地图指南！ ✨🌟

目录

🌟✨ Hello，探索技术的你，这里是本篇的地图指南！ ✨🌟

滑动窗口

1. 3. 无重复字符的最长子串

2. 76. 最小覆盖子串

3. 239. 滑动窗口最大值

4. 438. 找到字符串中所有字母异位词

 贪心

1. 55. 跳跃游戏

数学

1. 48. 旋转图像

其他

1. 253. 会议室 II

2.621. 任务调度器

🎉🌈 陪伴至此，感谢有你 🌈🎉

---

滑动窗口

1. 3. 无重复字符的最长子串

算术评级: 5

提示

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

// 双指针
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> need; // 使用哈希表记录字符的出现次数int n = s.size(); // 获取字符串的长度if (0 == n) return 0; // 如果字符串为空，直接返回0int left{}, right{1}, result{1}; // 初始化左右指针和结果变量need[s[left]]++; // 将第一个字符加入哈希表，表示已经访问过// 遍历字符串，移动右指针for (; right < n; ++right) {if (need[s[right]] > 0) { // 如果当前字符已经出现过（即在哈希表中计数大于0）// 移动左指针，直到当前字符不再重复while (need[s[right]] > 0) {need[s[left++]]--; // 将左指针指向的字符从哈希表中移除}}need[s[right]]++; // 将当前字符加入哈希表result = max(result, right - left + 1); // 更新最长不重复子串的长度}return result; // 返回最终结果}
};

2. 76. 最小覆盖子串

算术评级: 6

提示

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

// 滑动窗口+哈希表
class Solution {
public:string minWindow(string s, string t) {vector<int> need(128); // 使用大小为128的数组作为哈希表，记录字符的需要量// 初始化need数组，记录字符串t中每个字符的出现次数for (char c : t) need[c]++;int left{}, right{}; // 初始化左右指针int start{}; // 用于记录最小子串的起始位置int count = t.size(); // 记录还需要匹配的字符数量int size = INT_MAX; // 用于记录最小子串的长度，初始值为最大整数// 开始滑动窗口过程for (; right < s.size(); ++right) {char c = s[right]; // 当前右指针指向的字符if (need[c] > 0) count--; // 如果当前字符是需要的字符，则count减1need[c]--; // 将当前字符加入窗口，更新需要量// 当所有字符都匹配成功后（count == 0），尝试缩小窗口if (count == 0) {// 缩小左边界，直到窗口中不再包含多余的字符while (left < right && need[s[left]] < 0) {need[s[left++]]++; // 将左边界字符移出窗口}// 更新最小子串的长度和起始位置if (right - left + 1 < size) {size = right - left + 1; // 更新最小子串长度start = left; // 更新最小子串的起始位置}// 左边界右移，准备寻找下一个可能的子串need[s[left++]]++; // 将左边界字符移出窗口count++; // 由于移出了一个字符，count加1}}// 如果size仍为初始值INT_MAX，说明没有找到符合条件的子串，返回空字符串// 否则返回最小子串return size == INT_MAX ? "" : s.substr(start, size);}
};

3. 239. 滑动窗口最大值

算术评级: 6

提示

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

// 滑动窗口
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size(); // 获取数组的长度priority_queue<pair<int, int>> pq; // 使用优先队列（最大堆）存储窗口中的元素及其索引// 初始化第一个窗口（前k个元素）for (int i = 0; i < k; ++i) {pq.push(pair(nums[i], i)); // 将元素及其索引加入优先队列}vector<int> result; // 用于存储每个窗口的最大值result.push_back(pq.top().first); // 第一个窗口的最大值// 遍历数组，从第k个元素开始，模拟滑动窗口for (int i = k; i < n; ++i) {pq.push(pair(nums[i], i)); // 将当前元素加入优先队列// 移除窗口外的元素while (pq.top().second <= i - k) {pq.pop(); // 如果堆顶元素的索引不在当前窗口范围内，则移除}result.push_back(pq.top().first); // 当前窗口的最大值}return result; // 返回结果}
};

4. 438. 找到字符串中所有字母异位词

算术评级: 4

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

// 滑动窗口
class Solution {
public:vector<int> findAnagrams(string s, string p) {int slen = s.size(); // 获取字符串 s 的长度int plen = p.size(); // 获取字符串 p 的长度// 如果 s 的长度小于 p 的长度，直接返回空结果if (slen < plen) return {};vector<int> sArr(26, 0); // 用于记录窗口内字符的频率（s 的子串）vector<int> pArr(26, 0); // 用于记录字符串 p 中字符的频率vector<int> ans; // 用于存储结果（异位词的起始索引）// 初始化 pArr，记录字符串 p 中每个字符的频率for (char c : p) {pArr[c - 'a']++; // 将字符 c 转换为索引（0-25），并增加频率}// 初始化 sArr，记录 s 中前 plen 个字符的频率for (int i = 0; i < plen; ++i) {sArr[s[i] - 'a']++; // 将字符 s[i] 转换为索引，并增加频率}// 检查初始窗口是否与 pArr 相等if (sArr == pArr) ans.emplace_back(0); // 如果相等，记录起始索引 0// 滑动窗口，从第 plen 个字符开始，到 s 的末尾for (int i = 0; i < slen - plen; ++i) {// 更新窗口：// 移除窗口左侧的字符（s[i]），并减少其频率sArr[s[i] - 'a']--;// 添加窗口右侧的字符（s[i + plen]），并增加其频率sArr[s[i + plen] - 'a']++;// 检查当前窗口是否与 pArr 相等if (sArr == pArr) ans.emplace_back(i + 1); // 如果相等，记录当前窗口的起始索引}return ans; // 返回所有异位词的起始索引}
};

 贪心

1. 55. 跳跃游戏

算术评级: 5

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

// 贪心
class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size(); // 获取数组的长度int maxJump = 0; // 用于记录当前能到达的最远位置for (int i = 0; i < n; ++i) {maxJump = max(maxJump, i + nums[i]); // 更新最远能到达的位置// 如果最远位置已经能到达或超过数组末尾，直接返回 trueif (maxJump >= n - 1) return true;// 如果当前位置 i 无法到达下一个位置（即 maxJump < i + 1），返回 falseif (maxJump < i + 1) {return false;}}return true; // 如果循环正常结束，说明可以到达末尾}
};

数学

1. 48. 旋转图像

算术评级: 5

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

class Solution {
public: // 重点是找到规律：对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。// 即 matrix[r][c] 在旋转后，新的位置是 matrix[c][n-r-1]// 方法一：借助辅助数组// void rotate(vector<vector<int>>& matrix) {//     auto mNew = matrix; // 创建一个辅助矩阵//     int n = matrix.size();//     for (int i = 0; i < n; ++i) {//         for (int j = 0; j < n; ++j) {//             mNew[j][n - i - 1] = matrix[i][j]; // 根据规律更新位置//         }//     }//     matrix = mNew; // 将辅助矩阵赋值回原矩阵// }// 方法二：利用翻转代替旋转// 水平翻转：matrix[r][c] = matrix[n-row-1][c]// 主对角线翻转: matrix[r][c] = matrix[c][r]void rotate(vector<vector<int>>& matrix) {int n = matrix.size(); // 获取矩阵的大小// 第一步：水平翻转（上下翻转）for (int i = 0; i < n / 2; ++i) { // 只需翻转上半部分for (int j = 0; j < n; ++j) { // 遍历每一列swap(matrix[i][j], matrix[n - i - 1][j]); // 交换第 i 行和第 n-i-1 行的元素}}// 第二步：主对角线翻转（沿对角线翻转）for (int i = 0; i < n; ++i) { // 遍历每一行for (int j = 0; j < i; ++j) { // 只需翻转对角线左侧的元素swap(matrix[i][j], matrix[j][i]); // 交换 matrix[i][j] 和 matrix[j][i]}}}
};

其他

1. 253. 会议室 II

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei)，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例 1:

输入: [[0, 30],[5, 10],[15, 20]]
输出: 2
示例 2:

输入: [[7,10],[2,4]]
输出: 1

// 优先队列（最小堆）
class Solution {
public:int minMeetingRooms(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end()); // 按会议开始时间排序// 使用最小堆（优先队列）来跟踪会议室的结束时间priority_queue<int, vector<int>, greater<int>> pq;for (auto &meet : intervals) {// 如果堆不为空且堆顶的结束时间小于等于当前会议的开始时间if (!pq.empty() && pq.top() <= meet[0]) {pq.pop(); // 释放会议室}pq.push(meet[1]); // 分配会议室给当前会议}return pq.size(); // 堆的大小即为需要的会议室数量}
};

2.621. 任务调度器

算术评级: 6

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。

返回完成所有任务所需要的 最短时间间隔 。

示例 1：

输入：tasks = ["A","A","A","B","B","B"], n = 2

输出：8

解释：

在完成任务 A 之后，你必须等待两个间隔。对任务 B 来说也是一样。在第 3 个间隔，A 和 B 都不能完成，所以你需要待命。在第 4 个间隔，由于已经经过了 2 个间隔，你可以再次执行 A 任务。

示例 2：

输入：tasks = ["A","C","A","B","D","B"], n = 1

输出：6

解释：一种可能的序列是：A -> B -> C -> D -> A -> B。

由于冷却间隔为 1，你可以在完成另一个任务后重复执行这个任务。

示例 3：

输入：tasks = ["A","A","A","B","B","B"], n = 3

输出：10

解释：一种可能的序列为：A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B。

只有两种任务类型，A 和 B，需要被 3 个间隔分割。这导致重复执行这些任务的间隔当中有两次待命状态。

class Solution {
public:// 总排队时间 = (桶个数 - 1) * (n + 1) + 最后一桶的任务数int leastInterval(vector<char>& tasks, int n) {// 总的任务数int len = tasks.size();vector<int> vec(26, 0); // 用于记录每个任务的出现次数（任务为大写字母，共26个）// 统计每个任务的出现次数for (char c : tasks) ++vec[c - 'A'];// 按出现次数降序排序sort(vec.rbegin(), vec.rend());// 计算最后一桶的任务数int cnt = 1; // 初始化为1，表示至少有一个任务（出现次数最多的任务）while (cnt < vec.size() && vec[cnt] == vec[0]) {cnt++; // 如果有多个任务的出现次数等于最大值，它们都会在最后一桶中}// 计算总时间// vec[0] - 1：桶的数量（出现次数最多的任务）// n + 1：每个桶的总时间（一个任务 + n个冷却时间）// cnt：最后一桶的任务数return max(len, cnt + (n + 1) * (vec[0] - 1));}
};

🎉🌈 陪伴至此，感谢有你 🌈🎉

感谢你能坚持看到这里！如果这篇文章对你有一点点帮助，希望能收获你的：
👍 一个赞，⭐ 一个收藏，💬 一条评论 或 🔗 一键分享！
你的支持是我持续输出的最大动力！✨

有问题？有灵感？
别犹豫，直接留言和我交流～让我们一起成长、一起突破 💡。

最后，祝你：

🍯 生活美满如蜜香
🌞 心情灿烂似朝阳
🌱 成长如树渐成章
🚀 未来闪耀梦飞翔！

再次感谢你的阅读！🌟 下次再见～ 🎉