leetcode常规算法题复盘（第五期）——八皇后
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode常规算法题复盘（第五期）——八皇后，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含11684字，纯文字阅读大概需要17分钟。
内容图文
题目原文
面试题 08.12. 八皇后
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。注意：本题相对原题做了扩展
示例:
输入：4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
尝试解答
八皇后老生常谈的问题了，提到回溯思想首先想到的经典例题就是八皇后，不过我的代码好像没太把回溯的味道做出来（虽然确实是回溯算法），先上自己的代码：
1 class Solution: 2 def solveNQueens(self, n: int): 3 listQ = [["." for _ in range(n)]for _ in range(n)] 4 res = [] 5 return self.place(0,listQ,res) 6 7 8 def place(self,rol,listQ,res): 9 if rol==0: 10 for i in range(len(listQ)): 11 listQ[rol][i]="Q" 12 #print(listQ) 13 self.place(rol+1,listQ,res) 14 listQ[rol][i]="." 15 return res 16 17 18 19 if rol == len(listQ): 20 res.append([''.join(listQ[i]) for i in range(len(listQ))]) 21 print(res) 22 listQ = [["." for _ in range(len(listQ))]for _ in range(len(listQ))] 23 24 25 else: 26 for i in range(len(listQ)): 27 if self.check(rol,i,listQ): 28 listQ[rol][i] = "Q" 29 #print(listQ) 30 self.place(rol+1,listQ,res) 31 listQ[rol][i]="." 32 33 34 35 36 37 def check(self,y,x,listQ): 38 for j in range(len(listQ)): 39 for i in range(len(listQ)): 40 if listQ[j][i]=="Q": 41 if j==y or i==x or abs(j-y)==abs(i-x): 42 return False 43 return True 44 45 46 47 48 49 50 if __name__ == "__main__": 51 solu = Solution() 52 print(solu.solveNQueens(4))
就是最简单的暴力尝试的算法，优化的方法暂时还没想到，还是借鉴一下大佬的思想吧。
标准题解
思路一：递归算法
先上代码：
1 public List<List<String>> solveNQueens(int n) {
2 char[][] chess = new char[n][n];
3 //初始化数组
4 for (int i = 0; i < n; i++)
5 for (int j = 0; j < n; j++)
6 chess[i][j] = '.';
7 List<List<String>> res = new ArrayList<>();
8 solve(res, chess, 0);
9 return res;
10 }
11
12 private void solve(List<List<String>> res, char[][] chess, int row) {
13 //终止条件，最后一行都走完了，说明找到了一组，把它加入到集合res中
14 if (row == chess.length) {
15 res.add(construct(chess));
16 return;
17 }
18 //遍历每一行
19 for (int col = 0; col < chess.length; col++) {
20 //判断这个位置是否可以放皇后
21 if (valid(chess, row, col)) {
22 //数组复制一份
23 char[][] temp = copy(chess);
24 //在当前位置放个皇后
25 temp[row][col] = 'Q';
26 //递归到下一行继续
27 solve(res, temp, row + 1);
28 }
29 }
30 }
31
32 //把二维数组chess中的数据测下copy一份
33 private char[][] copy(char[][] chess) {
34 char[][] temp = new char[chess.length][chess[0].length];
35 for (int i = 0; i < chess.length; i++) {
36 for (int j = 0; j < chess[0].length; j++) {
37 temp[i][j] = chess[i][j];
38 }
39 }
40 return temp;
41 }
42
43 //row表示第几行，col表示第几列
44 private boolean valid(char[][] chess, int row, int col) {
45 //判断当前列有没有皇后,因为他是一行一行往下走的，
46 //我们只需要检查走过的行数即可，通俗一点就是判断当前
47 //坐标位置的上面有没有皇后
48 for (int i = 0; i < row; i++) {
49 if (chess[i][col] == 'Q') {
50 return false;
51 }
52 }
53 //判断当前坐标的右上角有没有皇后
54 for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
55 if (chess[i][j] == 'Q') {
56 return false;
57 }
58 }
59 //判断当前坐标的左上角有没有皇后
60 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
61 if (chess[i][j] == 'Q') {
62 return false;
63 }
64 }
65 return true;
66 }
67
68 //把数组转为list
69 private List<String> construct(char[][] chess) {
70 List<String> path = new ArrayList<>();
71 for (int i = 0; i < chess.length; i++) {
72 path.add(new String(chess[i]));
73 }
74 return path;
75 }
76
77 //作者：sdwwld
78 //链接：https://leetcode-cn.com/problems/eight-queens-lcci/solution/nhuang-hou-jing-dian-hui-su-suan-fa-tu-wen-xiang-2/
79 //来源：力扣（LeetCode）
80 //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码的注释非常清楚，因此就不再做更多解释了，代码很长，并且在不断复制数据，复制一次就需要一个二维遍历，所以代码性能必然会很差，不过这也确实是一个可以AC的方法。
思路二：回溯算法
先上代码：
1 public List<List<String>> solveNQueens(int n) {
2 char[][] chess = new char[n][n];
3 for (int i = 0; i < n; i++)
4 for (int j = 0; j < n; j++)
5 chess[i][j] = '.';
6 List<List<String>> res = new ArrayList<>();
7 solve(res, chess, 0);
8 return res;
9 }
10
11 private void solve(List<List<String>> res, char[][] chess, int row) {
12 if (row == chess.length) {
13 res.add(construct(chess));
14 return;
15 }
16 for (int col = 0; col < chess.length; col++) {
17 if (valid(chess, row, col)) {
18 chess[row][col] = 'Q';
19 solve(res, chess, row + 1);
20 chess[row][col] = '.';
21 }
22 }
23 }
24
25 //row表示第几行，col表示第几列
26 private boolean valid(char[][] chess, int row, int col) {
27 //判断当前列有没有皇后,因为他是一行一行往下走的，
28 //我们只需要检查走过的行数即可，通俗一点就是判断当前
29 //坐标位置的上面有没有皇后
30 for (int i = 0; i < row; i++) {
31 if (chess[i][col] == 'Q') {
32 return false;
33 }
34 }
35 //判断当前坐标的右上角有没有皇后
36 for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
37 if (chess[i][j] == 'Q') {
38 return false;
39 }
40 }
41 //判断当前坐标的左上角有没有皇后
42 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
43 if (chess[i][j] == 'Q') {
44 return false;
45 }
46 }
47 return true;
48 }
49
50 //把数组转为list
51 private List<String> construct(char[][] chess) {
52 List<String> path = new ArrayList<>();
53 for (int i = 0; i < chess.length; i++) {
54 path.add(new String(chess[i]));
55 }
56 return path;
57 }
58
59 //作者：sdwwld
60 //链接：https://leetcode-cn.com/problems/eight-queens-lcci/solution/nhuang-hou-jing-dian-hui-su-suan-fa-tu-wen-xiang-2/
61 //来源：力扣（LeetCode）
62 //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码结构与我自己写的几乎一摸一样可是我们之间的运行差距真的很大（抓狂，我的都垫底了）
这是大佬的运行结果：
这是我的运行结果：
上面代码中每次遇到能放皇后的时候，我们都会把原数组复制一份，这样对新数据的修改就不会影响到原来的，也就是不会造成分支污染。但这样每次尝试的时候都都把原数组复制一份，影响效率，有没有其他的方法不复制呢，是有的。就是每次我们选择把这个位置放置皇后的时候，如果最终不能成功，那么返回的时候我们就还要把这个位置还原。这就是回溯算法，也是试探算法。我们来看下代码
1 private void solve(List<List<String>> res, char[][] chess, int row) {
2 if (row == chess.length) {
3 res.add(construct(chess));
4 return;
5 }
6 for (int col = 0; col < chess.length; col++) {
7 if (valid(chess, row, col)) {
8 chess[row][col] = 'Q';
9 solve(res, chess, row + 1);
10 chess[row][col] = '.';
11 }
12 }
13 }
主要来看下8-10行，其他的都没变，还和上面的一样。这和之前讲的391，回溯算法求组合问题很类似。他是先假设[row][col]这个位置可以放皇后，然后往下找，无论找到找不到最后都会回到这个地方，因为这里是递归调用，回到这个地方的时候再把它复原，然后走下一个分支。
不过鉴于我用相同的思路跑出了这么差的成绩，于是我决定尝试一下新的思路。
于是我找到了一个运行几乎双百的java代码：
1 class Solution {
2 public List<List<String>> solveNQueens(int n) {
3 List<List<String>> ans = new ArrayList<>();
4 char[][] nums = new char[n][n];
5 for (int i = 0; i < n; i++) {
6 Arrays.fill(nums[i], '.');
7 }
8 backtrack(nums,0, ans);
9 return ans;
10 }
11
12 private void backtrack(char[][] nums, int currRow, List<List<String>> ans) {
13 int len = nums.length;
14 if (len == currRow) {
15 List<String> path2 = new ArrayList<>();
16 for (int i = 0; i < len; i++) {
17 path2.add(String.valueOf(nums[i]));
18 }
19 ans.add(path2);
20 return;
21 }
22
23 for (int col = 0; col < len; col++) {
24 //判断这个位置是否合适
25 boolean isok = true;
26 for (int row = 0; row < currRow; row++) {
27 //竖的有Q
28 if (nums[row][col] == 'Q') {
29 isok = false;
30 break;
31 }
32 //判断对角线
33 if (col + (currRow - row) < len && nums[row][col + (currRow - row)] == 'Q') {
34 isok = false;
35 break;
36 }
37 if (col - (currRow - row) >= 0 && nums[row][col - (currRow - row)] == 'Q') {
38 isok = false;
39 break;
40 }
41 }
42 if (!isok) {
43 continue;
44 }
45 //满足条件
46 nums[currRow][col] = 'Q';
47 backtrack(nums, currRow + 1, ans);
48 nums[currRow][col] = '.';
49 }
50 }
51 }
52
53 //作者：ckhero
54 //链接：https://leetcode-cn.com/problems/eight-queens-lcci/solution/jie-jin-shuang-bai-by-ckhero/
55 //来源：力扣（LeetCode）
56 //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这个几乎双百的java代码并没有更新奇的思路，他只是将check函数写进了主体处理函数中，这样省去了函数中调用其他函数的开销，提高了一些处理速度，但我个人认为这样也不是很可取，这回降低代码的可读性（读起来缺少了一些模块化的感觉，本质上对理解代码本身影响不大。）
思路差距
八皇后实在太经典了，它的解题思路已经相当家喻户晓了，所以思路这里也没什么差距，就是代码实现不同人会有不同的写法。另外，复制数据结构的操作也不是完全不可取，或许有些问题非这种办法不可，至少我在这个问题上没有先想到这个方法，先记下来。
技术差距
从这期开始，技术差距将会专门讨论一些如何提高代码性能的问题，我们的目标不能仅仅停留在全AC上，缩短运行时间也是应该考虑的一个重要目标。
1、用一个数据结构将递归运算中的运行结果存储起来可以起到节省运算资源的效果，有时候甚至必须要这么做，因为这样可以实现回溯的作用。而单纯的进行存储效率会不如在原数据上进行改写的效果好。
2、函数中调用函数会降低代码的性能，但有时候我们不得不这么做，像某些递归运算，不得不在函数中调用函数。
内容总结
以上是互联网集市为您收集整理的leetcode常规算法题复盘（第五期）——八皇后全部内容，希望文章能够帮你解决leetcode常规算法题复盘（第五期）——八皇后所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。