跳跃游戏 IV-1345

[sl1673495]

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标：

i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

 

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
示例 2：

输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。
示例 3：

输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
示例 4：

输入：arr = [6,1,9]
输出：2
示例 5：

输入：arr = [11,22,7,7,7,7,7,7,7,22,13]
输出：3

提示：

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

本题和跳跃游戏 III-1306 的思路是一致的，只不过要多几个处理。

在开始的时候，需要针对最后一个特殊用例，中间有大量重复的数字 7 做一个处理，当连续重复数字超过两个以后，中间的数字都可以去掉，因为最短的路径一定是从第一个数字直接“跳跃”到最后一个数字。

处理完后，需要遍历一遍数组，把每个数字出现在的下标位置都记录下来，便于后续 BFS 的过程中找到。

根据 BFS 的特性，最先找到终点的那一条路径一定是最短的路径，因为 BFS 就相当于在模拟一次一次的跳跃，只不过每一次可以去跳跃：

1. index - 1。
2. index + 1。
3. 和当前数字相同的其他所有下标。

在每次 BFS while 循环开始的时候，先把当前队列里的 length 缓存下来，然后把 count + 1，接下来的 for 循环只针对缓存的 length 而不管遍历过程中新增的 length。

/**
 * @param {number[]} arr
 * @return {number}
 */
let minJumps = function (arr) {
    let n = arr.length
    if (n === 1) {
        return 0
    }

    // 连续出现超过两次的数字就抛弃掉
    let newArr = []
    let sameCount = 0
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === arr[i - 1]) {
            sameCount += 1
            if (sameCount >= 2) {
                continue
            } else {
                newArr.push(arr[i])
            }
        } else {
            newArr.push(arr[i])
            sameCount = 0
        }
    }
    arr = newArr
    n = arr.length
    // 遍历一遍 记录每个数字出现的下标位置
    let indexesMap = new Map()
    for (let i = 0; i < n; i++) {
        let val = arr[i]
        let indexes = indexesMap.get(val)
        if (!indexes) {
            indexesMap.set(val, [i])
        } else {
            indexes.push(i)
        }
    }

    let visited = []
    let count = 0
    let queue = [0]
    while (queue.length) {
        count++
        let len = queue.length
        for (let i = 0; i < len; i++) {
            let index = queue.shift()
            // 找到了 由于bfs的特性 此时用的跳跃次数一定是最少的
            if (index === n - 1) {
                return count - 1
            }

            // 没找到 继续把可以跳的几个位置都放入队列中
            let val = arr[index]
            let left = index - 1
            let right = index + 1
            let sameIndexes = indexesMap.get(val)

            if (left >= 0 && !visited[left]) queue.push(left)
            if (right < n && !visited[right]) queue.push(right)
            for (let sameIndex of sameIndexes) {
                if (sameIndex !== index && !visited[sameIndex]) {
                    queue.push(sameIndex)
                }
            }

            visited[index] = true
        }
    }
    return n
};

[xiaomisu]

你好 这个通不过leetcode的测试呀 超出时间限制