美妆网站源码asp,烟台H5网站设计公司,凡科网h5,如何做明星的个人网站你好呀#xff0c;欢迎来到 Dong雨 的技术小栈 #x1f331; 在这里#xff0c;我们一同探索代码的奥秘#xff0c;感受技术的魅力 ✨。 #x1f449; 我的小世界#xff1a;Dong雨 #x1f4cc; 分享我的学习旅程 #x1f6e0;️ 提供贴心的实用工具 #x1f4a1; 记… 你好呀欢迎来到 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_mapchar, 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.lengthn t.length1 m, n 105s 和 t 由英文字母组成
// 滑动窗口哈希表
class Solution {
public:string minWindow(string s, string t) {vectorint 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:vectorint maxSlidingWindow(vectorint nums, int k) {int n nums.size(); // 获取数组的长度priority_queuepairint, int pq; // 使用优先队列最大堆存储窗口中的元素及其索引// 初始化第一个窗口前k个元素for (int i 0; i k; i) {pq.push(pair(nums[i], i)); // 将元素及其索引加入优先队列}vectorint 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:vectorint findAnagrams(string s, string p) {int slen s.size(); // 获取字符串 s 的长度int plen p.size(); // 获取字符串 p 的长度// 如果 s 的长度小于 p 的长度直接返回空结果if (slen plen) return {};vectorint sArr(26, 0); // 用于记录窗口内字符的频率s 的子串vectorint pArr(26, 0); // 用于记录字符串 p 中字符的频率vectorint 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(vectorint 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(vectorvectorint 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(vectorvectorint 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(vectorvectorint intervals) {sort(intervals.begin(), intervals.end()); // 按会议开始时间排序// 使用最小堆优先队列来跟踪会议室的结束时间priority_queueint, vectorint, greaterint 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(vectorchar tasks, int n) {// 总的任务数int len tasks.size();vectorint 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));}
}; 陪伴至此感谢有你 感谢你能坚持看到这里如果这篇文章对你有一点点帮助希望能收获你的 一个赞⭐ 一个收藏 一条评论 或 一键分享 你的支持是我持续输出的最大动力✨ 有问题有灵感 别犹豫直接留言和我交流让我们一起成长、一起突破 。 最后祝你 生活美满如蜜香 心情灿烂似朝阳 成长如树渐成章 未来闪耀梦飞翔 再次感谢你的阅读 下次再见
