代码随想录算法训练营|day30

332.重新安排行程

(1)参考
创建map存储src，[]dest映射关系，并对[]dest排序
每次取map中第一个dest访问，将其作为新的src，每访问一条src->dest，删除该记录。
如果访问的src没有dest了，将当前节点加入结果集，并沿栈返回。
结果是沿栈返回的，故需要逆序输出

func findItinerary(tickets [][]string) []string {res := []string{}m := make(map[string][]string, 0)for _, ticket := range tickets {src, dest := ticket[0], ticket[1]m[src] = append(m[src], dest)}for k:= range m {sort.Strings(m[k])}var help func(srcTicket string)help = func(srcTicket string) {for {if v, ok := m[srcTicket]; !ok || len(v) == 0 {break}tmp := m[srcTicket][0]m[srcTicket] = m[srcTicket][1:]help(tmp)}res = append(res, srcTicket)}help("JFK")for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {res[i], res[j] = res[j], res[i]}return res
}

(2)回溯：超时了
排列问题。先对tickets排序，used记录当前车票是否被使用
若车票使用完并找到路径，返回，否则回溯查找路径

func findItinerary(tickets [][]string) []string {sort.Slice(tickets, func(i, j int) bool {return tickets[i][1] < tickets[j][1]})path := []string{"JFK"}used := make([]bool, len(tickets))var help func(srcTicket string, ticket [][]string) boolhelp = func(srcTicket string, ticket [][]string) bool {if len(path) == len(tickets)+1 {return true}for i, next := range tickets {if next[0] == path[len(path)-1] && !used[i] {path = append(path, next[1])used[i] = trueif help(next[1], tickets) {return true}path = path[:len(path)-1]used[i] = false}}return false}help("JFK", tickets)return path
}

51.N皇后

回溯
row控制递归深度，for循环控制列，进而确定当前位置
判断当前值是否有效：因为每行只选取一个位置，故只需判断列和正斜、反斜方向是否有皇后

func solveNQueens(n int) [][]string {res := [][]string{}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] = "."}}var help func(row int, board [][]string) boolhelp = func(row int, board [][]string) bool {if row == n {temp := make([]string, n)for i, rowStr := range board {temp[i] = strings.Join(rowStr, "")}res = append(res, temp)}for i := 0; i < n; i++ {if isValid(n, row, i, board) {board[row][i] = "Q"if help(row+1, board) {return true}board[row][i] = "."}}return false}help(0, board)return res
}func isValid(n, row, col int, board [][]string) bool {for i := 0; i < row; i++ {if board[i][col] == "Q" {return false}}for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {if board[i][j] == "Q" {return false}}for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {if board[i][j] == "Q" {return false}}return true
}

37.解数独

回溯
当前位置有效性判断：行、列、九宫格数字不重复
如果当前位置能放数字，且有效，递归，否则回溯

func solveSudoku(board [][]byte) {var help func(board [][]byte) boolhelp = func(board [][]byte) bool {for i := 0; i < 9; i++ {for j := 0; j < 9; j++ {if board[i][j] == '.' {for k := '1'; k <= '9'; k++ {if isValid(i, j, byte(k), board) {board[i][j] = byte(k)if help(board) {return true}board[i][j] = '.'}}return false}}}return true}help(board)
}func isValid(row, col int, val byte, board [][]byte) bool {for i := 0; i < 9; i++ {if board[row][i] == val {return false}}for i := 0; i < 9; i++ {if board[i][col] == val {return false}}startRow := (row / 3) * 3startCol := (col / 3) * 3for i := startRow; i < startRow+3; i++ {for j := startCol; j < startCol+3; j++ {if board[i][j] == val {return false}}}return true
}

代码随想录文章详解

332.重新安排行程
51.N皇后
37.解数独
回溯总结篇