1.重新安排行程

1.1 我的代码，超时通不过

var (used   []boolpath   []stringres    []stringisFind bool
)func findItinerary(tickets [][]string) []string {sortTickets(tickets)res = make([]string, len(tickets)+1)path = make([]string, 0)used = make([]bool, len(tickets))isFind = falsestart := "JFK"path = append(path, start)dfs(start, 0, tickets)return res
}func dfs(start string, num int, tickets [][]string) {if isFind {return}if num == len(tickets) {copy(res, path)isFind = truereturn}for i := 0; i < len(tickets); i++ {// 当前机票未使用，且起点为startif !used[i] && tickets[i][0] == start {used[i] = truepath = append(path, tickets[i][1])dfs(tickets[i][1], num+1, tickets)if isFind {return}path = path[:len(path)-1]used[i] = false}}
}func sortTickets(tickets [][]string) {sort.Slice(tickets, func(i, j int) bool {if tickets[i][0] == tickets[j][0] {return tickets[i][1] < tickets[j][1]}return tickets[i][0] < tickets[j][0]})
}

1.2 正确的解法

首先先把图的邻接表存进字典，并且按字典序排序，然后从‘JFK’开始深搜，每前进一层就减去一条路径，直到某个起点不存在路径的时候就会跳出while循环进行回溯，相对先找不到路径的一定是放在相对后面，所以当前搜索的起点from会插在当前输出路径的第一个位置。

// No.332 重新安排行程
type pair struct {// pair储存机票目的地和当前航线是否已经使用target  stringvisited bool
}// 储存pair数组，实现sort接口
type pairs []*pairfunc (p pairs) Len() int {return len(p)
}func (p pairs) Swap(i, j int) {p[i], p[j] = p[j], p[i]
}func (p pairs) Less(i, j int) bool {return p[i].target < p[j].target
}func findItinerary(tickets [][]string) (res []string) {// record储存每个机场可到达的目的地，以及当前航线是否已选择targets := make(map[string]pairs, 0)for _, ticket := range tickets {if targets[ticket[0]] == nil {targets[ticket[0]] = make(pairs, 0)}// 添加新的可达目的地，初始置为未选择targets[ticket[0]] = append(targets[ticket[0]], &pair{target: ticket[1], visited: false})}for k := range targets {// 按字典升序排序目的地，保证第一个选出的就是字典序最小的结果sort.Sort(targets[k])}var backtrack func() boolbacktrack = func() bool {if len(tickets)+1 == len(res) {// 结果机场数量比票数大1说明已经构建出所有路径，找到了结果return true}// 当前所在机场here := res[len(res)-1]for i, t := range targets[here] {if i > 0 && targets[here][i-1].target == t.target && !targets[here][i-1].visited {// 剪枝（非常重要），如果上一个目的地和当前的相同，且上一个没用过，说明是从上一个回溯回来的// 上一个不可能那么当前的也不可能，直接跳过continue}// 枚举所有可能的目的地，已经使用过的航线除外if !t.visited {res = append(res, t.target)t.visited = trueif backtrack() {return true}res = res[:len(res)-1]t.visited = false}}return false}// 所有机票从JFK出发res = append(res, "JFK")backtrack()return
}

2.N皇后

var (res  [][]stringpath [][]int
)func solveNQueens(n int) [][]string {res = make([][]string, 0)path = make([][]int, n)for i := 0; i < n; i++ {path[i] = make([]int, n)}dfs(n, 0)return res
}func dfs(n int, curRow int) {if curRow == n {temp := make([]string, 0)for i := 0; i < n; i++ {str := ""for j := 0; j < n; j++ {if path[i][j] == 0 {str = str + "."} else {str = str + "Q"}}temp = append(temp, str)}res = append(res, temp)}for i := 0; i < n; i++ {if canPlaceQueen(curRow, i, n) {path[curRow][i] = 1dfs(n, curRow+1)path[curRow][i] = 0}}
}func canPlaceQueen(row, col, n int) bool {if row >= n || col >= n || row < 0 || col < 0 {return false}// 检查同行同列的情况for i := 0; i < n; i++ {if path[i][col] == 1 {return false}if path[row][i] == 1 {return false}}// 检查主对角线row1, col1 := row, colfor row1 >= 0 && col1 >= 0 {if path[row1][col1] == 1 {return false}row1--col1--}row1, col1 = row, colfor row1 < n && col1 < n {if path[row1][col1] == 1 {return false}row1++col1++}// 检查副对角线row1, col1 = row, colfor row1 >= 0 && col1 < n {if path[row1][col1] == 1 {return false}row1--col1++}row1, col1 = row, colfor row1 < n && col1 >= 0 {if path[row1][col1] == 1 {return false}row1++col1--}return true
}

3.解数独

var (chunks     [9][]boolrows       [9][]boolcols       [9][]boolmatrixSize int  = 9emptyCount int  = 0hasFind    bool = false
)func solveSudoku(board [][]byte) {emptyCount = 0hasFind = falsefor i := 0; i < matrixSize; i++ {chunks[i] = make([]bool, 10) //用来表示每个区域中的数字1-9是否已经被使用rows[i] = make([]bool, 10)   //用来表示每行中的数字1-9是否已经被使用cols[i] = make([]bool, 10)   //用来表示每列中的数字1-9是否已经被使用}for i := 0; i < matrixSize; i++ {for j := 0; j < matrixSize; j++ {if board[i][j] != '.' {num := board[i][j] - '0'chunkId := findChunkIndex(i, j)chunks[chunkId][num] = truerows[i][num] = truecols[j][num] = true} else {emptyCount++}}}dfs(emptyCount, board, &hasFind)
}func dfs(emptyCount int, board [][]byte, hasFind *bool) {if *hasFind { //在其他分支已经找到答案了return}if emptyCount == 0 { //空格全部填完，找到答案*hasFind = truereturn}for i := 0; i < matrixSize; i++ {for j := 0; j < matrixSize; j++ {if board[i][j] == '.' {for num := byte(1); num <= 9; num++ {if canPlaceNumber(i, j, num) {chunkId := findChunkIndex(i, j)board[i][j] = '0' + numchunks[chunkId][num] = truerows[i][num] = truecols[j][num] = trueemptyCount--dfs(emptyCount, board, hasFind)if *hasFind { //在其他分支已经找到答案了return}chunks[chunkId][num] = falserows[i][num] = falsecols[j][num] = falseboard[i][j] = '.'emptyCount++}}return}}}
}
//查看在该位置是否能放下该数
func canPlaceNumber(row, col int, num byte) bool {//行列中是否已经有这个数if rows[row][num] || cols[col][num] {return false}//3*3的块中是否有这个数if chunks[findChunkIndex(row, col)][num] {return false}return true
}
//找到所属的3*3的块
func findChunkIndex(row, col int) int {return (row/3)*3 + col/3
}