目錄

題目：劍指 Offer 12. 矩陣中的路徑 - 力扣（LeetCode）

題目的接口：

解題思路：

代碼：

過啦?。?！

題目：劍指 Offer 13. 機器人的運動范圍 - 力扣（LeetCode）

題目的接口：

解題思路：

代碼：

過啦?。?！

寫在最后：

題目：劍指 Offer 12. 矩陣中的路徑 - 力扣（LeetCode）

題目的接口：

func exist(board [][]byte, word string) bool {

}

解題思路：

這是一道經典的搜索題，用和是深度優(yōu)先搜素，這個方法是我比較喜歡使用的方法，我來講講這個實現方法的幾個核心：

我們從上往下看，dic 數組的作用是讓我們可以搜索的時候往四個方向搜素；

vis 數組的作用是用來判斷在這次搜索中，格子是否被占用；

check 函數，這里就是 golang 的特色實現，我們把函數邏輯實現在主邏輯內；

最后的那個循環(huán)就是將每個格子都作為起點走搜索的邏輯。

代碼：

type pair struct {
    x int
    y int
}

var dic = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func exist(board [][]byte, word string) bool {
    h, w := len(board), len(board[0])

    // 用于判斷格子是否已經被占用
    vis := make([][]bool, h)
    for i := range vis {
        vis[i] = make([]bool, w)
    }

    // 搜索函數
    var check func(i, j, k int) bool
    check = func(i, j, k int) bool {
        if board[i][j] != word[k] { // 字符匹配失敗
            return false
        }
        if k == len(word)-1 { // 單詞匹配成功
            return true
        }
        vis[i][j] = true // 標記使用過的單元格
        defer func() { vis[i][j] = false }() // 回溯的時候還原使用過的單元格
        for _, dir := range dic {
            newI, newJ := dir.x+i, dir.y+j
            if newI >= 0 && newI < h && newI < h && newJ >= 0 && newJ < w && !vis[newI][newJ] {
                if  check(newI, newJ, k+1) {
                    return true
                }
            }
        }
        return false
    }

    // 每個格子作為起點搜素
    for i, row := range board {
        for j := range row {
            if check(i, j, 0) {
                return true
            }
        }
    }
    return false
}

過啦！??！

題目：劍指 Offer 13. 機器人的運動范圍 - 力扣（LeetCode）

題目的接口：

func movingCount(m int, n int, k int) int {

}

解題思路：

這道題還是一道搜索題，跟上一題差不多，主要有兩個要點，首先是這道題我們得計算機器人走的步數，第二點是我們需要求出他的位數和才能判斷他是否能夠抵達該位置。

代碼：

func movingCount(m int, n int, k int) int {
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	return dfs(m, n, 0, 0, k, dp)
}

func dfs(m, n, i, j, k int, dp [][]int) int {
	if i < 0 || j < 0 || i >= m || j >= n || dp[i][j] == 1 || (sumPos(i)+sumPos(j)) > k {
		return 0
	}

	dp[i][j] = 1

	sum := 1
	sum += dfs(m, n, i, j+1, k, dp)
	sum += dfs(m, n, i+1, j, k, dp)
	return sum
}

// 求所有位之和
func sumPos(n int) int {
	var sum int

	for n > 0 {
		sum += n % 10
		n = n / 10
	}

	return sum
}

過啦?。?！

寫在最后：

以上就是本篇文章的內容了，感謝你的閱讀。

如果感到有所收獲的話可以給博主點一個贊哦。

如果文章內容有遺漏或者錯誤的地方歡迎私信博主或者在評論區(qū)指出~文章來源地址http://www.zghlxwxcb.cn/news/detail-703501.html

到了這里，關于【LeetCode】劍指 Offer ＜二刷＞（6）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！