LeetCode 第 51 题
在一个 N×N 的国际象棋棋盘上放置 N 个皇后，每行一个并使她们不能互相攻击。给定一个整数 N，返回 N 皇后不同的的解决方案的数量。
解题思路
解决 N 皇后问题的关键就是如何判断当前各个皇后的摆放是否合法。
class Solution {List<int[]> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {if(n == 0){return null;}int[] columns = new int[n];backtracking(0, columns, n);List<List<String>> ret = new ArrayList<>();for(int[] solution : res){List<String> element = new ArrayList<>();for(int i = 0; i < n; i++){int QPos = solution[i];char[] tempCharArray = new char[n];for(int k = 0; k < n; k++){tempCharArray[k] = '.';}tempCharArray[QPos] = 'Q';String tmpString = new String(tempCharArray);element.add(tmpString);}ret.add(element);}return ret;}public void backtracking(int row, int[] columns, int n){if(row == n){int[] a2 = Arrays.copyOf(columns, n);res.add(a2);return;}//尝试将皇后放置在每一列 for(int i = 0; i < n; i++){if(check(row, i, columns)){columns[row] = i;backtracking(row + 1, columns, n);}columns[row] = -1;}}public boolean check(int row, int col, int[] columns){//出错i < row，而不是nfor(int i = 0; i < row; i++){if(col == columns[i] || Math.abs(row - i) == Math.abs(col - columns[i])){return false;}}return true;}
}解题心得:
<1>无法直接Arrays.asList(int[]);因为只有包装类才能作为参数，需要要转换成Integer[]
<2>思路正确，但在判断位置是否有效（check)函数中，i的判断条件是i < row,而非i < n,否则永远为false, 因为自己和自己肯定是在同一行啦~555(排错了近一个小时)