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

2022-08-10 22:32:24 浏览数 (2)

2022-08-10:为了给刷题的同学一些奖励,力扣团队引入了一个弹簧游戏机,

游戏机由 N 个特殊弹簧排成一排,编号为 0 到 N-1,

初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处,

通过按动弹簧,可以选择把小球向右弹射 jumpi 的距离,或者向左弹射到任意左侧弹簧的位置,

也就是说,在编号为 i 弹簧处按动弹簧,

小球可以弹向 0 到 i-1 中任意弹簧或者 i jumpi 的弹簧(若 i jumpi>=N ,则表示小球弹出了机器),

小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励,你需要将小球弹出机器。

请求出最少需要按动多少次弹簧,可以将小球从编号 0 弹簧弹出整个机器,即向右越过编号 N-1 的弹簧。

答案2022-08-10:

宽度优先遍历。Index Tree。

时间复杂度:O(N*logN)。

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

代码语言: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代码

0 人点赞