你好呀，欢迎来到 Dong雨 的技术小栈 🌱
在这里，我们一同探索代码的奥秘，感受技术的魅力 ✨。
👉 我的小世界：Dong雨
📌 分享我的学习旅程
🛠️ 提供贴心的实用工具
💡 记录每一个灵感火花
🌟✨ Hello，探索技术的你，这里是本篇的地图指南！ ✨🌟
滑动窗口
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; // 如果字符串为空，直接返回0
int 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.lengthn == t.length1 <= m, n <= 105s和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减1
need[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 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 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]); // 更新最远能到达的位置
// 如果最远位置已经能到达或超过数组末尾，直接返回 true
if (maxJump >= n - 1) return true;
// 如果当前位置 i 无法到达下一个位置（即 maxJump < i + 1），返回 false
if (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));
}
};🎉🌈 陪伴至此，感谢有你 🌈🎉
感谢你能坚持看到这里！如果这篇文章对你有一点点帮助，希望能收获你的：
👍 一个赞，⭐ 一个收藏，💬 一条评论 或 🔗 一键分享！
你的支持是我持续输出的最大动力！✨有问题？有灵感？
别犹豫，直接留言和我交流～让我们一起成长、一起突破 💡。最后，祝你：
🍯 生活美满如蜜香
🌞 心情灿烂似朝阳
🌱 成长如树渐成章
🚀 未来闪耀梦飞翔！再次感谢你的阅读！🌟 下次再见～ 🎉
![73,【5】BUUCTF WEB [网鼎杯 2020 玄武组]SSRFMe（未解出）](https://i-blog.csdnimg.cn/direct/cd51ad18a35442e2829531be3f965a1a.png)
