1345.跳跃游戏-iv.md

1345.跳跃游戏-iv

/*
 * @lc app=leetcode.cn id=1345 lang=typescript
 *
 * [1345] 跳跃游戏 IV
 */

// @lc code=start
function minJumps(arr: number[]): number {}
// @lc code=end

解法 1: BFS

function minJumps(arr: number[]): number {
  if (arr.length === 1) return 0
  const map = new Map<number, number[]>()
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i]
    if (!map.has(num)) map.set(num, [])
    map.get(num)?.push(i)
  }

  const cache = new Set<number>()
  const bfs = (start: Set<number>, depth = 1): number => {
    const tmp = new Set<number>()

    for (const cur of start) {
      for (const i of [cur + 1, cur - 1]) {
        if (i === arr.length - 1) return depth
        if (cache.has(i) || tmp.has(i) || i < 0 || i >= arr.length) continue

        tmp.add(i)
      }
      if (cache.has(cur)) continue

      for (const i of map.get(arr[cur])!) {
        if (i === arr.length - 1) return depth
        if (cache.has(i) || tmp.has(i) || i < 0 || i >= arr.length) continue

        tmp.add(i)
        cache.add(i)
      }
    }

    return bfs(tmp, depth + 1)
  }

  return bfs(new Set([0]))
}

解法 2: 双向 BFS

function minJumps(arr: number[]): number {
  if (arr.length === 1) {
    return 0
  }
  const map = new Map<number, number[]>()
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i]
    if (!map.has(num)) map.set(num, [])
    map.get(num)?.push(i)
  }
  const cache = new Set<number>()
  const bfs = (queue: Set<number>, target: Set<number>, depth = 1): number => {
    const tmp = new Set<number>()

    for (const cur of queue) {
      for (const i of [cur + 1, cur - 1]) {
        if (target.has(i)) return depth
        if (cache.has(i) || tmp.has(i) || i < 0 || i >= arr.length) continue

        tmp.add(i)
      }
      if (cache.has(cur)) continue

      for (const i of map.get(arr[cur])!) {
        if (target.has(i)) return depth
        if (cache.has(i) || tmp.has(i) || i < 0 || i >= arr.length) continue

        tmp.add(i)
        cache.add(i)
      }
    }

    return bfs(target, tmp, depth + 1)
  }
  return bfs(new Set([0]), new Set([arr.length - 1]))
}

test.each([
  { input: { arr: [100, -23, -23, 404, 100, 23, 23, 23, 3, 404] }, output: 3 },
  { input: { arr: [7] }, output: 0 },
  { input: { arr: [7, 6, 9, 6, 9, 6, 9, 7] }, output: 1 },
])('input: arr = $input.arr', ({ input: { arr }, output }) => {
  expect(minJumps(arr)).toEqual(output)
})