1306. Jump Game III¶
题目信息¶
- 题号:
1306
- 难度:
Medium
- 主题:
数组、图搜索、可达性
- 原题:
- 重点:
从下标
i可跳到i + arr[i]或i - arr[i],只能落在合法范围;判断能否到达任意值为零的位置
题目重述¶
给定非负整数数组 arr 和起始下标 start。当前位于下标 i 时,可以跳到 i + arr[i] 或 i - arr[i],但目标下标必须位于数组范围内。
可以执行任意次数跳跃。请判断是否能够到达某个值为 0 的位置;允许经过同一位置,但实现需要避免无限循环。
1 <= arr.length <= 5 * 10^4,0 <= arr[i] < arr.length,0 <= start < arr.length。
自建示例¶
通过多次跳跃到达零:
输入:arr = [2,3,1,1,0], start = 0
输出:true
解释:可以按 0 -> 2 -> 1 -> 4 跳跃,最终到达值为 0 的下标 4。
零位置被可达范围隔离时失败:
输入:arr = [1,2,0], start = 0
输出:false
解释:从 0 只能到 1,而从 1 只能回到 0 或跳出数组,无法到达下标 2。