力扣51.N皇后
原题，题目描述：
想必这道题都不用介绍，这本身就是一道非常出名的题目。题目只给出一个整数N，我们需要使用这个整数初始化一个N\times N的一个棋盘，然后在其中放置N个互相不会吃掉的皇后。皇后在题目描述里面有介绍，我们这里不多说。题目要求给出所有的放置办法。
思路
我们首先拿到题的思路肯定是回溯穷尽所有的情况，这个是当然的，所以我们也可以直接写出下面的代码：
代码一
class Solution {
ArrayList<List<String>> solveNQueensRes = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
int[] position = new int[n];
for (int i = 0; i < n; i++) {
position[0] = i;
ArrayList<String> r = new ArrayList<>();
String row = ".".repeat(i) + 'Q' + ".".repeat(n - i - 1);
r.add(row);
solveNQueens2(n, position, 1, r);
}
return solveNQueensRes;
}
public void solveNQueens2(int n, int[] position, int index, ArrayList<String> path) {
if (index >= n) {
solveNQueensRes.add(path);
return;
}
for (int i = 0; i < n; i++) {
ArrayList<String> r=new ArrayList<>(path);
boolean flag = true;
for (int j = 0; j < index; j++) {
int pos = position[j];
if (i == pos) {
flag = false;
break;
}
if (pos - (index-j) >= 0 && pos - (index-j) == i) {
flag = false;
break;
}
if (pos + (index-j) < n && pos + (index-j) == i) {
flag = false;
break;
}
}
if (!flag) {
continue;
}
String row = ".".repeat(i) + 'Q' + ".".repeat(n - i - 1);
r.add(row);
position[index] = i;
solveNQueens2(n, position, index + 1, r);
}
}
}
当然，这份代码还有很多可以优化的地方，我们慢慢来看。
- 首先path其实是可以省掉的，因为我们已经有一个position来记录放置的位置，如果使用path，反而会每一次要额外的创建对象。
- 然后是字符串的拼接。我们使用的直接是加法拼接。这里拼接的次数其实还是很多的，所以我们可以换成StringBuilder。
代码二
修改后如下：
class Solution {
ArrayList<List<String>> solveNQueensRes = new ArrayList<>();
int[] solveNQueensPosition;
public List<List<String>> solveNQueens(int n) {
solveNQueensPosition = new int[n];
for (int i = 0; i < n; i++) {
solveNQueensPosition[0] = i;
solveNQueens2(n, 1);
}
return solveNQueensRes;
}
public void solveNQueens2(int n, int index) {
if (index >= n) {
ArrayList<String> l = new ArrayList<>(n);
StringBuilder sb =new StringBuilder(n);
for (int i : solveNQueensPosition) {
for (int j = 0; j < i; j++) {
sb.append('.');
}
//sb.append(".".repeat(Math.max(0, i)));
sb.append('Q');
for (int j = 0; j < n - 1 - i; j++) {
sb.append('.');
}
//sb.append(".".repeat(Math.max(0, n - 1 - i)));
l.add(sb.toString());
sb.setLength(0);
}
solveNQueensRes.add(l);
return;
}
for (int i = 0; i < n; i++) {
boolean flag = true;
for (int j = 0; j < index; j++) {
int pos = solveNQueensPosition[j];
if (i == pos) {
flag = false;
break;
}
if (pos - (index - j) >= 0 && pos - (index - j) == i) {
flag = false;
break;
}
if (pos + (index - j) < n && pos + (index - j) == i) {
flag = false;
break;
}
}
if (flag) {
solveNQueensPosition[index] = i;
solveNQueens2(n, index + 1);
}
}
}
}
速度还算优秀，3ms，打败百分之60左右。代码的时间复杂度在O(N!)，空间复杂度O(N)。
优化到这里实在是优化不上去了。就去看了一下其他人的写法和管解。官方解答有一个非常天才的位运算解法。浅浅的理解了一下。然后再看了看其他人的，跟我差不多。不过我看到有人的皇后位置的记录方法有优化。我后面会尝试一下优化，其实我也有想过一样的方法，但是实现到一半感觉有点问题没有实现下去，结果是能实现的。