上海网站建设seo,抖音短剧推广怎么做,怎么建设小型网站,彩票网站开发需要多少钱【代码随想录】算法训练计划30
1、51. N 皇后
按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。
给你一个整数 n #xff0c;…【代码随想录】算法训练计划30
1、51. N 皇后
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
我写的
我先想了一个思路然后去看代码回想录和我想的一样我取巧了直接看了她的写的不过都理解 但也有一点别的收获 他把res设为了全局变量这样就连和*都不需要了
收获 全局的声明var res [][]string 函数内初始化res [][]string{} 这样就不需要取值操作了——就是* 这些个 func solveNQueens(n int) [][]string {res : make([][]string, 0)board : make([][]string, n)//下边就是把数组空的位置都初始化为.代表空for i : 0; i n; i {board[i] make([]string, n)}for i : 0; i n; i{for j : 0; j n; j {board[i][j] .}}backtrack(board, 0, res)return res
}
func backtrack(board [][]string, row int, res *[][]string) {size : len(board)//结束条件是到board就是到最后一行也添加皇后了if row size {ans : make([]string, size)for i : 0; i size; i {ans[i] strings.Join(board[i], )}*res append(*res, ans)return}for col : 0; col size; col {if !isValid(board, row, col){continue}board[row][col] Qbacktrack(board, row1, res)board[row][col] .}
}
func isValid(board [][]string, row,col int) (res bool){n : len(board)//判断这一列上下行是否有Qfor i : 0; i row; i {if board[i][col] Q {return false}}//判断这一行左右列是否有Qfor i : 0; i col; i {if board[row][i] Q {return false}}//为什么不判断左下线和右下线的原因很简单因为下边的行还没有给皇后所以不需要判断//判断左上线是否有Qfor i, j : row, col; i 0 j 0; i, j i-1, j-1 {if board[i][j] Q {return false}}//判断右上线是否有Qfor i, j : row, col; i 0 j n; i,j i-1,j1 {if board[i][j] Q {return false}}return true
}2、37. 解数独
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图 数独部分空格内已填入了数字空白格用 ‘.’ 表示。
提示
board.length 9 board[i].length 9 board[i][j] 是一位数字或者 ‘.’ 题目数据 保证 输入数独仅有一个解 我第一次只能写到如下这么多了
//做一个二维的字典或者数组方便第三个判断0-02,1-35,2-68或者0-131-462-79
jgg : [3][2]{{0,2},{3,5},{6,8},
}
func solveSudoku(board [][]byte) {list : make([]int, 0)backtrack(list []int, board)return board
}
func backtrack(board *[][]byte) {//到第九行结束一行一行的填入,每一行要填入9个数字//记住这个数独只有唯一一个解if Index 9 {ans : make([]int, len(list))copy(ans, list)*board}for i : 0; i 9; i {//我的难点就是不知道怎么去知道这个行列然后去嗯...给他整上数字}
}//判断所填入数字是否满足条件
func mz(board *[][]byte, shu,row,col int) bool{//左右这个数没出现过,i不变j变,情况下可以添加这个数字for j : 0; j 9 ; j {if board[row][j] shu {return false}}//上下这个数没出现过, i变j不变for i : 0; i 9; i {if board[i][col] shu {return false}}//判断他所在区域的9个格子是否出现-除以三-判断是第几个格子h : row/3l : col/3for i : jgg[h][0]; i jgg[h][1] {for j : jgg[l][0]; j jgg[l][1]{if board[i][j] shu {return false}}}return true
}看题解理解后如下啊
思路
第一步咱们很清楚的知道需要判断加入的数是否满足条件所以写了mz函数感觉我判断格子的方法有点臃肿了好开始正题进入backtrack为什么这次没有和solveSudoku分开单独写一个呢在于这个题目人家不要返回值而且填写的是board二维的咱要是在分开的backtrack函数用*[][]int,其实传不进去单个值所以直接在solveSudoku函数先声明再初始化再使用 4.好了开始说说初始化也就是backtrack的主体首先是这个双重for循环记得水仙花数打印图形吗这类的题目就是用了双重for循环来代表要添加的元素所在的行列接着判断不是’.的不需要变成数字跳过当前循环进入下一层重重点开始首先是’1’-9’是选择列表但是因为board是[][]byte类型在你追加的时候需要类型转换byte(shu),判断是否满足mz的传参也需要接着是循环不过这里用了if多了一层判断为真就return true接着回溯都知道接着下边又有两个return说实话我还不太理解这三个return到底有什么妙用关于方格的判断条件啊还是人家代码随想录写得好值得看看不过别担心不难理解
func solveSudoku(board [][]byte) {var backtrack func(board [][]byte) boolbacktrack func(board [][]byte) bool {//双重for循环代表行列for i : 0; i 9; i {for j : 0; j 9; j {//只有当前位置为.的时候才可以添加数字否则跳过这个数if board[i][j] ! .{continue}//重点填写1-9是选择列表for shu : 1; shu 9; shu {if mz(board,byte(shu),i,j) true {//追加board[i][j] byte(shu)//循环if backtrack(board) true {return true}//回溯board[i][j] .}}return false}}return true}backtrack(board)
}
func backtrack(board *[][]byte) {}//判断所填入数字是否满足条件
func mz(board [][]byte, shu byte, row,col int) bool {//做一个二维的字典或者数组方便第三个判断0-02,1-35,2-68或者0-131-462-79jgg : [3][2]int{{0,2},{3,5},{6,8},}//左右这个数没出现过,i不变j变,情况下可以添加这个数字for j : 0; j 9 ; j {if board[row][j] shu {return false}}//上下这个数没出现过, i变j不变for i : 0; i 9; i {if board[i][col] shu {return false}}//判断他所在区域的9个格子是否出现-除以三-判断是第几个格子h : row/3l : col/3for i : jgg[h][0]; i jgg[h][1]; i {for j : jgg[l][0]; j jgg[l][1]; j{if board[i][j] shu {return false}}}return true
}
