2022-08-10：为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机， 游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1， 初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹

2022-08-10：为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机，
游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1，
初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，
通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置，
也就是说，在编号为 i 弹簧处按动弹簧，
小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器），
小球位于编号 0 处的弹簧时不能再向左弹。
为了获得奖励，你需要将小球弹出机器。
请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

答案2022-08-10：

宽度优先遍历。Index Tree。
时间复杂度：O(N*logN)。

代码用rust编写。代码如下：

fn main() {

    let mut jump1: Vec<i32> = vec![2, 5, 1, 1, 1, 1];

    let mut jump2 = jump1.clone();

    let ans1 = min_jump(&mut jump1);

    let ans2 = min_jump2(&mut jump2);

    println!("ans1 = {}", ans1);

    println!("ans2 = {}", ans2);

}

// 宽度优先遍历

// N*logN

fn min_jump(jump: &mut Vec<i32>) -> i32 {

    let n = jump.len() as i32;

    let mut queue: Vec<i32> = vec![];

    for _ in 0..n {

        queue.push(0);

    }

    let mut l: i32 = 0;

    let mut r: i32 = 0;

    queue[r as usize] = 0;

    r += 1;

    let mut it = IndexTree::new(n);

    // 1...n初始化的时候 每个位置填上1

    for i in 1..n {

        it.add(i, 1);

    }

    let mut step: i32 = 0;

    while l != r {

        // 队列里面还有东西

        // tmp记录了当前层的终止位置！

        let tmp = r;

        // 当前层的所有节点，都去遍历!

        while l < tmp {

            let cur = queue[l as usize];

            let forward = cur + jump[cur as usize];

            if forward >= n {

                return step + 1;

            }

            if it.value(forward) != 0 {

                queue[r as usize] = forward;

                r += 1;

                it.add(forward, -1);

            }

            // cur

            // 1....cur-1 cur

            while it.sum(cur - 1) != 0 {

                let find0 = find(&mut it, cur - 1);

                it.add(find0, -1);

                queue[r as usize] = find0;

                r += 1;

            }

            l += 1;

        }

        step += 1;

    }

    return -1;

}

fn find(it: &mut IndexTree, mut right: i32) -> i32 {

    let mut left = 0;

    let mut mid;

    let mut find0 = 0;

    while left <= right {

        mid = (left + right) / 2;

        if it.sum(mid) > 0 {

            find0 = mid;

            right = mid - 1;

        } else {

            left = mid + 1;

        }

    }

    return find0;

}

pub struct IndexTree {

    tree: Vec<i32>,

    n: i32,

}

impl IndexTree {

    pub fn new(size: i32) -> Self {

        let mut tree: Vec<i32> = vec![];

        for _ in 0..size + 1 {

            tree.push(0);

        }

        Self { tree, n: size }

    }

    pub fn value(&mut self, index: i32) -> i32 {

        if index == 0 {

            return self.sum(0);

        } else {

            return self.sum(index) - self.sum(index - 1);

        }

    }

    pub fn sum(&mut self, i: i32) -> i32 {

        let mut index = i + 1;

        let mut ret = 0;

        while index > 0 {

            ret += self.tree[index as usize];

            index -= index & -index;

        }

        return ret;

    }

    pub fn add(&mut self, i: i32, d: i32) {

        let mut index = i + 1;

        while index <= self.n {

            self.tree[index as usize] += d;

            index += index & -index;

        }

    }

}

// 感谢黄汀同学

// 弄出了时间复杂度O(N)的过程

// 和大厂刷题班，第10节，jump game类似

fn min_jump2(jump: &mut Vec<i32>) -> i32 {

    let nn = jump.len() as i32;

    let mut ans = nn;

    let mut next = jump[0];

    if next >= nn {

        return 1;

    }

    if next + jump[next as usize] >= nn {

        return 2;

    }

    // dp[i] : 来到i位置，最少跳几步？

    let mut dp: Vec<i32> = vec![];

    for _ in 0..nn + 1 {

        dp.push(nn);

    }

    // dis[i] : <= i步的情况下，最远能跳到哪？

    let mut dis: Vec<i32> = vec![];

    for _ in 0..nn {

        dis.push(0);

    }

    // 如果从0开始向前跳，<=1步的情况下，最远当然能到next

    dis[1] = next;

    // 如果从0开始向前跳，<=2步的情况下，最远可能比next + jump[next]要远，

    // 这里先设置，以后可能更新

    dis[2] = next + jump[next as usize];

    dp[(next + jump[next as usize]) as usize] = 2;

    let mut step = 1;

    for i in 1..nn {

        if i > dis[step as usize] {

            step += 1;

        }

        dp[i as usize] = get_min(dp[i as usize], step + 1);

        next = i + jump[i as usize];

        if next >= nn {

            ans = get_min(ans, dp[i as usize] + 1);

        } else if dp[next as usize] > dp[i as usize] + 1 {

            dp[next as usize] = dp[i as usize] + 1;

            dis[dp[next as usize] as usize] = get_max(dis[dp[next as usize] as usize], next);

        }

    }

    return ans;

}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {

    if a > b {

        a

    } else {

        b

    }

}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {

    if a < b {

        a

    } else {

        b

    }

}

执行结果如下：

左神java代码

2022-08-10：为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机， 游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1， 初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹的相关教程结束。