跳跃游戏 III

标签: 深度优先搜索 广度优先搜索 数组

难度: Medium

这里有一个非负整数数组 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

Submission

运行时间: 29 ms

内存: 34.7 MB

from typing import List

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        # 创建一个集合用于记录已经访问过的位置
        visited = set()
        
        # 定义深度优先搜索函数
        def dfs(index):
            # 如果当前位置已经访问过，直接返回False
            if index in visited:
                return False
            
            # 将当前位置标记为已访问
            visited.add(index)
            
            # 如果当前位置的值为0，表示可以跳到对应元素值为0的位置，返回True
            if arr[index] == 0:
                return True
            
            # 尝试向右跳转，如果跳转后的位置在数组范围内且可以跳到对应元素值为0的位置，返回True
            if index + arr[index] < len(arr) and dfs(index + arr[index]):
                return True
            
            # 尝试向左跳转，如果跳转后的位置在数组范围内且可以跳到对应元素值为0的位置，返回True
            if index - arr[index] >= 0 and dfs(index - arr[index]):
                return True
            
            # 如果无法跳到对应元素值为0的位置，返回False
            return False
        
        # 从起始位置开始深度优先搜索
        return dfs(start)

solution = Solution()
arr = [4, 2, 3, 0, 3, 1, 2]
start = 5
print(solution.canReach(arr, start))  # 输出: True

Explain

本题采用深度优先搜索（DFS）的方法来解决。从起始索引 start 开始，尝试向数组的两个方向跳跃，即向右跳到 i + arr[i] 和向左跳到 i - arr[i]，并递归地进行这一过程。为了避免重复访问相同的索引，使用一个集合 visited 记录已经访问过的索引。如果达到的位置的值为0，则成功找到一条路径，返回 true。如果尝试所有可能的跳跃后都未能找到值为0的位置，返回 false。

时间复杂度: O(n)

空间复杂度: O(n)

from typing import List

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        visited = set()  # 创建一个集合用于记录已经访问过的位置
        
        def dfs(index):
            if index in visited:  # 如果当前位置已经访问过，直接返回False
                return False
            visited.add(index)  # 将当前位置标记为已访问
            if arr[index] == 0:  # 如果当前位置的值为0，表示可以跳到对应元素值为0的位置，返回True
                return True
            if index + arr[index] < len(arr) and dfs(index + arr[index]):  # 尝试向右跳转
                return True
            if index - arr[index] >= 0 and dfs(index - arr[index]):  # 尝试向左跳转
                return True
            return False  # 如果无法跳到对应元素值为0的位置，返回False
        
        return dfs(start)  # 从起始位置开始深度优先搜索

solution = Solution()
arr = [4, 2, 3, 0, 3, 1, 2]
start = 5
print(solution.canReach(arr, start))  # 输出: True

Explore

DFS 和 BFS 都可以用来解决这个问题，但是 DFS 在某些情况下可能更简单直观，特别是在需要找到任一可行解而非最短解的问题上。DFS通常需要较少的内存，因为它不需要存储所有扩展的状态节点，而是随着递归的深入逐渐探索。此外，由于题目只需要判断是否存在一条路径到达值为0的节点，DFS能够在找到第一个满足条件的结果时立即停止搜索，这可能比BFS在某些情况下更快。

如果数组中的数字非常大，确实会影响算法的性能，因为较大的数字会导致尝试访问数组界外的索引，从而增加了边界检查的操作。在DFS实现中，每次跳跃前都需要检查新的索引是否在数组范围内（即索引是否非负且小于数组长度）。如果跳跃步长超过数组长度，这个检查将阻止访问无效索引，从而避免程序崩溃或不正确的行为。

递归实现的栈溢出风险主要取决于递归的深度，这通常与数组的大小和元素的值有关。在处理大数组或元素值导致频繁和深层的递归调用时，存在较高的栈溢出风险。为减轻这种风险，可以考虑使用迭代版本的DFS和显式栈，或转换为使用BFS，因为BFS通常使用队列处理节点，避免了深度递归的问题。优化递归算法的一种方法是利用尾递归，但Python默认不支持尾递归优化，因此更换算法或数据结构可能是更安全的选择。

示例中的DFS逻辑在找到第一个值为0的节点时就会停止搜索，并返回true，这意味着它只关注找到首个满足条件的路径。一旦找到一个解决方案，就不会继续探索其他可能的跳跃路径。这种方法适用于题目要求的判断是否存在解决方案的情况，而不需要找到所有可能的解决方案或最短路径。