题目：332. 重新安排行程
思路：
其实这里已经是图的部分了，回溯应该也可以。Hierholzer算法解决欧拉问题
代码：
func findItinerary(tickets [][]string) []string {
var (
m = map[string][]string{}
res []string
)
for _, ticket := range tickets {
src, dst := ticket[0], ticket[1]
m[src] = append(m[src], dst)
}
for key := range m {
sort.Strings(m[key])
}
var dfs func(curr string)
dfs = func(curr string) {
for {
if v, ok := m[curr]; !ok || len(v) == 0 {
break
}
tmp := m[curr][0]
m[curr] = m[curr][1:]
dfs(tmp)
}
res = append(res, curr)
}
dfs("JFK")
for i := 0; i < len(res)/2; i++ {
res[i], res[len(res) - 1 - i] = res[len(res) - 1 - i], res[i]
}
return res
}
参考：
题目：51. N 皇后
思路：
哈哈哈，先这样吧
代码：
var solutions [][]string
func solveNQueens(n int) [][]string {
solutions = [][]string{}
queens := make([]int, n)
for i := 0; i < n; i++ {
queens[i] = -1
}
columns := map[int]bool{}
diagonals1, diagonals2 := map[int]bool{}, map[int]bool{}
backtrack(queens, n, 0, columns, diagonals1, diagonals2)
return solutions
}
func backtrack(queens []int, n, row int, columns, diagonals1, diagonals2 map[int]bool) {
if row == n {
board := generateBoard(queens, n)
solutions = append(solutions, board)
return
}
for i := 0; i < n; i++ {
if columns[i] {
continue
}
diagonal1 := row - i
if diagonals1[diagonal1] {
continue
}
diagonal2 := row + i
if diagonals2[diagonal2] {
continue
}
queens[row] = i
columns[i] = true
diagonals1[diagonal1], diagonals2[diagonal2] = true, true
backtrack(queens, n, row + 1, columns, diagonals1, diagonals2)
queens[row] = -1
delete(columns, i)
delete(diagonals1, diagonal1)
delete(diagonals2, diagonal2)
}
}
func generateBoard(queens []int, n int) []string {
board := []string{}
for i := 0; i < n; i++ {
row := make([]byte, n)
for j := 0; j < n; j++ {
row[j] = '.'
}
row[queens[i]] = 'Q'
board = append(board, string(row))
}
return board
}
参考：
题目：37. 解数独
思路：
哈哈哈，先这样吧
代码：
func solveSudoku(board [][]byte) {
var backtracking func(board [][]byte) bool
backtracking = func(board [][]byte) bool {
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
//判断此位置是否适合填数字
if board[i][j] != '.' {
continue
}
//尝试填1-9
for k := '1'; k <= '9'; k++ {
if isvalid(i, j, byte(k), board) == true { //如果满足要求就填
board[i][j] = byte(k)
if backtracking(board) == true {
return true
}
board[i][j] = '.'
}
}
return false
}
}
return true
}
backtracking(board)
}
//判断填入数字是否满足要求
func isvalid(row, col int, k byte, board [][]byte) bool {
for i := 0; i < 9; i++ { //行
if board[row][i] == k {
return false
}
}
for i := 0; i < 9; i++ { //列
if board[i][col] == k {
return false
}
}
//方格
startrow := (row / 3) * 3
startcol := (col / 3) * 3
for i := startrow; i < startrow+3; i++ {
for j := startcol; j < startcol+3; j++ {
if board[i][j] == k {
return false
}
}
}
return true
}