织梦网站修改教程视频教程,珠海市网站建设的公司,线上兼职的正规网站,松滋做网站491.递增子序列
本题做的时候除了去重逻辑之外#xff0c;其他的也勉强算是写出来了#xff0c;不过还是有问题的#xff0c;总结如下#xff1a;
1 本题的关键#xff1a;去重
与其说是不知道用什么去重#xff0c;更应该说是完全没想到本题需要去重#xff0c;说明…491.递增子序列
本题做的时候除了去重逻辑之外其他的也勉强算是写出来了不过还是有问题的总结如下
1 本题的关键去重
与其说是不知道用什么去重更应该说是完全没想到本题需要去重说明这种题光靠干想还是不太行的。
要想去重本质上还是要想明白什么情况会发生重复。对于本题来说就是在同一个循环内相同的数出现第二次的时候。
在递归生成子序列的过程中代码中的每个循环代表一次“选择”操作。在同一层循环内两个相同的数被选择所形成的结果是相同的尽管它们可能出现在不同的位置但生成的子序列完全一致。如果在同一层循环中选择了两个相同的数那么这两个数选择后生成的子序列将发生重复。 还有最后一个问题为什么是哈希表
我们前面也有说过发生重复的情况就是同一循环内相同的数出现两次。那看一个数出没出现过的最快的方法当然就是哈希了。 2 分治问题
这个题倒是学会分治了把递增的判断专门写了一个函数但其实每次只要和vector的尾部判断就行了完全不需要写一个函数属于是ptsd了然后就没去细想另外也可以说是没想明白递归就可以完美解决递增判断的问题。 3 对于递归当中每个部分的作用的不熟悉
一开始写for循环的时候写成了这样
for(int istartindex; inums.size(); i){path.push_back(nums[i]);if(isup(path)){result.push_back(path);}all(nums, i1, path, result);path.pop_back();all(nums, i1, path, result);}
没去重是一方面还写了两遍递归当时想法是每次循环每个值有取或者不取两个选项所以取一个递归不取一个递归。但不取的那个递归其实是在下一个for循环里涵盖了的加上了才是多余的。
class Solution {
public:vectorvectorint findSubsequences(vectorint nums) {int startindex 0;vectorvectorint result;vectorint path;all(nums, startindex, path, result);return result;}void all(vectorint nums, int startindex, vectorint path, vectorvectorint result){if(startindex nums.size()){return ;}unordered_setint used;for(int istartindex; inums.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, i1, path, result);path.pop_back();//all(nums, i1, path, result);}}bool isup(const vectorint path){int n path.size();if(n 2){return false;}int max -101;for(int i0; in; i){if(path[i] max){max path[i];}else{return false;}}return true;}
};
可以看到我上面的代码还是很麻烦的不仅体现在代码量上还有计算量其实也比只判断队尾元素要大上不少。 46.全排列
这个题想的时候想了半天怎么去判断一个数组当中的各个元素有没有被用过。最终我想到的办法是一个二维数组第一个维度是每个元素第二个维度是对应它们有没有被使用过。想好之后直接去看了解析因为我觉的我这个肯定想复杂了一看果然如此第一个维度完全没有必要直接用下标就可以把值和用没用过的两个数组进行对应。
在看完解析之后写代码也是没遇到太大的问题的就是还是在判断结束条件的时候写的复杂了一点 bool allused true;for(int i0; inums.size(); i){if(used[i]1){allused false;break;}}
直接定义了一个布尔值来判断每个元素是否都被用过了但其实不必如此其实我后来也想明白了并且注释掉了改成了判断path的长度和nums是否一致这个才是更简洁更快的办法。
class Solution {
public:vectorvectorint permute(vectorint nums) {vectorint used(nums.size());vectorint path;vectorvectorint result;all(nums, used, path, result);return result;}void all(vectorint nums, vectorint used, vectorint path, vectorvectorint result){// bool allused true;// for(int i0; inums.size(); i){// if(used[i]1){// allused false;// break;// }// }if(path.size() nums.size()){result.push_back(path);return;}for(int i0; inums.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(i0 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:vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());vectorvectorint result;vectorint path;vectorint used(nums.size());permute(nums, used, result, path);return result;}void permute(vectorint nums, vectorint used, vectorvectorint result, vectorint path){if(path.size() nums.size()){result.push_back(path);return;}for(int i0; inums.size(); i){if(used[i] 1){continue;}if(i0 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:vectorvectorstring solveNQueens(int n) {vectorstring chessboard;string str ;for(int i0; in; i){str .;}for(int i0; in; i){chessboard.push_back(str);}int row 0;vectorvectorstring result;backtracking(chessboard, n, row, result);return result;}void backtracking(vectorstring chessboard, int n, int row, vectorvectorstring 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, row1, result);chessboard[row][i] .;}}}bool isvalid(int row, int col, vectorstring chessboard, int n){int yoko row - 1;int tate col - 1;while(yoko 0 tate0){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(yoko0){if(chessboard[yoko][tate] Q){return false;}yoko--;}return true;}
}; 哪怕现在刷完回溯以及前面那么多部分的题再来看这个N皇后都绝对没法说这是一个简单的题目。就像我在看完解析之后依然遇到了不少的问题
1 二维棋盘的初始化方法
我写的这么多代码 vectorstring chessboard;string str ;for(int i0; in; i){str .;}for(int i0; in; i){chessboard.push_back(str);}
其实用这一句
vectorstring 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(vectorvectorchar board) {backtracking(board);}bool backtracking(vectorvectorchar 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(vectorvectorchar 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;}
};
写的还是麻烦了的不过太困了就不优化了。
