LeetCode31~50题解
LeetCode31. 下一个排列：
题目描述：
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，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
思路：
注释代码：
class Solution {
public:void nextPermutation(vector<int>& nums) {// 为什么k = nums.size() -1,因为这里是要最后面的数组元素的下标int k = nums.size() -1;//从后往前找，找到第一个升序的位置while(k > 0 && nums[k -1] >= nums[k]) k--;//如果遍历完数组都是降序的，那么要进行翻转if(k <= 0){reverse(nums.begin(), nums.end());}else {//k此时位于后面部分的最大值上（降序）int t = k;//从升序位置开始，往后找，找到大于第一个升序位置的数的最小的数//因为此时升序位置后面的数都是降序的，所以只管往后找，找到排在最后面的大于升序位置的数while(t < nums.size() && nums[t] > nums[k -1]) t++;//交换升序位置和它后面最小的大于升序位置的数swap(nums[t -1], nums[k -1]);//再将升序后面的数改成升序排序(翻转后面的数)reverse(nums.begin() + k, nums.end());}}
};纯享版:
class Solution {
public:void nextPermutation(vector<int>& nums) {int s = nums.size() - 1;while(s > 0 && nums[s - 1] >= nums[s]) s--;if(s <= 0){reverse(nums.begin(), nums.end());}else {int k = s;while(k < nums.size() && nums[k] > nums[s - 1]) k++;swap(nums[k -1], nums[s - 1]);reverse(nums.begin() + s, nums.end());}}
};
LeetCode32.最长有效括号：
题目描述：
给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号
子串
的长度。
示例 1：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：
输入：s = “”
输出：0
提示：
0 <= s.length <= 3 * 10^4
s[i] 为 ‘(’ 或 ‘)’
思路：
注释代码：
class Solution {
public:int longestValidParentheses(string s) {stack<int> stk;int res = 0;//start是每一段的起始位置的前一个位置，因为第一段的起点为0，所以记录为-1for(int i = 0, start = -1; i < s.size(); i++){//每段遍历//发现当前是左括号，那么将它对应的下标放入栈中if(s[i] == '(') stk.push(i);else{//如果是右括号if(stk.size()){//如果栈里有元素，就将当前右括号跟栈顶的（左括号）进行匹配stk.pop();if(stk.size()){//如果此时栈里还有元素，说明完成了小段的匹配，返回当前的长度res = max(res, i - stk.top());}else{//栈中没有元素了,返回当前整段的长度res = max(res, i - start);}} else {//如果是右括号并且栈中没有能匹配的左括号，那么进入下一段的开始//更新startstart = i;}}}return res;}
};纯享版：
class Solution {
public:int longestValidParentheses(string s) {stack<int> stk;int res = 0;for(int i = 0, start = -1; i < s.size(); i++){if(s[i] == '('){stk.push(i);}else{if(stk.size()){stk.pop();if(stk.size()){res = max(res, i - stk.top());}else{res = max(res, i - start);}}else{start = i;}}}return res;}
};
LeetCode33.搜索旋转排序数组：
题目描述：
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
思路：
由于不存在相同元素，并且旋转之后必然后面的段整体小于前面段，所以先利用这个性质找到分界下标，然后对比target与nums[0]的值就能知道target位于前面段还是后面段，那么该如何找到分界下标：可以利用二分法的二段性，找到第一个不大于nums[0]的值，它的下标就是后面段的起始位置，然后在target对应段进行二分找到等于target值的下标
注释代码：
class Solution {
public:int search(vector<int>& nums, int target) {if(nums.empty()) return -1;int l = 0, r = nums.size() - 1;//先通过二分找到旋转的下标//前半段的值都是大于nums[0] 的//边界点为最后一个满足上述性质的数while(l < r){//中心位置int mid = l + r + 1 >> 1;//当前中心的值是满足条件的，又因为前半段始终大于后半段//那么真正的答案在mid的右边区间，所以将区间由[l, r] -> [mid, r]if(nums[mid] >= nums[0]) l = mid;else r = mid - 1;}//对target进行判断在哪一段//此时的l和r都位于旋转的下标位置//如果目标值在前半段，那么左边界从0开始，右边界为旋转下标位置if(target >= nums[0]) l = 0;//在后半段则左边界从旋转else l = r + 1, r = nums.size() - 1;//此时target一定在[l , r]中，而且[l, r]是单调的while(l < r){int mid = l + r >> 1;if(nums[mid] >= target) r = mid;else l = mid + 1; }if(nums[r] == target) return r;return -1;}
};
纯享版：
class Solution {
public:int search(vector<int>& nums, int target) {if(nums.empty()) return -1;int l = 0, r = nums.size() - 1;while(l < r){int mid = l + r + 1 >> 1;if(nums[mid] >= nums[0]) l = mid;else r = mid -1;}if(target >= nums[0]) l = 0;else l = r + 1, r = nums.size() - 1;while(l < r){int mid = l + r >> 1;if(nums[mid] >= target) r = mid;else l = mid + 1;}if(nums[r] == target) return r;return -1;}
};
LeetCode34.在排序数组中查找元素的第一个和最后一个位置：
题目描述：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9
思路：
使用二分将区间划分为以第一个target为分界的左右两段，找到第一个target位置，再通过二分思想将区间划分为以最后一个target为分界的左右两段，通过二分找到最后一个target位置：
复习：
这里实在对二分思想又模糊起来了，回去复习了一下：
以及评论区一些帮助理解的大神评论：
代码：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if (nums.empty()) return {-1, -1};int l = 0, r = nums.size() - 1;while (l < r) {int mid = l + r >> 1;if (nums[mid] >= target) r = mid;else l = mid + 1;}//如果当前找到的边界不等于target，说明该序列中没有这个值if (nums[r] != target) return {-1, -1};int L = r;l = 0, r = nums.size() - 1;while (l < r) {int mid = l + r + 1 >> 1;if (nums[mid] <= target) l = mid;else r = mid - 1;}return {L, r};}
};
纯享版：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.empty()) return {-1, -1};int l = 0, r = nums.size() -1 ;while(l < r){int mid = l + r >> 1;if(nums[mid] >= target) r = mid;else l = mid + 1;}if(nums[r] != target) return {-1, -1};int L = r;l = 0, r = nums.size() - 1;while(l < r){int mid = l + r + 1 >> 1;if(nums[mid] <= target) l = mid;else r = mid - 1;}return {L, r};}
};
LeetCode35.搜索插入位置：
题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的 升序 排列数组
-10^4 <= target <= 10^4
思路：
由于整个数组是升序且不重复的，那么要找到target或者target要插入的位置，可以用二分找到第一个大于等于target的位置，如果该数存在返回它的小标，如果不存在按照排序也是插入当前位置，于是分成两段，条件为 x >= target
注意这里的边界情况，如果所有数组元素都小于target那么插入的位置为最末尾，所以r应该为数组长度+1
代码：
class Solution {
public:int searchInsert(vector<int>& nums, int target) {if(nums.empty()) return 0;int l = 0, r = nums.size();while(l < r){int mid = l + r >> 1;if(nums[mid] >= target) r = mid;else l = mid + 1;}return r;}
};LeetCode36.有效的数独：
题目描述：
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。
示例 1：
输入：board =
[[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出：true
示例 2：
输入：board =
[[“8”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 ‘.’
思路：
对整体的每一行每一列进行模拟，用bool数组进行维护每个数是否存在，再对每一个3 * 3的小方格进行模拟
注释代码：
class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {//st维护当前数字是否出现过bool st[9];//判断行for(int i = 0; i < 9; i++){//对每一行初始化st数组memset(st, 0, sizeof st);for(int j = 0; j < 9; j++){if(board[i][j] != '.'){//如果当前第i行的第j个不是.的话，对当前出现的数值判断是否有重复//这里因为st数组开的长度是9，小标对应0 ~ 8， 所以要将1 ~ 9 映射到对应下标int t = board[i][j] - '1';//如果st为true，说明出现过，返回falseif(st[t]) return false;//没有的话把当前数值置为true，表示同一行出现过st[t] = true;}}}//判断列for(int i = 0; i < 9; i++){//对每一列初始化st数组memset(st, 0, sizeof st);for(int j = 0; j < 9; j++){if(board[j][i] != '.'){//如果当前第j列的第i个不是.的话，对当前出现的数值判断是否有重复//这里因为st数组开的长度是9，小标对应0 ~ 8， 所以要将1 ~ 9 映射到对应下标int t = board[j][i] - '1';//如果st为true，说明出现过，返回falseif(st[t]) return false;//没有的话把当前数值置为true，表示同一列出现过st[t] = true;}}}//判断3 * 3 小方格for(int i = 0; i < 9; i += 3){for(int j = 0; j < 9; j += 3){//对每个小方格初始化st数组memset(st, 0, sizeof st);for(int x = 0; x < 3; x++){for(int y = 0; y < 3; y++){if(board[i + x][j + y] != '.'){//遍历每个小方格：每个小方格的起始位置+当前偏移量int t = board[i + x][j + y] - '1';if(st[t]) return false;st[t] = true;}}}}}return true;}
};纯享版：
LeetCode37.解数独：
题目描述：
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
示例 1：
输入：board = [[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”],[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”],[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”],[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”],[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”],[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”],[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”],[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”],[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出：[[“5”,“3”,“4”,“6”,“7”,“8”,“9”,“1”,“2”],[“6”,“7”,“2”,“1”,“9”,“5”,“3”,“4”,“8”],[“1”,“9”,“8”,“3”,“4”,“2”,“5”,“6”,“7”],[“8”,“5”,“9”,“7”,“6”,“1”,“4”,“2”,“3”],[“4”,“2”,“6”,“8”,“5”,“3”,“7”,“9”,“1”],[“7”,“1”,“3”,“9”,“2”,“4”,“8”,“5”,“6”],[“9”,“6”,“1”,“5”,“3”,“7”,“2”,“8”,“4”],[“2”,“8”,“7”,“4”,“1”,“9”,“6”,“3”,“5”],[“3”,“4”,“5”,“2”,“8”,“6”,“1”,“7”,“9”]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’
题目数据 保证 输入数独仅有一个解
思路：
使用深度优先遍历将每个位置能出现的数字枚举一遍，同时用三个bool数组维护行，列，小方格出现的数字情况
注释代码：
class Solution {
public://row每一行中 1~9有没有出现过//col每一列中 1~9有没有出现过//cell每一3 * 3 的小方格中 1~9有没有出现过bool row[9][9], col[9][9], cell[3][3][9];void solveSudoku(vector<vector<char>>& board) {memset(row, 0, sizeof row);memset(col, 0, sizeof col);memset(cell, 0, sizeof cell);//初始化已经给出的数字位置for(int i = 0; i< 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] != '.'){//记录当前的数 映射到对应下标int t = board[i][j] - '1';//将出现的所有位置为truerow[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;}}}dfs(board, 0, 0);}bool dfs(vector<vector<char>>& board, int x, int y){//使用深度优先遍历，每次从当前位置出发，纵坐标往后移动一格//如果纵坐标已经移完一行，那么转到下一行开始位置if(y == 9) x++, y = 0;//如果x == 9 也就是说已经找完所有格子了if(x == 9) return true;//如果当前位置有数，那么往后移动一位if(board[x][y] != '.') return dfs(board, x, y + 1);//开始尝试给下一个位置填数for(int i = 0; i < 9; i++){//如果当前位置都是没有出现过iif(!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]){//将数填入，这里下标映射的数应该是i+ 1board[x][y] = '1' + i;//同时将对应位置置为出现过row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;//如果下一个位置填入之后能找到方案，那么返回trueif(dfs(board, x, y + 1)) return true;//否则的话说明填的数是走不通的，那么要恢复现场，重新将该位置的符号变为'.'board[x][y] = '.';//同时已经标记的位置也要置为falserow[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;}}//全部尝试过还是无解那么返回falsereturn false;}};纯享版：
class Solution {
public:bool row[9][9], col[9][9], cell[3][3][9];void solveSudoku(vector<vector<char>>& board) {memset(row, 0, sizeof row);memset(col, 0, sizeof col);memset(cell, 0, sizeof cell);for(int i = 0; i < 9; i ++){for(int j = 0; j < 9; j++){if(board[i][j] != '.'){int t = board[i][j] - '1';row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;}}}dfs(board, 0, 0);}bool dfs(vector<vector<char>>& board, int x, int y){if(y == 9) x++, y = 0;if(x == 9) return true;if(board[x][y] != '.') return dfs(board, x, y + 1);for(int i = 0; i < 9; i++){if(!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]){board[x][y] = '1' + i;row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;if(dfs(board, x, y + 1)) return true;board[x][y] = '.';row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;}}return false;}
};LeetCode38.外观数列：
题目描述：
「外观数列」是一个数位字符串序列，由递归公式定义：
countAndSay(1) = “1”
countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 “3322251” ，我们将 “33” 用 “23” 替换，将 “222” 用 “32” 替换，将 “5” 用 “15” 替换并将 “1” 用 “11” 替换。因此压缩后字符串变为 “23321511”。
给定一个整数 n ，返回 外观数列 的第 n 个元素。
示例 1：
输入：n = 4
输出：“1211”
解释：
countAndSay(1) = “1”
countAndSay(2) = “1” 的行程长度编码 = “11”
countAndSay(3) = “11” 的行程长度编码 = “21”
countAndSay(4) = “21” 的行程长度编码 = “1211”
示例 2：
输入：n = 1
输出：“1”
解释：
这是基本情况。
提示：
1 <= n <= 30
思路：
这题主要理解题目意思，求第n项，由于第一项是固定的，所以循环操作n- 1次得到第n项，每次将上次的结果放回下次循环中进行双指针操作
注释代码：
class Solution {
public:string countAndSay(int n) {//第一项基本情况都是“1”string s = "1";//求的是第n项，需要变换n-1次for(int i = 0; i < n - 1; i++){string t;//每次遍历s串for(int j = 0; j < s.size();){//双指针：k从j后面开始往后面找， 如果相同那么k往后移int k = j + 1;while(k < s.size() && s[j] == s[k]) k++;//j ~k这段就是当前相同的个数,将个数放前面，相同的字符数字放后面t += to_string(k - j) + s[j];//继续往后面找j = k;}//将组合完全的t转交给s返回s = t;}return s;}
};
纯享版：
class Solution {
public:string countAndSay(int n) {string res = "1";for(int i = 0; i < n - 1; i++){string t;for(int j = 0; j < res.size();){int k = j + 1; while(k < res.size() && res[k] == res[j]) k++;//cout<<k<<endl;t += to_string(k - j) + res[j];//cout<<t<<endl;j = k;}res = t;}return res;}
};LeetCode39.组合总和：
题目描述：
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
思路：
看似有点像完全背包问题，但是题目要返回所有方案，涉及排列组合类问题，使用dfs进行爆搜，在target范围内对于每个数组元素枚举他们所有可能选的个数，target 每次减去选的方案
注释代码：
class Solution {
public://ans: 存所有方案vector<vector<int>> ans;//每种选法的路径vector<int> path;vector<vector<int>> combinationSum(vector<int>& c, int target) {dfs(c, 0, target);return ans; }//在c数组中取元素出来， u表示当前取到c数组的第几个元素， target是每次取之后减去当前取的值void dfs(vector<int>&c, int u, int target){//如果当前target为0了，那么说明当前取的值是一种方案if(target == 0){//加入答案容器中ans.push_back(path);return;}//如果当前取到c数组的最后面了，还没有凑出来，说明当前路径无解if(u == c.size()) return;//对c数组的每个元素，在可能选取的范围内， 遍历所有可选个数的方案for(int i = 0; c[u] * i <= target; i++){//刚开始是从0个开始选，直接进入下一层dfs//这里的dfs会爆搜掉所有选i个c[u]的情况dfs(c, u + 1, target - c[u] * i);//每次将当前c数组元素选的情况加入pathpath.push_back(c[u]);}for(int i = 0; c[u] * i <= target; i++){//恢复现场，将path清到上一步的位置path.pop_back();}}
};
纯享版：
class Solution {
public:vector<vector<int>> res;vector<int> path;vector<vector<int>> combinationSum(vector<int>& c, int target) {dfs(c, 0, target);return res;}void dfs(vector<int>& c, int k, int target){if(target == 0){res.push_back(path);return;}if(k == c.size()) return;for(int i = 0; c[k] * i <= target; i++){dfs(c, k + 1, target - c[k] * i);path.push_back(c[k]);}for(int i = 0; i * c[k] <= target; i++){path.pop_back();}}
};
LeetCode40.组合总和Ⅱ：
题目描述：
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
思路：
跟 LeetCode39.组合求和 是一样的，不过对每个元素的次数加以限制，
注释代码：
纯享版：
class Solution {
public:vector<vector<int>> res;vector<int> path;vector<vector<int>> combinationSum2(vector<int>& c, int target) {sort(c.begin(), c.end());dfs(c, 0, target);return res;}void dfs(vector<int>& c, int u, int target){if(target == 0){res.push_back(path);return;}if(u == c.size()) return;int k = u + 1;while(k < c.size() && c[u] == c[k]) k++;int cnt = k - u;for(int i = 0; i * c[u] <= target && i <= cnt; i++){dfs(c, k, target - c[u] * i);path.push_back(c[u]);}for(int i= 0; i * c[u] <= target && i <= cnt; i++){path.pop_back();}}
};LeetCode41.缺失的第一个正数：
题目描述：
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
思路：
(桶排序) O(n)Time, O(1)Space
不用额外空间的桶排序：nums[0] = 1, nums[1] = 2,..., nums[n - 1] = n，其他的数字不管。
例如[3,4,-1,1]将被排序为[1,-1,3,4]
遍历nums，找到第一个不在应在位置上的1到n的数。例如，排序后的[1,-1,3,4]中第一个 nums[i] != i + 1 的是数字2（注意此时i=1）。
时间复杂度分析：代码中第二层while循环，每循环一次，会将一个数放在正确的位置上，所以总共最多执行n次，所以总时间复杂度 O(n)。
##为什么要用while：因为交换后，当前位置出现的新数也需要同样的判断，使用while会对当前nums[i]位置上的数以及交换之后的’nums[i]'也会进行交换，直到当前nums[i]不再具备交换资格
注释代码：
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();//正整数从1 开始if(n == 0) return 1;//从1开始找每个整数对应的下标for(int i = 0; i < n; i++)//数组长度为n，那么整数就是从1 ~ n，//只要找数组元素中不在这里面的最小，如果说刚好都对应上了， 没有缺失，那么n+ 1就是没有出现的最小整数//nums[0] = 1, nums[1] = 2 ... nums[n - 1] = n;//每次将nums[i]放入到它正确的位置上//使用while可以将当前位置的所有交换都落实while(nums[i] >= 0 && nums[i] <= n && nums[i] != i + 1 && nums[nums[i] - 1] != nums[i])swap(nums[i], nums[nums[i] - 1]);//将位置放好之后，只需要找对应位置上不是对应数值的数，如果都对应上了，那么返回n+1for(int i = 0; i < n; i++)if(nums[i] != i + 1)return i + 1;return n + 1;}
};纯享版：
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int s = nums.size();if(s == 0) return 1;for(int i = 0; i < s; i++){while(nums[i] > 0 && nums[i] < s && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){swap(nums[i], nums[nums[i] - 1]);}}for(int i = 0; i < s; i++){if(nums[i] != i + 1){return i + 1;}}return s + 1;}
};LeetCode42.接雨水：
题目描述：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5
思路：
利用单调栈，当右边柱子高于左边柱子时，会形成U字存储雨水，每次将当前U字先削平，然后继续看栈中的下一个是否形成U字
代码：
class Solution {
public:int trap(vector<int>& height) {//stk存储对应柱子的下标stack<int> stk;int res = 0;for(int i = 0; i < height.size(); i++){while(!stk.empty() && height[stk.top()] <= height[i]){int top = stk.top();stk.pop();if(stk.empty()) break;res += (i - stk.top() - 1) * (min(height[stk.top()], height[i]) - height[top]);}stk.push(i);}return res;}
};LeetCode43.字符串相乘：
题目描述：
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
提示：
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。
思路：
涉及字符串数字相乘，一般都是将字符串中的每个数字拆分开到两个数组中进行高精度乘法那套：
##值得注意的是高精度乘法从后面往前乘，所以首先需要倒序存入每个数，用另外一个容器去存他们每一位相乘之后的结果
##关于相乘之后的结果管理如图：C[i + j] = A[i]* B[j] 会发现相乘结果的每一项的i和j相加的数是固定的，所以可以由此将相乘结果累计到最终结果位上：
注释代码：
class Solution {
public:string multiply(string num1, string num2) {vector<int> A, B;int n = num1.size(), m = num2.size();//A和B倒序存储对应数字字符for(int i = n - 1; i >= 0; i--) A.push_back(num1[i] - '0');for(int i = m - 1; i >= 0; i--) B.push_back(num2[i] - '0');//这里是从前往后，但是对应实际的是从后往前将每一位相乘结果放入C中vector<int> C(n + m);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){C[i + j] += A[i] * B[j];}}//处理C的每一位，保留个位，十位叠加到下一位上完成进位for(int i = 0, t = 0; i < C.size(); i++){t += C[i];C[i] = t % 10;t = t / 10;}//将C中最后面的0去除，也就是高位后面的零去除int k = C.size() -1;while(k > 0 && !C[k]) k--;string res;//从后往前将高位到低位依次加到res的后面while(k >= 0) res += C[k--] + '0';return res;}
};纯享版：
class Solution {
public:string multiply(string num1, string num2) {vector<int> A, B;int n = num1.size(), m = num2.size();for(int i = n - 1; i >= 0; i--) A.push_back(num1[i] - '0');for(int i = m - 1; i >= 0; i--) B.push_back(num2[i] - '0');vector<int> C(n + m);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){C[i + j] += A[i] * B[j];}}for(int i = 0, t = 0; i < C.size(); i++){t += C[i];C[i] = t % 10;t = t / 10;}int k = C.size() - 1;while(k > 0 && !C[k]) k--;string res;while(k >= 0) res += C[k--] + '0';return res;}
};LeetCode.通配符匹配：
题目描述：
给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2：
输入：s = “aa”, p = ""
输出：true
解释：'’ 可以匹配任意字符串。
示例 3：
输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
提示：
0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、‘?’ 或 ‘*’ 组成
思路：
这题跟 LeetCode44.正则表达式 思路完全一致，只是匹配条件变化了，不过还是动态规划问题。
注释代码：
class Solution {
public:bool isMatch(string s, string p) {int n = s.size(), m = p.size();s = ' ' + s, p = ' ' + p;vector<vector<bool>> f(n + 1, vector<bool> (m + 1));f[0][0] = true;for(int i = 0; i <= n; i++){for(int j = 1; j <= m; j++){//如果p[j]是*也就是说//1.可以不匹配字符,那么s串的前i个要和p串的前j - 1个匹配//2.匹配一个字符，那么s串的前i -1 个要和p串的前j - 1个匹配//...//优化： 发现f[i - 1][j] 等于 后面p[j]匹配s串任意一个及以上字符的值，所以替换if(p[j] == '*'){f[i][j] = f[i][j - 1] || i && f[i - 1][j];}else {//如果p[j] 不是*，也就是说//s串的前i个和p串的前j个要匹配必须s串的前i - 1 个和p串的前j - 1个先匹配的情况下//并且s[i] = p[j] 或者 p[j] = '?'能单个匹配s[i]//为了防止数组越界，i不能小于1 。。（i- 1）f[i][j] = (s[i] == p[j] || p[j] = '?') && i && f[i - 1][j - 1];}}}}
};纯享版：
class Solution {
public:bool isMatch(string s, string p) {int n = s.size(), m = p.size();s = ' ' + s, p = ' ' + p;vector<vector<bool>> f(n + 1, vector<bool> (m + 1));f[0][0] = true;for(int i = 0; i <= n; i++){for(int j = 1; j <= m; j++){if(p[j] == '*'){f[i][j] = f[i][j - 1] || i && f[i - 1][j];} else{f[i][j] = (s[i] == p[j] || p[j] == '?') && i && f[i - 1][j - 1];}}}return f[n][m];}
};
LeetCode45.跳跃游戏：
题目描述：
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]
思路：
(动态规划+ 贪心优化)O(n) f[i] 表示到达i所需要的最小步数
##通过归纳发现： f[i]是单调增(有时可能不增，比如： 0，1，1，2，2…)的
代码：
class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();vector<int> f(n);f[0] = 0;for(int i = 1,last = 0; i < n; i++){while(last + nums[last] < i) last++; //找到第一个能跳到i的点f[i] = f[last] + 1; //直接更新f[i]}return f[n - 1];}
};LeetCode46.全排列：
题目描述：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
##思路：标准的dfs模板题：列出爆搜递归树，了解需要记哪些状态： 每个位置填什么、当前看的第几位、哪些数已经用过了
注释代码：
class Solution {
public:vector<vector<int>> res;vector<bool> st; //记录状态: 当前哪些数用过了vector<int> path; //每个位置填的什么vector<vector<int>> permute(vector<int>& nums) {path = vector<int>(nums.size());st = vector<bool>(nums.size());dfs(nums, 0);return res;}void dfs(vector<int>& nums, int u){if(u == nums.size()) {res.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(st[i] == false){path[u] = nums[i]; //更新路径st[i] = true; //更新状态dfs(nums, u + 1); //进入下一层st[i] = false; //恢复现场}}}};
纯享版：
class Solution {
public:vector<vector<int>> res;vector<int> path;vector<bool> st;vector<vector<int>> permute(vector<int>& nums) {path = vector<int>(nums.size());st = vector<bool>(nums.size());dfs(nums, 0);return res;}void dfs(vector<int>& nums, int u){if(u == nums.size()){res.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(st[i] == false){path[u] = nums[i];st[i] = true;dfs(nums, u + 1);st[i] = false;}}}
};
LeetCode47.全排列Ⅱ：
题目描述：
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
思路：
跟全排列一样，但是涉及重复元素的话要将重复的排序去除，比如： [1,1,3] ： [[1, 1, 3],[1, 3, 1], [3, 1, 1]],正常的全排列会排列两个[1, 1, 3]， 因为它是将两个1看成不同的数进行罗列， 这里则需要对相同的数进行一定限定：如保证相同的元素出现的顺序保证不变，将数组进行排序，如果nums[i - 1] == nums[i] 并且nums[i -1]没有使用过，说明当前相同元素使用顺序不是有序的
注释代码：
class Solution {
public:vector<vector<int>> res;vector<int> path;vector<bool> st;vector<vector<int>> permuteUnique(vector<int>& nums) {path = vector<int> (nums.size()); //初始化长度st = vector<bool> (nums.size());sort(nums.begin(), nums.end()); //排序一遍，将所有相同的数放到一块dfs(nums, 0);return res;}void dfs(vector<int> & nums, int u){if(u == nums.size()){res.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(st[i] == false){//当前面一个相同的数没有被用过时，应该先用相同的前一个数if(i && nums[i - 1] == nums[i] && st[i - 1] == false) continue; path[u] = nums[i];st[i] = true;dfs(nums, u + 1);st[i] = false;}}}
};纯享版：
class Solution {
public:vector<vector<int>> res;vector<int> path;vector<bool> st;vector<vector<int>> permuteUnique(vector<int>& nums) {path = vector<int> (nums.size());st = vector<bool> (nums.size());sort(nums.begin(), nums.end());dfs(nums, 0);return res;}void dfs(vector<int>& nums, int u){if(u == nums.size()){res.push_back(path);return;}for(int i = 0; i < nums.size(); i ++){if(st[i] == false){if(i && st[i - 1] == false && nums[i - 1] == nums[i]) continue;st[i] = true;path[u] = nums[i];dfs(nums, u + 1);st[i] = false;}}}
};LeetCode48.旋转图像：
题目描述：
给定一个 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]]
提示：
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
思路：
直接挨个替换显然工作量很大并且复杂，一步又不能到位， 所以思考交换规律：根据图中的一个位置的转换规则，再部署到全局进行规范，就会发现交换规律： 有点类似于矩阵的转置
注释代码：
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();//根据对角线 y = x 先对角交换for(int i = 0; i < n;i++){for(int j = 0; j < i; j++){swap(matrix[i][j], matrix[j][i]);}}//沿着中轴进行对称交换for(int i = 0; i < n; i++){for(int j = 0, k = n - 1; j < k; j++, k--){swap(matrix[i][j], matrix[i][k]);}}}
};纯享版：
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for(int i = 0; i < n; i++){for(int j = 0; j < i; j++){swap(matrix[i][j], matrix[j][i]);}}for(int i = 0; i < n; i++){for(int j = 0, k = n - 1; j < k; j++, k--){swap(matrix[i][j], matrix[i][k]);}}}
};LeetCode49.字母异位词分组：
题目描述：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
提示：
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
思路：
将相同字母组成的不同子串放入同一个映射（hash),如何找到相同字母组成的不同子串并放相同映射：sort一遍所有子串，将相同字母组成的不同子串放入它们相同的hash下标中
注释代码：
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;//用hash表来存相同字母组成下的不同子串for(auto& str : strs){string new_str = str;sort(new_str.begin(), new_str.end()); //相同字母组成的子串经过sort会变成一样hash[new_str].push_back(str); //那么将这些不一样的子串存入同一个映射下标}vector<vector<string>> res;//将相同字母组成的不同子串集合放入集合for(auto& item : hash){res.push_back(item.second);}return res;}
};纯享版：
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;for(auto& str : strs){string new_str = str;sort(new_str.begin(), new_str.end());hash[new_str].push_back(str);}vector<vector<string>> res;for(auto& item : hash){res.push_back(item.second);}return res;}
};LeetCode50.Pow(X, n):
题目描述：
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-23^1 <= n <= 23^1-1
n 是一个整数
要么 x 不为零，要么 n > 0 。
-10^4 <= xn <= 10^4
思路：
快速幂的模板题， 但是涉及到负指数，但是负指数也就是 1 / res
##注释代码：
class Solution {
public:double myPow(double x, int n) {typedef long long LL;bool is_minus = n < 0; //判断n为负数的话 = truedouble res = 1;//k 用来表示n的二进制表示，每次右移一位for(LL k = abs((LL) n); k; k >>= 1){//如果当前二进制位为1,说明是有乘法方的if(k & 1) res *= x;x *= x; //x 指数型增长}if(is_minus) res = 1 / res; //如果n为负数，那么实际上是开方return res;}
};纯享版：
class Solution {
public:double myPow(double x, int n) {typedef long long LL;bool is_minus = n < 0;double res = 1;LL k = abs((LL)n);while(k){if(k & 1) res *= x;x *= x;k >>= 1;}if(is_minus) res = 1 / res;return res;}
};