問(wèn)題1：?jiǎn)卧~搜索 //
樹(shù)問(wèn)題，樹(shù)結(jié)構(gòu)如下
思路如上圖：
1）遍歷整個(gè)二維網(wǎng)格，對(duì)二維網(wǎng)格每個(gè)元素e疆导，嘗試以該元素e開(kāi)頭能否找到相關(guān)單詞
2）二維數(shù)組上的移動(dòng)借組1個(gè)二維數(shù)組來(lái)完成葛躏，x軸為首個(gè)元素，y軸為第二個(gè)元素败富，如下：
move := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}兽叮，上右下左鹦聪，順時(shí)針移動(dòng)椎麦，
這道題中移動(dòng)順序無(wú)關(guān)緊要观挎，不過(guò)有些題目中移動(dòng)順序不同會(huì)影響性能
如 x=x+move[0][0]，y=y+move[0][1]嘁捷，為向上移動(dòng)
具體實(shí)現(xiàn)：
func exist(board [][]byte, word string) bool {
m := len(board) // 行數(shù)
if m == 0 {
return false
}
n := len(board[0]) // 列數(shù)
move := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}} // 上右下左,順時(shí)針移動(dòng)
// 創(chuàng)建m行n列的visited二維數(shù)組,輔助判斷元素是否已經(jīng)被訪問(wèn)過(guò)
visited := newVisited(m, n)
for x := 0; x < m; x++ {
for y := 0; y < n; y++ {
if searchWord(board, word, 0, x, y, m, n, move, visited) {
return true
}
}
}
return false
}
// index: word的第幾位元素
// 函數(shù)功能: 從board[x][y]開(kāi)始,尋找word[index...len(word)-1]元素
func searchWord(board [][]byte, word string,
index, x, y, m, n int, move [][]int, visited [][]bool) bool {
//遞歸終止條件
if index == len(word)-1 {
// 最后元素,返回 board[x][y]==word[index]的結(jié)果
return board[x][y] == word[index]
} else {
// 遞歸過(guò)程
if board[x][y] == word[index] {
visited[x][y] = true
// 順時(shí)針移動(dòng)
for i := 0; i < 4; i++ {
newX := x + move[i][0]
newY := y + move[i][1]
// (1)x,y不越界;(2)board[x][y]沒(méi)被訪問(wèn)過(guò);(3)能找到匹配;
// 前2者同時(shí)符合進(jìn)行下一層搜索,3者同時(shí)滿足返回true
if !notArea(newX, newY, m, n) && !visited[newX][newY] &&
searchWord(board, word, index+1, newX, newY,
m, n, move, visited) {
return true
}
}
// 4個(gè)方向都找不到,該點(diǎn)重新置為false
visited[x][y] = false
}
}
return false
}
// 判斷是否越界: 越界返回true
func notArea(x, y, m, n int) bool {
return x < 0 || y < 0 || x >= m || y >= n
}
// 創(chuàng)建m行n列的visited二維數(shù)組
func newVisited(m, n int) [][]bool {
visited := make([][]bool, m)
for i := 0; i < m; i++ {
visited[i] = make([]bool, n)
}
return visited
}
提交leetcode，通過(guò)
問(wèn)題2：島嶼數(shù)量 //
結(jié)構(gòu)如下圖鼓鲁，藍(lán)色代表海洋
解決思路和問(wèn)題1類似，不同的是這里是對(duì)陸地進(jìn)行填充燥狰，并返回陸地?cái)?shù)量
func numIslands(grid [][]byte) int {
m := len(grid) // 行數(shù)
if m == 0 {
return 0
}
n := len(grid[0]) // 列數(shù)
move := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}} //順時(shí)針移動(dòng)
// 創(chuàng)建m行n列的visited二維數(shù)組,輔助判斷元素是否已經(jīng)被訪問(wèn)過(guò)
visited := newVisited(m, n)
count := 0 // 陸地?cái)?shù)量
for x := 0; x < m; x++ {
for y := 0; y < n; y++ {
// 本地不可以寫(xiě)成 == '1',只能寫(xiě)成byte(1),leetcode上則只能寫(xiě)成 == '1'
// 估計(jì)是golang版本不同導(dǎo)致
// 填充grid[x][y]開(kāi)頭的陸地
if grid[x][y] == byte(1) {
if !visited[x][y] {
count++
dfs(grid, x, y, m, n, move, visited)
}
}
}
}
return count
}
// dfs深度優(yōu)先遍歷的簡(jiǎn)寫(xiě)
// 對(duì)包含grid[x][y]的陸地開(kāi)始,進(jìn)行floodFill(填充)
func dfs(grid [][]byte, x, y, m, n int, move [][]int, visited [][]bool) {
visited[x][y] = true
for i := 0; i < 4; i++ {
newX := x + move[i][0]
newY := y + move[i][1]
//(1)不越界;(2)沒(méi)被填充過(guò);(3)是陸地;3者同時(shí)滿足進(jìn)行下一層搜索
if !notArea(newX, newY, m, n) && !visited[newX][newY] &&
grid[newX][newY] == byte(1) {
dfs(grid, newX, newY, m, n, move, visited)
}
}
}
func newVisited(m, n int) [][]bool {
visited := make([][]bool, m)
for i := 0; i < m; i++ {
visited[i] = make([]bool, n)
}
return visited
}
func notArea(x, y, m, n int) bool {
return x < 0 || y < 0 || x >= m || y >= n
}
提交leetcode，通過(guò)
繼下一篇《(26)Go遞歸求解n皇后問(wèn)題》http://www.reibang.com/p/61beb6faa2b5
有bug歡迎指出
