題目描述（困難難度）
和上一題一樣注盈，只不過這次不需要返回所有結(jié)果，只需要返回有多少個(gè)解就可以。
解法一
我們直接把上道題的 ans 的 size 返回就可以了睡互，此外 currentQueen.size ( ) == n 的時(shí)候肠套，也不用去生成一個(gè)解了舰涌，直接加一個(gè)數(shù)字占位。
public int totalNQueens(int n) {
List<Integer> ans = new ArrayList<>();
backtrack(new ArrayList<Integer>(), ans, n);
return ans.size();
}
private void backtrack(List<Integer> currentQueen, List<Integer> ans, int n) {
if (currentQueen.size() == n) {
ans.add(1);
return;
}
for (int col = 0; col < n; col++) {
if (!currentQueen.contains(col)) {
if (isDiagonalAttack(currentQueen, col)) {
continue;
}
currentQueen.add(col);
backtrack(currentQueen, ans, n);
currentQueen.remove(currentQueen.size() - 1);
}
}
}
private boolean isDiagonalAttack(List<Integer> currentQueen, int i) {
int current_row = currentQueen.size();
int current_col = i;
for (int row = 0; row < currentQueen.size(); row++) {
if (Math.abs(current_row - row) == Math.abs(current_col - currentQueen.get(row))) {
return true;
}
}
return false;
}
時(shí)間復(fù)雜度：
空間復(fù)雜度：
解法二
參考這里你稚。
既然不用返回所有解瓷耙，那么我們就不需要 currentQueen 來保存當(dāng)前已加入皇后的位置。只需要一個(gè) bool 型數(shù)組入宦，來標(biāo)記列是否被占有就可以了哺徊。
由于沒有了 currentQueen，所有不能再用之前 isDiagonalAttack 判斷對(duì)角線沖突的方法了乾闰。我們可以觀察下落追，對(duì)角線元素的情況。
可以發(fā)現(xiàn)對(duì)于同一條副對(duì)角線涯肩，row + col 的值是相等的轿钠。
對(duì)于同一條主對(duì)角線巢钓，row - col 的值是相等的。
我們同樣可以用一個(gè) bool 型數(shù)組疗垛，來保存當(dāng)前對(duì)角線是否有元素症汹，把它們相加相減的值作為下標(biāo)。
對(duì)于 row - col 贷腕，由于出現(xiàn)了負(fù)數(shù)背镇，所以可以加 1 個(gè) n，由 [ - 3, 3 ] 轉(zhuǎn)換為 [ 1 , 7 ] 泽裳。
public int totalNQueens(int n) {
List<Integer> ans = new ArrayList<>();
boolean[] cols = new boolean[n]; // 列
boolean[] d1 = new boolean[2 * n]; // 主對(duì)角線
boolean[] d2 = new boolean[2 * n]; // 副對(duì)角線
return backtrack(0, cols, d1, d2, n, 0);
}
private int backtrack(int row, boolean[] cols, boolean[] d1, boolean[] d2, int n, int count) {
if (row == n) {
count++;
} else {
for (int col = 0; col < n; col++) {
int id1 = row - col + n; //主對(duì)角線加 n
int id2 = row + col;
if (cols[col] || d1[id1] || d2[id2])
continue;
cols[col] = true;
d1[id1] = true;
d2[id2] = true;
count = backtrack(row + 1, cols, d1, d2, n, count);
cols[col] = false;
d1[id1] = false;
d2[id2] = false;
}
}
return count;
}
時(shí)間復(fù)雜度：
空間復(fù)雜度：
總
和上一題相比瞒斩，通過三個(gè) bool 型數(shù)組來標(biāo)記是否占有，不存儲(chǔ)具體的位置涮总，從而解決了這道題胸囱。
更多詳細(xì)通俗題解詳見 leetcode.wang 。
