1.重新安排行程
1.1 我的代码，超时通不过
var (
used []bool
path []string
res []string
isFind bool
)
func findItinerary(tickets [][]string) []string {
sortTickets(tickets)
res = make([]string, len(tickets)+1)
path = make([]string, 0)
used = make([]bool, len(tickets))
isFind = false
start := "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 = true
return
}
for i := 0; i < len(tickets); i++ {
// 当前机票未使用，且起点为start
if !used[i] && tickets[i][0] == start {
used[i] = true
path = 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 string
visited bool
}
// 储存pair数组，实现sort接口
type pairs []*pair
func (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() bool
backtrack = 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 = true
if backtrack() {
return true
}
res = res[:len(res)-1]
t.visited = false
}
}
return false
}
// 所有机票从JFK出发
res = append(res, "JFK")
backtrack()
return
}
2.N皇后
var (
res [][]string
path [][]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] = 1
dfs(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, col
for row1 >= 0 && col1 >= 0 {
if path[row1][col1] == 1 {
return false
}
row1--
col1--
}
row1, col1 = row, col
for row1 < n && col1 < n {
if path[row1][col1] == 1 {
return false
}
row1++
col1++
}
// 检查副对角线
row1, col1 = row, col
for row1 >= 0 && col1 < n {
if path[row1][col1] == 1 {
return false
}
row1--
col1++
}
row1, col1 = row, col
for row1 < n && col1 >= 0 {
if path[row1][col1] == 1 {
return false
}
row1++
col1--
}
return true
}
3.解数独
var (
chunks [9][]bool
rows [9][]bool
cols [9][]bool
matrixSize int = 9
emptyCount int = 0
hasFind bool = false
)
func solveSudoku(board [][]byte) {
emptyCount = 0
hasFind = false
for 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] = true
rows[i][num] = true
cols[j][num] = true
} else {
emptyCount++
}
}
}
dfs(emptyCount, board, &hasFind)
}
func dfs(emptyCount int, board [][]byte, hasFind *bool) {
if *hasFind { //在其他分支已经找到答案了
return
}
if emptyCount == 0 { //空格全部填完，找到答案
*hasFind = true
return
}
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' + num
chunks[chunkId][num] = true
rows[i][num] = true
cols[j][num] = true
emptyCount--
dfs(emptyCount, board, hasFind)
if *hasFind { //在其他分支已经找到答案了
return
}
chunks[chunkId][num] = false
rows[i][num] = false
cols[j][num] = false
board[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
}
