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
}