https://leetcode.com/problems/n-queens/
回溯问题
做出来不难，但是空间复杂度有优化空间，我的做法是O(n2)，实际可以到O(n)
最优解：
保存三个cache数组，一个记录col已经被占用的位置，另外两个记录对角线被占用的位置。d1=rowCur+j d2=j-rowCur+n-1，d1、d2可以判断当前位置相对于对角线是否valid。
巧用API的重要性，大大简化代码量！！
public class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> res = new LinkedList<>(); if (n < 1) return res; backTrace(res, new LinkedList<String>(), 0, n, new boolean[n], new boolean[n * 2], new boolean[n * 2]); return res; } private void backTrace(List<List<String>> res, LinkedList<String> part, int curRow, int n, boolean[] col, boolean[] d1, boolean[] d2) { if (curRow == n) { res.add(new LinkedList<String>(part)); return; } for (int i = 0; i < n; i++) { int t1 = i + curRow, t2 = n - i - 1 + curRow; if (!col[i] && !d1[t1] && !d2[t2]) { col[i] = true; d1[t1] = true; d2[t2] = true; char[] arr = new char[n]; Arrays.fill(arr, '.'); arr[i] = 'Q'; part.add(new String(arr)); backTrace(res, part, curRow + 1, n, col, d1, d2); col[i] = false; d1[t1] = false; d2[t2] = false; part.remove(part.size() - 1); } } } }
我的解法：
保存二维cache
public class Solution { boolean[][] cache; int n; public List<List<String>> solveNQueens(int n) { LinkedList<List<String>> res = new LinkedList<>(); if (n <= 0) return res; cache = new boolean[n][n]; this.n = n; for (int i = 0; i < n; i++) { cache[0][i] = true; dfs(1, res); cache[0][i] = false; } return res; } private void dfs(int i, LinkedList<List<String>> res) { if (i == n) { LinkedList<String> temp = new LinkedList<>(); for (int j = 0; j < n; j++) { StringBuilder sb = new StringBuilder(); for (int k = 0; k < n; k++) { if (cache[j][k]) { sb.append("Q"); } else { sb.append("."); } } temp.add(sb.toString()); } res.add(temp); return; } for (int j = 0; j < n; j++) { if (valid(i, j)) { cache[i][j] = true; dfs(i + 1, res); cache[i][j] = false; } } } private boolean valid(int row, int col) { for (int i = 0; i < row; i++) { for (int j = 0; j < n; j++) { if (cache[i][j] && (j == col || (Math.abs(i - row) == Math.abs(j - col)))) return false; } } return true; } }
