当前位置:网站首页>2022-08-10:为了给刷题的同学一些奖励,力扣团队引入了一个弹簧游戏机, 游戏机由 N 个特殊弹簧排成一排,编号为 0 到 N-1, 初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹
2022-08-10:为了给刷题的同学一些奖励,力扣团队引入了一个弹簧游戏机, 游戏机由 N 个特殊弹簧排成一排,编号为 0 到 N-1, 初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹
2022-08-11 07:47:00 【福大大架构师每日一题】
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
}
}
执行结果如下:
边栏推荐
猜你喜欢
随机推荐
1106 2019 Sequence (15 points)
1071 Small Gamble (15 points)
TF中的One-hot
美术2.4 UV原理基础
There may be fields that cannot be serialized in the abnormal object of cdc and sqlserver. Is there anyone who can understand it? Help me to answer
JUC并发编程
Activity的四种状态
JRS303-Data Verification
我的创作纪念日丨感恩这365天来有你相伴,不忘初心,各自精彩
【415. 字符串相加】
支持各种文件快速重命名最简单的小技巧
查找最新人员工资和上上次人员工资的变动情况
1002 Write the number (20 points)
2.1-梯度下降
Four operations in TF
项目2-年收入判断
迷你图书馆系统(对象+数组)
Activity的四种启动模式
租房小程序
1076 Wifi Password (15 points)