31. 下一个排列 本题考查的其实是next_permutation这个库函数。
class Solution { public: void nextPermutation(vector<int>& nums) { int k = nums.size() - 1; while (k > 0 && nums[k - 1] >= nums[k]) k--;//从后往前找到第一个开始降序的元素 if (k <= 0) {//升序排列的话就直接翻转 reverse(nums.begin(), nums.end()); } else { int t = k; while (t < nums.size() && nums[t] > nums[k - 1]) t++;//找到后面第一个小于等于k - 1位置的元素 swap(nums[t - 1], nums[k - 1]);//此时t - 1就是第一个大于当前的数，进行交换 reverse(nums.begin() + k, nums.end());//翻转后面的降序序列变为升序 } } };32. 最长有效括号 难题，竞赛题。
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; } };没上面那么严谨但是也过了的代码：直接用之前的括号匹配的思路。
class Solution { public: int longestValidParentheses(string s) { stack<int> stk; int res = 0; stk.push(-1); for (int i = 0; i < s.size(); i++) { if (s[i] == '(') { stk.push(i); } else { stk.pop(); if (stk.empty()) stk.push(i); else res = max(res, i - stk.top()); } } return res; } };33. 搜索旋转排序数组 这一题就是一个典型的二分，可以先二分找到最小值的位置，再根据target的值来确定区间在前一半还是后一半。再用一次二分查找。
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]) r = l, 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; } };34. 在排序数组中查找元素的第一个和最后一个位置 依旧是二分，和上一题是一样的，剑指上其实也是有类似的题目的。
第一次二分查找第一个位置使得它的值 大于等于 target，若该位置的值不等于 target，则返回 [-1, -1]。第二次二分查找第一个位置使得它的值 大于 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; } if (nums[r] != target) return {-1, -1};//没找到直接返回 //找右边界 int L = r; l = L, 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}; } };35. 搜索插入位置 依旧是二分，不过比上面两道题的难度要低一些。这题其实也就是插入排序中的一部分。
class Solution { public: int searchInsert(vector<int>& nums, int target) { int l = 0, r = nums.size();//因为可能插到最后，所以是nums.size(),而不是nums.size() - 1 while (l < r) { int mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; } return l; } };36. 有效的数独 就是一个模拟题，模拟题就是考代码基本功了hh。
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { bool st[9]; //判断行 for (int i = 0; i < 9; i++) {//枚举每一行 memset(st, 0, sizeof st);//先把每一行的布尔数组清空 for (int j = 0; j < 9; j++) {//再来看每一行里的元素有没有重复的 if (board[i][j] != '.') {//当前位置不为空 int t = board[i][j] - '1';//用t来记录当前的数,将字符的1~9表示为数字的0~8，所以要-'1' if (st[t]) return false;//如果t之前出现过，则矛盾，不符合要求 st[t] = true;//否则就记录当前的数字 } } } //判断列，将ij对调即可 for (int i = 0; i < 9; i++) {//枚举每一列 memset(st, 0, sizeof st);//先把每一列的布尔数组清空 for (int j = 0; j < 9; j++) {//再来看每一行里的元素有没有重复的 if (board[j][i] != '.') {//当前位置不为空 int t = board[j][i] - '1';//用t来记录当前的数,将字符的1~9表示为数字的0~8，所以要-'1' if (st[t]) return false;//如果t之前出现过，则矛盾，不符合要求 st[t] = true;//否则就记录当前的数字 } } } //判断每个小方格 for (int i = 0; i < 9; i += 3) {//每一行，3个一跳，所以+3 for (int j = 0; j < 9; j += 3) {//每一列 memset(st, 0, sizeof st);//初始化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;//全部枚举完没有问题则说明合法 } };另一种写法：
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { vector<int> row(9), col(9), squ(9); // 使用三个整型数组判重。 for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) { if (board[i][j] == '.') continue; if (board[i][j] < '1' || board[i][j] > '9') return false; int num = board[i][j] - '0'; // 以row[i] & (1 << num)为例，这是判断第i行中，num数字是否出现过。 // 即row[i]值的二进制表示中，第num位是否是1。 // 以下col和squ同理。 if ((row[i] & (1 << num)) || (col[j] & (1 << num)) || (squ[(i / 3) * 3 + (j / 3)] & (1 << num))) return false; row[i] |= (1 << num); col[j] |= (1 << num); squ[(i / 3) * 3 + (j / 3)] |= (1 << num); } return true; }37. 解数独 解数独就是一个标准的暴搜问题了，dfs模板。
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);//从左上角开始dfs } bool dfs(vector<vector<char>>& board, int x, int y) { if (y == 9) x ++, y = 0;//纵坐标到头了(越界了)，让行号+1，列为0 if (x == 9) return true; if (board[x][y] != '.') return dfs(board, x, y + 1);//当前点不是'.',说明有数了，直接枚举下一个数 //否则就说明当前位置没有数，那么就枚举一下当前位置可以填哪些数 for (int i = 0; i < 9; i ++ ){ //第x行没有出现过，第j列没有出现过，所在的小九宫格页眉出现过 if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) { board[x][y] = '1' + i;//将xy这个位置填上数‘1’ + i row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;//填完之后记录已经填过了 if (dfs(board, x, y + 1)) return true;//dfs下一个格子，返回true说明找到了答案，直接返回 board[x][y] = '.';//恢复现场 row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false; } } return false;//最后都没找到，说明当前分支无解，返回false } };38. 外观数列
class Solution { public: string countAndSay(int n) { string s = "1";//第一项就是规定好的1 for (int i = 0; i < n - 1; i ++ ) {//求第n项，那么肯定要变换n - 1次 string t;//每次新的项用t来表示 for (int j = 0; j < s.size();) {//找前一段相同的数 int k = j + 1;//k从j + 1开始找 while (k < s.size() && s[k] == s[j]) k ++ ;//只要相同就一直往后找 t += to_string(k - j) + s[j];//t就加上对应的个数 j = k;//j移到下一个位置 } s = t;//将s更新成t即可 } return s; } };39. 组合总和 这题是没法用完全背包做的，因为要求的是所有方案；所以直接暴搜，递归枚举，暴搜问题主要考虑的就是一个搜索顺序的问题，按照什么样的顺序可以不重不漏。
class Solution { public: vector<vector<int>> ans;//记录所有的答案 vector<int> path;//满足条件的方案 vector<vector<int>> combinationSum(vector<int>& candidates, int target) { dfs(candidates, 0, target);//从第一个数开始，从前往后dfs一遍 return ans;//返回答案即可 } //dfs暴搜一遍，传入数组，当前枚举到第几个数了，需要凑的值 void dfs(vector<int>& candidates, int u, int target) { //每次的target都会减去前一个数，所以当target减到0说明已经找到了一组解 if (target == 0) { ans.push_back(path); return; } //如果枚举完了所有的数还是没有凑出target，说明当前分支无解，直接return if (u == candidates.size()) return; //枚举一下当前的数可以选几个,可以选0个，或者选i个总和不超过target的个数 for (int i = 0; i * candidates[u] <= target; i++) { //第一次选了0个，也就是什么都没选，所以直接dfs下一个 dfs(candidates, u + 1, target - i *candidates[u]); path.push_back(candidates[u]);//把选的元素加到答案中 } //最后再恢复现场即可 for (int i = 0; i * candidates[u] <= target; i++) { path.pop_back(); } } };40. 组合总和 II
做法与上一题很类似，只不过本题是每个数字仅用一次。此题需要排序，目的是为了防止重复。防止重复的方法是，搜索时如果不想要当前层的数字，则需要找到下一个与之不同的数字才可以进行下一层的搜索。 class Solution { public: vector<vector<int>> ans; vector<int> path; vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end());//排序，方便枚举每一段 dfs(candidates, 0, target); return ans; } void dfs(vector<int>& candidates, int u, int target) { if (target == 0) { ans.push_back(path); return; } if (u == candidates.size()) return; //找到每一段的起始 int k = u + 1; while (k < candidates.size() && candidates[k] == candidates[u]) k++; int cnt = k - u;//每一段有cnt个相同的数，枚举的个数不能超过cnt //枚举一下当前的数可以选几个,可以选0个，或者选i个总和不超过target的个数并且不能超过cnt个 for (int i = 0; i * candidates[u] <= target && i <= cnt; i++) { dfs (candidates, k, target - i * candidates[u]); path.push_back(candidates[u]); } //恢复现场 for (int i = 0; i * candidates[u] <= target && i <= cnt; i++) { path.pop_back(); } } };