友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
52. N-Queens II
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below. [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
解题分析
解题分析参考 51. N-Queens。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* Runtime: 1 ms, faster than 95.68% of Java online submissions for N-Queens II.
* Memory Usage: 36 MB, less than 8.70% of Java online submissions for N-Queens II.
*/
private int result = 0;
public int totalNQueens(int n) {
int[][] matrix = new int[n][n];
backtrack(matrix, 0, 0);
return result;
}
private void backtrack(int[][] matrix, int y, int step) {
if (step == matrix.length) {
result++;
return;
}
for (int xi = 0; xi < matrix[0].length; xi++) {
if (isValid(matrix, y, xi)) {
matrix[y][xi] = 1;
backtrack(matrix, y + 1, step + 1);
matrix[y][xi] = 0;
}
}
}
private boolean isValid(int[][] matrix, int y, int x) {
int len = matrix.length;
// 同列
for (int i = 0; i < y; i++) {
if (matrix[i][x] == 1) {
return false;
}
}
// 左上角
for (int i = 1; i < len && y - i >= 0 && x - i >= 0; i++) {
if (matrix[y - i][x - i] == 1) {
return false;
}
}
// 右上角：从右上角到最下角的对角线，他们 "行号 + 列号 = 常数"
int sum = x + y;
for (int yi = y - 1; yi >= 0 && 0 <= sum - yi && sum - yi < len; yi--) {
if (matrix[yi][sum - yi] == 1) {
return false;
}
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* 自己实现
*/
private int result = 0;
public int totalNQueens(int n) {
int[][] matrix = new int[n][n];
backtrack(matrix, 0, 0);
return result;
}
private void backtrack(int[][] matrix, int step, int count) {
int size = matrix.length;
int pow = size * size;
printMatrix(matrix);
if (step > pow) {
return;
} else if (size == count) {
result++;
} else {
for (int i = step; i < pow; i++) {
int row = i / size;
int col = i % size;
if (isValid(matrix, row, col)) {
matrix[row][col] = 1;
backtrack(matrix, (row + 1) * size, count + 1);
matrix[row][col] = 0;
}
}
}
}
private boolean isValid(int[][] matrix, int row, int col) {
int length = matrix.length;
for (int i = 0; i < length; i++) {
if (matrix[row][i] == 1) {
return false;
}
if (i < row && matrix[i][col] == 1) {
return false;
}
}
for (int i = 0; i < length; i++) {
// 左上角
if (0 <= row - i && 0 <= col - i && matrix[row - i][col - i] == 1) {
return false;
}
// 右上角
if (0 <= row - i && col + i < length && matrix[row - i][col + i] == 1) {
return false;
}
}
return true;
}