在每次 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
};
给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。
每一步,你可以从下标 i 跳到下标:
i + 1 满足:i + 1 < arr.length i - 1 满足:i - 1 >= 0 j 满足:arr[i] == arr[j] 且 i != j 请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意:任何时候你都不能跳到数组外面。
提示:
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 就相当于在模拟一次一次的跳跃,只不过每一次可以去跳跃:
index - 1
。index + 1
。和当前数字相同的其他所有下标
。在每次 BFS while 循环开始的时候,先把当前队列里的
length
缓存下来,然后把count + 1
,接下来的 for 循环只针对缓存的length
而不管遍历过程中新增的length
。