【LeetCode】剑指 Offer <二刷>(6)

这篇具有很好参考价值的文章主要介绍了【LeetCode】剑指 Offer <二刷>(6)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目:剑指 Offer 12. 矩阵中的路径 - 力扣(LeetCode)

题目的接口:

解题思路:

代码:

过啦!!!

题目:剑指 Offer 13. 机器人的运动范围 - 力扣(LeetCode)

题目的接口:

解题思路:

代码:

过啦!!!

写在最后:


题目:剑指 Offer 12. 矩阵中的路径 - 力扣(LeetCode)

【LeetCode】剑指 Offer <二刷>(6),38 天二刷剑指 Offer,leetcode,算法,职场和发展,go,golang

题目的接口:

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

}

解题思路:

这是一道经典的搜索题,用和是深度优先搜素,这个方法是我比较喜欢使用的方法,我来讲讲这个实现方法的几个核心:

我们从上往下看,dic 数组的作用是让我们可以搜索的时候往四个方向搜素;

vis 数组的作用是用来判断在这次搜索中,格子是否被占用;

check 函数,这里就是 golang 的特色实现,我们把函数逻辑实现在主逻辑内;

最后的那个循环就是将每个格子都作为起点走搜索的逻辑。

代码:

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
}

过啦!!!

【LeetCode】剑指 Offer <二刷>(6),38 天二刷剑指 Offer,leetcode,算法,职场和发展,go,golang

题目:剑指 Offer 13. 机器人的运动范围 - 力扣(LeetCode)

【LeetCode】剑指 Offer <二刷>(6),38 天二刷剑指 Offer,leetcode,算法,职场和发展,go,golang

题目的接口:

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
}

过啦!!!

【LeetCode】剑指 Offer <二刷>(6),38 天二刷剑指 Offer,leetcode,算法,职场和发展,go,golang

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~文章来源地址https://www.toymoban.com/news/detail-703501.html

到了这里,关于【LeetCode】剑指 Offer <二刷>(6)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】剑指 Offer <二刷>(6)

    目录 题目:剑指 Offer 12. 矩阵中的路径 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 13. 机器人的运动范围 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这是一道经典的搜索题,用和是深度优先搜素,这个方法

    2024年02月09日
    浏览(43)
  • (搜索) 剑指 Offer 38. 字符串的排列 ——【Leetcode每日一题】

    难度:中等 输入一个字符串,打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组,但里面 不能有重复元素 。 示例: 输入:s = “abc” 输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”] 限制 : 1 = s 的长度 = 8 💡思路:回溯 可以直接 暴力穷举 ,但

    2024年02月12日
    浏览(51)
  • 【leetcode刷题之路】剑指Offer(3)——搜索与回溯算法

    7 搜索与回溯算法 7.1 【BFS】剑指 Offer 32 - I - 从上到下打印二叉树 https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/   这里借助队列来实现广度优先遍历,由于需要访问每一层的节点,而且这一层访问才可以访问下一层,所以可以考虑队列的先进先出,先把每一层的节

    2024年02月13日
    浏览(59)
  • 【leetcode刷题之路】剑指Offer(4)——分治+排序算法+动态规划

    8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/   前序遍历是根左右,中序遍历是左根右,这也就意味着前序遍历的第一个节点是整棵树的根节点,顺着这个节点找到它在中序遍历中的位置,即为in_root,那么in_root左边的都在左子

    2024年02月11日
    浏览(59)
  • 【算法】双指针——leetcode盛最多水的容器、剑指Offer57和为s的两个数字

    盛水最多的容器 (1)暴力解法   算法思路:我们枚举出所有的容器大小,取最大值即可。   容器容积的计算方式:   设两指针 i , j ,分别指向水槽板的最左端以及最右端,此时容器的宽度为 j - i 。由于容器的高度由两板中的较短的板决定,因此可得容积公式 :

    2024年02月13日
    浏览(48)
  • 【LeetCode】剑指 Offer(28)

    目录 题目:剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - I. 二叉树的深度 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - II. 平衡二叉树 - 力扣(Leetcode) 题目的接

    2023年04月24日
    浏览(52)
  • 【LeetCode】剑指 Offer(26)

    目录 题目:剑指 Offer 51. 数组中的逆序对 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这一道题,我的思路是用双指针暴力求解, 但这个数组长度,O(N^2)的时间复杂度肯定是不可能把所有样例跑完, 看了大佬的思路,用的是归并排序,(如果不

    2023年04月11日
    浏览(43)
  • 【LeetCode】剑指 Offer(27)

    目录 题目:剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 那么这道题呢, 如果只是作为一道题,或者说笔试题, 我们当然是二话不说直接暴力拿下, 来看代码: 是的,就是这么简单,三行代码暴力拿下

    2023年04月13日
    浏览(45)
  • 【LeetCode】剑指 Offer(25)

    目录 题目:剑指 Offer 49. 丑数 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 丑数这道题用到一点动态规划的思想, 具体思路如下: 根据题意: 如果说第一个丑数是一,包含质因子 2、3 和 5 的数称作丑数, 那么我们发现,之后的丑数: 都是前

    2023年04月09日
    浏览(52)
  • 【LeetCode】剑指 Offer(21)

    目录 题目:剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 40. 最小的k个数 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题,我的思路是直接排序, 然后返回中间

    2023年04月10日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包