移动网站设计心得,网站推广引流,电商公司名字大全,废橡胶网站建设#xff3b;抄题#xff3d;#xff1a; n皇后问题是将n个皇后放置在n*n的棋盘上#xff0c;皇后彼此之间不能相互攻击。 给定一个整数n#xff0c;返回所有不同的n皇后问题的解决方案。 每个解决方案包含一个明确的n皇后放置布局#xff0c;其中“Q”和“.”分别表示一个…抄题 n皇后问题是将n个皇后放置在n*n的棋盘上皇后彼此之间不能相互攻击。 给定一个整数n返回所有不同的n皇后问题的解决方案。 每个解决方案包含一个明确的n皇后放置布局其中“Q”和“.”分别表示一个女王和一个空位置。 对于4皇后问题存在两种解决的方案 [ [.Q.., // Solution 1 ...Q, Q..., ..Q.], [..Q., // Solution 2 Q..., ...Q, .Q..] ] 思维问题 看不懂特殊情况主要是要区别x y 一句话思路 DFS去掉特殊情况后画图 输入量空 正常情况特大特小程序里处理到的特殊情况异常情况不合法不合理的输入 画图 一刷 search函数可以是空类型不返回search函数返回其中的results即可。cols链表是后续函数的参数此处需要新建链表。如果辅助链表cols满了需要在结果数组中添加画图之后直接返回results。cols是数组画成图才是链表drawCheesboard方法中需要新建一个chessboard数组作为最后返回的结果。 sb.append(j cols.get(i) ? Q : .);表示j如果到达x有值处就打印Q判断函数要有默认的return true 此函数判断的是cols,column是否有效因此全部行通过后返回true 二刷 三刷 四刷 五刷 [五分钟肉眼debug的结果] 总结 search函数用的DFS回溯是关键 复杂度Time complexity: O(分支的深度次方) Space complexity: O(分支*深度) 英文数据结构或算法为什么不用别的数据结构或算法 DFS找出全部方法 其他解法 Follow Up LC给出的题目变变变 Nqueen第二版改参数不行 暂时算了吧 [代码风格] 规律返回值和函数类型是相同的 class Solution {/*** Get all distinct N-Queen solutions* param n: The number of queens* return: All distinct solutions* For example, A string ...Q shows a queen on forth position*/ListListString solveNQueens(int n) {ListListString results new ArrayList();if (n 0) {return results;}search(results, new ArrayListInteger(), n);return results;}/** results store all of the chessboards* cols store the column indices for each row*/private void search(ListListString results,ListInteger cols,int n) {if (cols.size() n) {results.add(drawChessboard(cols));return;}for (int colIndex 0; colIndex n; colIndex) {if (!isValid(cols, colIndex)) {continue;}cols.add(colIndex);search(results, cols, n);cols.remove(cols.size() - 1);}}private ListString drawChessboard(ListInteger cols) {ListString chessboard new ArrayList();for (int i 0; i cols.size(); i) {StringBuilder sb new StringBuilder();for (int j 0; j cols.size(); j) {sb.append(j cols.get(i) ? Q : .);}chessboard.add(sb.toString());}return chessboard;}private boolean isValid(ListInteger cols, int column) {int row cols.size();for (int rowIndex 0; rowIndex cols.size(); rowIndex) {if (cols.get(rowIndex) column) {return false;}if (rowIndex cols.get(rowIndex) row column) {return false;}if (rowIndex - cols.get(rowIndex) row - column) {return false;}}return true;}
} View Code 转载于:https://www.cnblogs.com/immiao0319/p/8410050.html
