1. 下一个排列【中等】

题目链接：https://leetcode.cn/problems/next-permutation/
参考题解：https://leetcode.cn/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/

1.1 题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

示例1：

输入：nums = [1,2,3]
输出：[1,3,2]

示例2：

输入：nums = [3,2,1]
输出：[1,2,3]

示例3：

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

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

1.2 解题思路

1.3 代码实现

class Solution {
public:void nextPermutation(vector<int>& nums) {int len = nums.size();int leftMax = len - 2;int rightMax = len - 1;while(leftMax >= 0 && nums[leftMax] >= nums[leftMax + 1])--leftMax;if(leftMax >= 0) {while(rightMax >= 0 && nums[leftMax] >= nums[rightMax])--rightMax;swap(nums[leftMax], nums[rightMax]);    }reverse(nums.begin() + leftMax + 1, nums.end());}
};

2. 两数相加【中等】

题目链接：https://leetcode.cn/problems/add-two-numbers/
参考题解：https://leetcode.cn/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode-solution/

2.1 题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

2.2 解题思路

2.3 代码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* dummy = new ListNode();ListNode* current = dummy;int carry = 0;while(l1 || l2 || carry) {int val1 = l1 ? l1->val : 0;int val2 = l2 ? l2->val : 0;int sum = val1 + val2 + carry;current->next = new ListNode(sum % 10);current = current->next;carry = sum / 10;if(l1) l1 = l1->next;if(l2) l2 = l2->next;}return dummy->next;}
};

3. 括号生成【中等】

题目链接：https://leetcode.cn/problems/generate-parentheses/
参考题解：https://leetcode.cn/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/

3.1 题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例1：

输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例2：

输入：n = 1
输出：[“()”]

提示：

• 1 <= n <= 8

3.2 解题思路

3.3 代码实现

class Solution {
public:void tryGenerate(vector<string>& ans, string str, int n, int leftNum, int rightNum) {int len = str.length();if(len == n * 2) {ans.push_back(str);return;}if(leftNum < n) {str.push_back('(');tryGenerate(ans, str, n, leftNum + 1, rightNum);str.pop_back();}if(rightNum < leftNum) {str.push_back(')');tryGenerate(ans, str, n, leftNum, rightNum + 1);str.pop_back();}}vector<string> generateParenthesis(int n) {vector<string> ans;tryGenerate(ans, "", n, 0, 0);return ans;}
};

4. 滑动窗口最大值【困难】

题目链接：https://leetcode.cn/problems/sliding-window-maximum/
参考题解：https://leetcode.cn/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/

4.1 题目描述

给你一个整数数组 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]

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

4.2 解题思路

4.3 代码实现

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int len = nums.size();priority_queue<pair<int, int>> currentWindow;vector<int> ans;for(int i = 0; i < k; ++i) {currentWindow.emplace(nums[i], i);}ans.push_back(currentWindow.top().first);for(int i = k; i < len; ++i) {currentWindow.emplace(nums[i], i);while(currentWindow.top().second < i - k + 1)currentWindow.pop();ans.push_back(currentWindow.top().first);}return ans;}
};

5. 最小覆盖子串【困难】

题目链接：https://leetcode.cn/problems/minimum-window-substring/
参考题解：https://leetcode.cn/problems/minimum-window-substring/solution/tong-su-qie-xiang-xi-de-miao-shu-hua-dong-chuang-k/

5.1 题目描述

给你一个字符串 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 <= 10^5
• s 和 t 由英文字母组成

进阶： 你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

5.2 解题思路

5.3 代码实现

class Solution {
public:string minWindow(string s, string t) {int min = s.length() + 1;unordered_map<char, int> need;int needNum = t.length();for(char c : t) {need[c]++;}int left = 0, right = 0;int start = 0;while(right < s.length()) {if(need[s[right]] > 0)needNum--;need[s[right]]--;if(!needNum) {while(left < right && need[s[left]] < 0) {need[s[left]]++;left++;}if(right - left + 1 < min) {min = right - left + 1;start = left;}need[s[left]]++;left++;needNum++;}right++;}return min <= s.length() ? s.substr(start, min) : "";}
};