【代码随想录day25】【C++复健】491.递增子序列；46.全排列；47.全排列 II；51. N皇后；37. 解数独

491.递增子序列

本题做的时候除了去重逻辑之外，其他的也勉强算是写出来了，不过还是有问题的，总结如下：

1 本题的关键：去重

与其说是不知道用什么去重，更应该说是完全没想到本题需要去重，说明这种题光靠干想还是不太行的。

要想去重，本质上还是要想明白什么情况会发生重复。对于本题来说，就是在同一个循环内，相同的数出现第二次的时候。

在递归生成子序列的过程中，代码中的每个循环代表一次“选择”操作。在同一层循环内，两个相同的数被选择所形成的结果是相同的，尽管它们可能出现在不同的位置，但生成的子序列完全一致。如果在同一层循环中选择了两个相同的数，那么这两个数选择后生成的子序列将发生重复。

还有最后一个问题，为什么是哈希表？ 

我们前面也有说过，发生重复的情况就是同一循环内相同的数出现两次。那看一个数出没出现过的最快的方法？当然就是哈希了。

2 分治问题

这个题倒是学会分治了，把递增的判断专门写了一个函数，但其实每次只要和vector的尾部判断就行了，完全不需要写一个函数，属于是ptsd了，然后就没去细想，另外也可以说是没想明白递归就可以完美解决递增判断的问题。

3 对于递归当中每个部分的作用的不熟悉

一开始写for循环的时候写成了这样：

for(int i=startindex; i<nums.size(); i++){path.push_back(nums[i]);if(isup(path)){result.push_back(path);}all(nums, i+1, path, result);path.pop_back();all(nums, i+1, path, result);}

没去重是一方面，还写了两遍递归，当时想法是每次循环，每个值有取或者不取两个选项，所以取一个递归，不取一个递归。但不取的那个递归其实是在下一个for循环里涵盖了的，加上了才是多余的。

class Solution {
public:vector<vector<int>> findSubsequences(vector<int>& nums) {int startindex = 0;vector<vector<int>> result;vector<int> path;all(nums, startindex, path, result);return result;}void all(vector<int>& nums, int startindex, vector<int>& path, vector<vector<int>>& result){if(startindex == nums.size()){return ;}unordered_set<int> used;for(int i=startindex; i<nums.size(); i++){if (used.find(nums[i]) != used.end()) continue;path.push_back(nums[i]);used.insert(nums[i]);if(isup(path)){result.push_back(path);}all(nums, i+1, path, result);path.pop_back();//all(nums, i+1, path, result);}}bool isup(const vector<int>& path){int n = path.size();if(n < 2){return false;}int max = -101;for(int i=0; i<n; i++){if(path[i] >= max){max = path[i];}else{return false;}}return true;}
};

可以看到我上面的代码还是很麻烦的，不仅体现在代码量上，还有计算量其实也比只判断队尾元素要大上不少。

46.全排列

这个题想的时候想了半天怎么去判断一个数组当中的各个元素有没有被用过。最终我想到的办法是一个二维数组，第一个维度是每个元素，第二个维度是对应它们有没有被使用过。想好之后直接去看了解析（因为我觉的我这个肯定想复杂了）一看果然如此，第一个维度完全没有必要，直接用下标就可以把值和用没用过的两个数组进行对应。

在看完解析之后写代码也是没遇到太大的问题的，就是还是在判断结束条件的时候写的复杂了一点：

        bool allused = true;for(int i=0; i<nums.size(); i++){if(used[i]==1){allused = false;break;}}

直接定义了一个布尔值来判断每个元素是否都被用过了，但其实不必如此，其实我后来也想明白了并且注释掉了，改成了判断path的长度和nums是否一致，这个才是更简洁更快的办法。

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<int> used(nums.size());vector<int> path;vector<vector<int>> result;all(nums, used, path, result);return result;}void all(vector<int>& nums, vector<int>& used, vector<int>& path, vector<vector<int>>& result){// bool allused = true;// for(int i=0; i<nums.size(); i++){//     if(used[i]==1){//         allused = false;//         break;//     }// }if(path.size() == nums.size()){result.push_back(path);return;}for(int i=0; i<nums.size(); i++){if(used[i]==1){continue;}path.push_back(nums[i]);used[i] = 1;all(nums, used, path, result);path.pop_back();used[i] = 0;}}
};

47.全排列 II

本题也是差点一遍做出来，不过对于去重的判断还是不够理解，所以导致一遍并没有成功。

首先，我们也要先理解为什么这道题在什么情况下会发生重复。

一开始没有细想，写了一个if(i>0 && nums[i] == nums[i-1])，但这个的意思是说，只要相同的出现第二回就视为重复。但实际情况是，我先输入一个1，然后再来一个1，这个时候的11和只有一个1显然是不同的，所以我又想，应该再加一个条件，那就是前一个元素没被用过，也就是used[i-1]==false。加上之后就成功通过了，但卡哥的used[i - 1] == true 也行，used[i - 1] == false 也行有给我干懵了，如果是true的情况下，又是什么逻辑？

冥思苦想很久之后去看了解析，看完之后沉默了。因为虽然说了很多树层树枝去重什么的，但感觉是在从结果上反推的，如果不画出图来根本不知道true的情况是怎么一个运作逻辑，所以个人认为就按false这个来会比较好。

class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> result;vector<int> path;vector<int> used(nums.size());permute(nums, used, result, path);return result;}void permute(vector<int>& nums, vector<int>& used, vector<vector<int>>& result, vector<int>& path){if(path.size() == nums.size()){result.push_back(path);return;}for(int i=0; i<nums.size(); i++){if(used[i] == 1){continue;}if(i>0 && nums[i] == nums[i-1] && used[i-1] == false){continue;}used[i] = 1;path.push_back(nums[i]);permute(nums, used, result, path);path.pop_back();used[i] = 0;}}
};

