支付网站备案,做网站需要商标注册吗,北京企业建站哪家好,360优化大师官方免费下载文章目录 刷题前唠嗑题目#xff1a;最长平衡子字符串题目描述代码与解题思路偷看大佬题解 结语 刷题前唠嗑 LeetCode? 启动#xff01;#xff01;#xff01;
嗯#xff1f;什么#xff1f;今天是 hard#xff1f;陷入沉思。。。先看看题吧
题目#xff1a;最长平… 文章目录 刷题前唠嗑题目最长平衡子字符串题目描述代码与解题思路偷看大佬题解 结语 刷题前唠嗑 LeetCode? 启动
嗯什么今天是 hard陷入沉思。。。先看看题吧
题目最长平衡子字符串
题目链接2258. 逃离火灾
题目描述 这题目可太长啦不过题意还是挺好理解滴
代码与解题思路
type pair struct { x, y int }
var dir []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}func maximumMinutes(grid [][]int) int {m, n : len(grid), len(grid[0])// bfs 函数取三个数, 到达安全屋/安全屋上边/安全屋左边bfs : func(q []pair) (int, int, int) {time : make([][]int, m)for i, _ : range time { // 给 time 数组赋值为 -1time[i] make([]int, n)for j, _ : range time[i] {time[i][j] -1 // 表示未访问该点}}for _, v : range q { // 设置起点time[v.x][v.y] 0}for t : 1; len(q) 0; t {tmp : qq nilfor _, v : range tmp {for _, v2 : range dir {// x, y 设置偏移量, 然后控制边界, grid 0 表示能走(不是墙), time 0 也就是 -1 表示未访问该节点if x, y : v.xv2.x, v.yv2.y; x 0 x m y 0 y n grid[x][y] 0 time[x][y] 0 { time[x][y] tq append(q, pair{x, y}) // 需要 bfs 的新坐标起点}}}}return time[m-1][n-1], time[m-1][n-2], time[m-2][n-1]}manToHouseTime, m1, m2 : bfs([]pair{{0, 0}})if manToHouseTime 0 { // 人能否到安全屋return -1}firPos : []pair{}for i, row : range grid { // 收集火的位置for j, x : range row {if x 1 {firPos append(firPos, pair{i, j})}}}fireToHouseTime, f1, f2 : bfs(firPos)if fireToHouseTime 0 { // 火能否到安全屋return 1_000_000_000}d : fireToHouseTime - manToHouseTime if d 0 { // 火到安全屋的时间是否比人快return -1}// 如果人需要从上面或左边进入安全屋, 与火到这两个位置的时间进行比较if m1 ! -1 m1d f1 || m2 ! -1 m2d f2 { return d}return d-1
}我就非常朴素的把题目翻译了一遍算是模拟题意吧具体是这样的
首先需要分析的就是火和人一起走向安全屋如果火到安全屋的上面或者左边之后人就进不了安全屋了所以我们在进行 bfs 搜索最短路的时候需要返回 安全屋/安全屋上面/安全屋左边 这几个位置考虑火把人进入安全屋的路径挡住的情况
首先 bfs 人查看是否能进安全屋如果不能就返回 -1然后遍历地图收集火的位置然后 bfs 火查看火能否进安全屋如果不能就返回 1_000_000_000然后判断火到安全屋的时间是否比人快如果比人快就返回 -1最后判断火是否会到安全屋的上方或左方对人进入安全屋造成影响如果有影响就让人少等一分钟提前进安全屋如果没影响就正常返回前往安全屋的时间
按照这个思路一步步走最后结果没什么问题
偷看大佬题解
emmm
二分查找我去看了看我尝试理解理解失败。。。开摆今天就到这里吧~
结语
今天的每日一题就当是练习 bfs 啦
