首页 > 代码库 > LeetCode: N-Queens II 解题报告
LeetCode: N-Queens II 解题报告
N-Queens II (LEVEL 4 难度级别，最高级5)
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the totalnumber of distinct solutions.
解答：
与第一题的解法是类似的，不同之处是，DFS的返回值是解的个数。我们每一次搜索本行8个位置时，
把8个位置的解都加在一起就行了。有的位置无解，它的返回值就是0咯。
另外注意BASE CASE:
当row == size时，也就是row越界了，这时意思是整个N-Queen都摆满了，我们这时应返回解为1.因为
你不需要任何动作，也就是唯一的解是保持原状。（虽然有点难以理解），同学可以退回到上一层来想
比如最后一行，你放置了一个皇后，它就是1个解，所以在那里dfs到下一层应该返回1.
1 public class Solution { 2 public int totalNQueens(int n) { 3 if (n == 0) { 4 return 0; 5 } 6 7 // Bug 1: forget to modify the parameters of the function. 8 return dfs(n, 0, new ArrayList<Integer>()); 9 }10 11 public int dfs(int n, int row, ArrayList<Integer> path) {12 if (row == n) {13 // The base case: 当最后一行，皇后只有1种放法(就是不放)14 return 1;15 }16 17 int num = 0;18 19 // The queen can select any of the slot.20 for (int i = 0; i < n; i++) {21 if (!isValid(path, i)) {22 continue;23 }24 path.add(i);25 26 // All the solutions is all the possiablities are add up.27 num += dfs(n, row + 1, path);28 path.remove(path.size() - 1);29 }30 31 return num;32 }33 34 public boolean isValid(ArrayList<Integer> path, int col) {35 int size = path.size();36 for (int i = 0; i < size; i++) {37 // The same column with any of the current queen.38 if (col == path.get(i)) {39 return false;40 }41 42 // diagonally lines.43 // Bug 2: forget to add a ‘)‘44 if (size - i == Math.abs(col - path.get(i))) {45 return false;46 }47 }48 49 return true;50 }51 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/dfs/totalNQueens_1218_2014.java
LeetCode: N-Queens II 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。