首页 > 代码库 > Leetcode: N-Queens II
Leetcode: N-Queens II
Follow up for N-Queens problem.Now, instead outputting board configurations, return the total number of distinct solutions.
跟N-Queen的考虑方式完全一样，NP问题，用循环递归处理子问题，具体做法就是：用循环去把皇后依次放在一行中的某列，如果这样放合法，然后就递归处理下一步，直到row=n说明 0到n-1行都已经处理完毕。这是得到一个合理的solution，把它加入result中
套路就是用一个循环去枚举当前所有情况，把元素加入，递归下一步，再把元素删除。
需要注意传值的问题，本题要传一个sum，如果直接定义一个integer来做sum，然后作为函数参数传入，递归之后再来检查sum的值，sum是不会有改变的，因为值传递，方法不会改变实参的值。所以用ArrayList<Integer>作为参数传入，这是一个对象，对象类型参数：传引用，方法体内改变形参引用，不会改变实参的引用，但有可能改变实参对象的属性值。
1 public class Solution { 2 public int totalNQueens(int n) { 3 ArrayList<Integer> res = new ArrayList<Integer>(); 4 res.add(0); 5 helper(n, 0, new int[n], res); 6 return res.get(0); 7 } 8 9 public void helper(int n, int row, int[] ColForRow, ArrayList<Integer> res) {10 if (row == n) { //find a suitable solution11 res.set(0, res.get(0) + 1);12 return;13 }14 for (int k = 0; k < n; k++) {15 ColForRow[row] = k;16 if (check(row, ColForRow)) {17 helper(n, row+1, ColForRow, res);18 }19 }20 }21 22 public boolean check(int row, int[]ColForRow) {23 for (int i = 0; i < row; i++) {24 if (ColForRow[i] == ColForRow[row] || Math.abs(ColForRow[i] - ColForRow[row]) == Math.abs(i - row)) {25 return false;26 }27 }28 return true;29 }30 }
Leetcode: N-Queens II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。