长沙公司名称大全_电商网络推广_百度学术论文查重免费检测_app用户量排名

前言

每天和你一起刷 LeetCode 每日一题~

今日看点：回溯问题必学经典

LeetCode 启动！

题目：N 皇后

代码与解题思路

先读题：同一行同一列，两条对角线上只能同时存在一个皇后，题目要我们找出组成这样棋盘的所有可能性

假设我们遍历每一行每一列，每一行和每一列只放一个皇后，这样我们只需要判断对角线上有没有皇后存在即可，通过回溯遍历所有情况，将合法的情况记录并存入 ans 即可

核心问题：怎么判断对角线上是否存在其他的皇后？

1、对角线：左上到右下， 11， 22，33，行列相减的值是相同的，我们通过 d1 数组记录行列相减的值，这样就能判断当前位置对角线上是否存在皇后了

（注意：如果是 12， 23， 34，这种情况，行列相减是负数，我们可以通过让相减 + n 的做法规避出现负数的情况。）

2、对角线：右上到左下，13， 22， 31，行列相加的值是相同的，我们通过 d2 数组记录行列相加的值，这样就能判断当前位置对角线上是否存在皇后了

代码如下：

func solveNQueens(n int) (ans [][]string) {// 经典回溯 N 皇后问题col, st := make([]int, n), make([]bool, n)d1, d2 := make([]bool, n*2), make([]bool, n*2) // 用来放对角线对应的位置var dfs func(int)dfs = func(r int) { // 枚举行if r == n { // 皇后已经放置完成，将这种情况的棋盘构造并加入 ans 数组board := make([]string, n)for i, c := range col {board[i] = strings.Repeat(".", c)+"Q"+strings.Repeat(".", n-c-1)}ans = append(ans, board)}for c, v := range st { // 枚举列rc1, rc2 := r-c+n, r+cif !v && !d1[rc1] && !d2[rc2] { // 当前位置 && 俩对角线上没有放皇后col[r] = c // 在 r 行 c 列上放置皇后st[c], d1[rc1], d2[rc2] = true, true, truedfs(r + 1)st[c], d1[rc1], d2[rc2] = false, false, false // 恢复现场}}}dfs(0)return ans
}

每天进步一点点，我们明天不见不散~

可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。