当前位置: 首页 > news >正文

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

目录

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

题目的接口:

解题思路:

代码:

过啦!!!

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

题目的接口:

解题思路:

代码:

过啦!!!

写在最后:


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

题目的接口:

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

解题思路:

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

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

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

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

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

代码:

type pair struct {x inty 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) boolcheck = 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+jif 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] = 1sum := 1sum += 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 intfor n > 0 {sum += n % 10n = n / 10}return sum
}

过啦!!!

写在最后:

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

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

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

http://www.lryc.cn/news/160732.html

相关文章:

  • jsp页面出现“String cannot be resolved to a type”错误解决办法
  • 【go-zero】使用自带Redis方法
  • 离线数仓同步数据3
  • Prometheus+Grafana 搭建应用监控系统
  • Spring Boot整合Log4j2.xml的问题
  • 代码随想录算法训练营第五十八天 | 739. 每日温度,496.下一个更大元素 I
  • 【动手学深度学习】--文本预处理
  • 2023年最佳研发管理平台评选:哪家表现出色?
  • 轻量容器引擎Docker基础使用
  • questions
  • MojoTween:使用「Burst、Jobs、Collections、Mathematics」优化实现的Unity顶级「Tween动画引擎」
  • Vue3响应式源码实现
  • 【RapidAI】P1 中文文本切割程序
  • 4、QT中的网络编程
  • 单例模式(饿汉式单例 VS 懒汉式单例)
  • Oracle数据库连接之TNS-12541异常
  • sql中的排序函数dense_rank(),RANK()和row_number()
  • Flask狼书笔记 | 05_数据库
  • HJ70 矩阵乘法计算量估算
  • Doris数据库使用记录
  • 华为OD机试真题【篮球比赛】
  • sublime text 格式化json快捷键配置
  • Spring Cloud 面试题总结
  • 如何实现24/7客户服务自动化?
  • 2022年12月 C/C++(六级)真题解析#中国电子学会#全国青少年软件编程等级考试
  • 【Spring Cloud系列】 雪花算法原理及实现
  • Postgresql 阿里云部署排雷
  • l8-d10 TCP协议是如何实现可靠传输的
  • 9月9日扒面经
  • 项目实战:ES的增加数据和查询数据