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