My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<String>> solveNQueens(int n) {
if (n <= 0)
return null;
ArrayList<List<String>> ret = new ArrayList<List<String>>();
ArrayList<String> queens = new ArrayList<String>();
boolean[][] isVisited = new boolean[n][n];
helper(0, isVisited, ret, queens);
return ret;
}
private boolean helper(int i, boolean[][] isVisited,
ArrayList<List<String>> ret, ArrayList<String> queens) {
int row = isVisited.length;
int col = isVisited.length;
if (i >= row) {
ret.add(new ArrayList<String>(queens));
return true;
}
else {
boolean isQueen = false;
for (int k = 0; k < col; k++) {
if (!isVisited[i][k]) {
boolean[][] isVisitedCurr = visit(i, k, isVisited);
String queen = formString(k, col);
queens.add(queen);
isQueen |= helper(i + 1, isVisitedCurr, ret, queens);
queens.remove(queens.size() - 1);
}
}
return isQueen;
}
}
private boolean[][] visit(int i, int j, boolean[][] isVisitedOld) {
int row = isVisitedOld.length;
int col = isVisitedOld.length;
boolean[][] isVisited = new boolean[row][col];
for (int m = 0; m < row; m++)
for (int n = 0; n < col; n++)
isVisited[m][n] = isVisitedOld[m][n];
isVisited[i][j] = true;
int left = j - 1;
while (left >= 0)
isVisited[i][left--] = true;
int right = j + 1;
while (right < col)
isVisited[i][right++] = true;
int up = i - 1;
while (up >= 0)
isVisited[up--][j] = true;
int down = i + 1;
while (down < row)
isVisited[down++][j] = true;
int leftUp = 1;
while (i - leftUp >= 0 && j - leftUp >= 0) {
isVisited[i - leftUp][j - leftUp] = true;
leftUp++;
}
int rightUp = 1;
while (i - rightUp >= 0 && j + rightUp < col) {
isVisited[i - rightUp][j + rightUp] = true;
rightUp++;
}
int leftDown = 1;
while (i + leftDown < row && j - leftDown >= 0) {
isVisited[i + leftDown][j - leftDown] = true;
leftDown++;
}
int rightDown = 1;
while (i + rightDown < row && j + rightDown < col) {
isVisited[i + rightDown][j + rightDown] = true;
rightDown++;
}
return isVisited;
}
private String formString(int k, int col) {
String queen = "";
for (int i = 0; i < k; i++)
queen += ".";
queen += "Q";
for (int i = k + 1; i < col; i++)
queen += ".";
return queen;
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.solveNQueens(2));
}
}
基本一遍過了N皇后。贪惹。苏章。
感覺自己強暴了。。枫绅。泉孩。
爆炸了。撑瞧。棵譬。
感覺這道題目的思想還是DFS，permutation 那一類題目预伺，只不過形式夸張了一些订咸。
就如同那道面試題，求質(zhì)數(shù)的次方和酬诀。脏嚷。。都是換個形式瞒御。
所以這種需要你求出多種變化父叙，多種結(jié)果，然后存在一個容器里面的肴裙，一般都是這個思路趾唱。
具體思路我也不想說了。我想我不會忘記蜻懦。
**
總結(jié)： permutation, dfs
**
Anyway, Good luck, Richardo!
My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ret = new ArrayList<List<String>>();
if (n <= 0) {
return ret;
}
helper(0, new boolean[n], new boolean[2 * n], new boolean[2 * n], new String[n], n, ret);
return ret;
}
private void helper(int row, boolean[] col, boolean[] l1, boolean[] l2, String[] board, int n, List<List<String>> ret) {
if (row >= n) {
List<String> group = new ArrayList<String>();
for (String s : board) {
group.add(s);
}
ret.add(group);
return;
}
for (int i = 0; i < n; i++) {
int index1 = row - i + n;
int index2 = 2 * n - i - row - 1;
if (!col[i] && !l1[index1] && !l2[index2]) {
col[i] = true;
l1[index1] = true;
l2[index2] = true;
char[] level = new char[n];
Arrays.fill(level, '.');
level[i] = 'Q';
board[row] = String.valueOf(level);
helper(row + 1, col, l1, l2, board, n, ret);
col[i] = false;
l1[index1] = false;
l2[index2] = false;
}
}
}
}
以前的做法甜癞，太復(fù)雜了，雖然思路沒怎么變宛乃。
網(wǎng)上看了答案悠咱，感覺是真的簡潔。
reference:
https://discuss.leetcode.com/topic/8592/comparably-concise-java-code
我一直在思考一個問題：
backtracking 的時候征炼，我給某個位置放個皇后析既，我得把用來記錄狀態(tài)的 isVisited[][] 相關(guān)區(qū)域全部設(shè)置成true
之后回到這一層，再把它恢復(fù)過來谆奥。但恢復(fù)過來是不可能的眼坏，因為你可能把別的皇后做成的true轉(zhuǎn)換成false
唯一的解決方法，就是每次dfs的時候酸些，都拷貝一份isVisited[][] 下去宰译，然后上來的時候就不用再恢復(fù)了。
但這個很花空間擂仍，花時間囤屹。
問題就在于熬甚，皇后占著一個位置逢渔，行列我都可以輕松地拿一維數(shù)組來mark，但是斜方向的兩條線乡括，我無法用數(shù)組來衡量肃廓。
其實是有的
仔細觀察智厌，對于斜率小于0的那條線。
i - j, 同一條線上的盲赊，永遠是定值铣鹏，不同線上的，值都不同哀蘑。
當(dāng)然诚卸， i - j 可能 < 0,所以， 為了可以用數(shù)組來表示绘迁，統(tǒng)一加上 n
于是合溺，數(shù)組中的index = i - j + n
斜率小于0的那條線
n - col - row - 1 是定值，為了讓他大于0
所以index = 2 * n - col - row - 1
這樣每次backtracking,下去的時候就把他們置成true,回來的時候缀台，很輕松地置成false棠赛。之后的問題就簡單了。就是簡單地一個backtracking
已經(jīng)見過好幾次利用一個數(shù)就能標(biāo)志一條線的例子了膛腐。
比如
Max point on a line
利用 (y2 - y1) / (x2 - x1) = (y3 - y1) / (x3 - x1)
和 最大公約數(shù)睛约，找出一條直線的代表數(shù)字
比如這道題目， n * n 里面哲身，表示一條對稱線的方法辩涝。
Anyway, Good luck, Richardo! -- 09/23/2016
