邵阳公司网站建设,软件开发平台合同,网页界面设计包括哪些,众筹网站怎么做自己写的#xff1a;
①想自己定义结构体node#xff0c;发现find函数太麻烦。看了眼模板#xff0c;就用一个vectorint记录行号就行#xff0c;索引自然而然就是列号。
②想用for循环写#xff08;未通过#xff09;
还在想这和模拟差不多。后来才意识到
①想自己定义结构体node发现find函数太麻烦。看了眼模板就用一个vectorint记录行号就行索引自然而然就是列号。
②想用for循环写未通过
还在想这和模拟差不多。后来才意识到还得是递归啊。
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param n int整型 the n* return int整型*/bool inGroup(vectorint huanghouGroup, int x1, int n){// 检验的点第x1行第y1列int y1 huanghouGroup.size();for(int y2 0; y2 y1; y2){// huanghouGroup里的点第x2行第y2列int x2 huanghouGroup[y2];// huanghouGroup里有在第x1行摆下皇后if( x2 x1 )return true;// 是对角线 abs(1.0*(列-列)/(行-行)) 1.0 if(abs(1.0 * (y1 - y2) / (x1 - x1) ) 1.0)return true;}return false;}void dfs(vectorint huanghouGroup, int y, int x, int n){if(y n)return;if(inGroup(huanghouGroup, x, n))return;for(int j 0; j n; j){dfs(huanghouGroup, y1, j, n);}}int Nqueen(int n) {// write code herevectorvectorint res;for (int i 0; i n; i) { //第0列遍历所有行coutiendl;vectorint huanghouGroup; //记录每列的行号huanghouGroup.push_back(i); //第0列第i行摆下皇后int flag 0; //该策略可行for (int j 1; j n; j) { //第1列开始遍历for(int k 0; k n; k){ //第j列遍历所有行//如果可以放下皇后if (!inGroup(huanghouGroup,k,n)){huanghouGroup.push_back(k);break; //粗心忘记加了,【此时此刻意识到该用dfs】}}if (huanghouGroup.size() ! j 1) { //第j列所有行都遍历完了却没有放下皇后flag 1;break;}}//如果这种策略可行并且之前没有出现过if(flag 0 find(res.begin(), res.end(), huanghouGroup) res.end())res.push_back(huanghouGroup);}return res.size();}
};
③递归通过
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param n int整型 the n* return int整型*/bool inGroup(vectorint huanghouGroup, int x1, int n) {// 检验的点第x1行第y1列int y1 huanghouGroup.size();for (int y2 0; y2 y1; y2) {// huanghouGroup里的点第x2行第y2列int x2 huanghouGroup[y2];// huanghouGroup里有在第x1行摆下皇后if (x2 x1)return true;// 是对角线 abs(1.0*(列-列)/(行-行)) 1.0 if (abs(1.0 * (y1 - y2) / (x1 - x2)) 1.0)return true;}return false;}void dfs(vectorvectorint res, vectorint huanghouGroup, int y, int x, int n) { //第y列第x行if (inGroup(huanghouGroup, x, n))return;huanghouGroup.push_back(x);if (y n-1) { res.push_back(huanghouGroup);return;}for (int j 0; j n; j) {dfs(res, huanghouGroup, y 1, j, n);}huanghouGroup.pop_back();}int Nqueen(int n) {// write code herevectorvectorint res;vectorint huanghouGroup; //记录每列的行号for (int i 0; i n; i) {dfs(res, huanghouGroup, 0, i, n);}return res.size();}
};
注
采用for循环里push的方法结果会多出n个重复的策略方案。因为在for循环里push需要在下一次递归里面判断长度和放入res最终导致倒数第二层已经是我们需要的答案了但是在for循环会重复n次递归在最后一层判断长度和放入res。
void dfs(vectorvectorint res, vectorint huanghouGroup, int y, int x, int n) { if (inGroup(huanghouGroup, x, n))return;if (y n) { res.push_back(huanghouGroup);return;}for (int j 0; j n; j) {huanghouGroup.push_back(x);dfs(res, huanghouGroup, y 1, j, n);huanghouGroup.pop_back();}}
for循环外面push就能解决重复答案的问题。调试很久判断长度。
void dfs(vectorvectorint res, vectorint huanghouGroup, int y, int x, int n) if (inGroup(huanghouGroup, x, n))return;huanghouGroup.push_back(x);if (y n-1) { //调式很久判断长度不是(y n)res.push_back(huanghouGroup);return;}for (int j 0; j n; j) {dfs(res, huanghouGroup, y 1, j, n);}huanghouGroup.pop_back();}
