1306-跳跃游戏III.md

题目描述

跳跃游戏III

题目简述

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

分类

中等 DFS 待优化

思路

思路1

/**
 * @param {number[]} arr
 * @param {number} start
 * @return {boolean}
 */
var canReach = function(arr, start) {
  // 记录已经遍历过的位置
  const hasArrived = []
  function backTrack (index) {
    if (arr[index] === 0) return true
    hasArrived.push(index)
    const left = index - arr[index]
    const right = index + arr[index]
    if (left >= 0 && hasArrived.indexOf(left) === -1) {
      if (backTrack(left)) return true
    }
    if (right < arr.length && hasArrived.indexOf(right) === -1) {
      if (backTrack(right)) return true
    }
  }
  return backTrack(start) || false
};

• 问题分析
  • 首先我们需要确定题目中的任一，意思是有多个0的情况，我们只需要满足能够到达某一个0即可，是贪心的。
  • 在某个位置我们有两种可能性去进行跳跃，所以我们需要进行尝试。目前我对DFS的理解是，一种特殊的回溯，每次只有两种情况可选择的回溯。
  • 由于我们在跳跃的过程中，可能出现反复跳跃的情况，所以我们需要记录当前已经经过的位置。再选择下一个可跳跃的位置时，去除已经跳跃的位置，否则形成了不可跳出的循环。由于跳跃的位置是可能产生越界的，所以我们也需要对越界情况进行剔除。
  • 当arr[index] === 0时，找到元素值为0，返回结果。