51. N皇后

这个题其实对我的意义还是很特殊的。

在我还是一个懵懂无知的大一少年时，一道n皇后粉碎了我的ACM梦。

冥思苦想许久后，一顿操作猛如虎，一看过了5%。

依然记得当时我在草稿纸上画棋盘格，试图找到答案组成的数组规律的狼狈样子（当时那个题好像是问n*n格有多少种方法，比这个可能简单一点？）...

后面和同学去抱怨，却得到了“这个题很经典，你应该会”的回答。

现在已经是能把这个题做出来的人了，回想同学的话，很有道理，但是我却有些会错了意。

题目很“经典”，所以不会做的我很“废材”，这样的逻辑关系是不存在的。因为对于我来说，这个题我没有见过，所以它不是经典题，而是一个全新的，并且很难的题，这样的题，或者哪怕是一个很简单很简单的题，只要我没做过，我都有不会的权力。“应该会”这个词背后的意义是“去了解”，而不是“不会的话，你就很废”，可惜我到现在才想明白。

不过总之，现在做完了这道题的我，也算是迈出那一步了吧。

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<string> chessboard;string str = "";for(int i=0; i<n; i++){str += ".";}for(int i=0; i<n; i++){chessboard.push_back(str);}int row = 0;vector<vector<string>> result;backtracking(chessboard, n, row, result);return result;}void backtracking(vector<string>& chessboard, int n, int row, vector<vector<string>>& result){if(row == n){result.push_back(chessboard);return;}for(int i = 0; i < n; i++){if(isvalid(row, i, chessboard, n)){chessboard[row][i] = 'Q';backtracking(chessboard, n, row+1, result);chessboard[row][i] = '.';}}}bool isvalid(int row, int col, vector<string>& chessboard, int n){int yoko = row - 1;int tate = col - 1;while(yoko >=0 && tate>=0){if(chessboard[yoko][tate] == 'Q'){return false;}yoko--;tate--;}yoko = row - 1;tate = col + 1;while(yoko >= 0 && tate < n){if(chessboard[yoko][tate] == 'Q'){return false;}yoko--;tate++;}yoko = row - 1;tate = col;while(yoko>=0){if(chessboard[yoko][tate] == 'Q'){return false;}yoko--;}return true;}
};

 哪怕现在刷完回溯，以及前面那么多部分的题，再来看这个N皇后，都绝对没法说这是一个简单的题目。就像我在看完解析之后依然遇到了不少的问题：

1 二维棋盘的初始化方法

我写的这么多代码：

        vector<string> chessboard;string str = "";for(int i=0; i<n; i++){str += ".";}for(int i=0; i<n; i++){chessboard.push_back(str);}

其实用这一句： 

vector<string> chessboard(n, string(n, '.'));

就可以等效了。

那为什么没写出来呢，鉴定为对于构造函数的不熟悉，无论是string还是vector都能用类似这种构造方式。

2 写判断的时候行和列没搞清楚 

写的列判断写成了行判断，并且右上对角线写成了左下对角线。这个也是对二维数组不熟悉导致的，还需要多练多熟悉。

37. 解数独

看了解析视频之后做的，不过还是遇到了一点麻烦：
1 传参给isvalid的时候没像卡哥一样传一个值和board，而是把值先插入board之后再传的。这样看似差不多，实则是个超级大麻烦：横着竖着和九宫格必须跳过i,j位置所对应的元素，极其麻烦，横着竖着尚可以分成两段，九宫格直接不知道怎么写了。

2 其实如果传val也不太知道就功能怎么处理，差点就用枚举法了。像这种先/3再乘3是很聪明的处理方式：int startRow = (row / 3) * 3;

并且还知道了这样写会变成离row最近的3的倍数，而不是变成row。也就是每个中间步都仍然是int。

class Solution {
public:void solveSudoku(vector<vector<char>>& board) {backtracking(board);}bool backtracking(vector<vector<char>>& board){for(int i = 0; i < board.size(); i++){for(int j = 0; j < board[0].size(); j++){if(board[i][j] == '.'){for(char p = '1'; p <= '9'; p++){if(isvalid(board, i, j, p)){board[i][j] = p;if(backtracking(board)){return true;}board[i][j] = '.';}}return false;}}}return true;}bool isvalid(vector<vector<char>>& board, int row, int col, int val){for(int i = 0; i < row; i++){if(board[i][col] == val){return false;}}for(int i = 8; i > row; i--){if(board[i][col] == val){return false;}}for(int j = 0; j < col; j++){if(board[row][j] == val){return false;}}for(int j = 8; j > col; j--){if(board[row][j] == val){return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) {for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val) {return false;}}}return true;}
};

写的还是麻烦了的，不过太困了，就不优化了。