Leetcode1306. 跳跃游戏 III(medium,BFS,DFS)
游戏 DFS BFS III Medium 跳跃
2023-09-14 09:01:30 时间
目录
1. 问题描述
这里有一个非负整数数组 arr
,你最开始位于该数组的起始下标 start
处。当你位于下标 i
处时,你可以跳到 i + arr[i]
或者 i - arr[i]
。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意,不管是什么情况下,你都无法跳到数组之外。
示例 1:
输入:arr = [4,2,3,0,3,1,2], start = 5 输出:true 解释: 到达值为 0 的下标 3 有以下可能方案: 下标 5 -> 下标 4 -> 下标 1 -> 下标 3 下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
示例 2:
输入:arr = [4,2,3,0,3,1,2], start = 0 输出:true 解释: 到达值为 0 的下标 3 有以下可能方案: 下标 0 -> 下标 4 -> 下标 1 -> 下标 3
示例 3:
输入:arr = [3,0,2,1,2], start = 2 输出:false 解释:无法到达值为 0 的下标 1 处。
提示:
1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jump-game-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题分析
应该就是普通的深度或广度优先搜索都可以吧。
在每个节点处,可以向左跳或者向右跳,但是要满足不能跳出去(即越界),并且不要重复访问(重复访问没有意义)。
3. 代码实现
from typing import List
from collections import deque
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
q = deque([start])
visited = set([start])
while len(q) > 0:
node = q.pop()
if arr[node] == 0:
return True
left = node - arr[node]
if left >= 0 and left not in visited:
q.append(left)
visited.add(left)
right = node + arr[node]
if right < len(arr) and right not in visited:
q.append(right)
visited.add(right)
return False
if __name__ == "__main__":
sln = Solution()
arr = [4,2,3,0,3,1,2]
start = 5
print(sln.canReach(arr, start))
arr = [4,2,3,0,3,1,2]
start = 0
print(sln.canReach(arr, start))
arr = [3,0,2,1,2]
start = 2
print(sln.canReach(arr, start))
arr = [0,1]
start = 1
print(sln.canReach(arr, start))
执行用时:52 ms, 在所有 Python3 提交中击败了94.80%的用户
内存消耗:20.3 MB, 在所有 Python3 提交中击败了45.97%的用户
嗯,随手一写,有这个表现也可以满意了。
相关文章
- 【说站】360右下角弹窗广告如何关闭?360浏览器游戏广告关闭方法
- 9.14VR行业大事件:高通或在测试下一代VR芯片;VR地下城游戏《Demeo》将于明年登陆PSVR 2
- RPG游戏高性能特效是怎么练成的?
- 元宇宙3D游戏开发规则丨元宇宙3D游戏链游系统开发实现技术逻辑及方案丨元宇宙3D游戏链游源码案例部署
- 探索 Linux 世界:支持的游戏之旅(linux支持的游戏)
- Linux平台上的游戏开发新思路(linux游戏开发)
- AMD Radeon 21.7.2 显卡驱动发布,支持游戏《切尔诺贝利》
- 独立开发三年的游戏 被“黑客”一波攻击全毁了?
- 红色之星:玩转游戏的神奇记忆法(redis游戏)
- 构建游戏公会基于Redis的实现方案(游戏公会 redis)
- Android游戏源码分享之2048
- JQuery做的一个简单的点灯游戏分享