Leetcode: N-Queens II
LeetCode II queens
2023-09-11 14:14:08 时间
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 solution 11 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: Max Consecutive Ones II(unsolved locked problem)
- Leetcode: Group Shifted Strings
- LeetCode Jump Game II
- JS Leetcode 503. 下一个更大元素 II 题解分析,依旧单调栈做法解决此题
- [LeetCode] Linked List Cycle II
- [LeetCode]657. 机器人能否返回原点
- 124、【回溯算法】leetcode ——46. 全排列(C++版本)
- 【数据结构/哈希表】leetcode刷题路线(持续更新)
- 【LeetCode】Add Two Numbers
- 【LeetCode】63. Unique Paths II
- 【LeetCode】90. Subsets II (2 solutions)
- 【Leetcode】Linked List Cycle II
- 【leetcode】92:反转链表 II
- [LeetCode] 790. Domino and Tromino Tiling 多米诺和三格骨牌
- [LeetCode] Beautiful Arrangement II 优美排列之二
- [LeetCode] 407. Trapping Rain Water II 收集雨水之二
- [LeetCode] Integer Replacement 整数替换
- [LeetCode] Super Ugly Number 超级丑陋数
- [LeetCode] Word Break II 拆分词句之二
- [LeetCode] 63. Unique Paths II 不同的路径之二
- [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二
- leetcode 287. Find the Duplicate Number 寻找重复数 (中等)