minimum-sideway-jumps.rs

#![allow(dead_code, unused, unused_variables, non_snake_case)]

fnmain(){
assert_eq!(Solution::min_side_jumps(vec![0,2,1,0,3,0]),2);
assert_eq!(Solution::min_side_jumps(vec![0,1,1,3,3,0]),0);
assert_eq!(Solution::min_side_jumps(vec![0,1,2,3,0]),2);
}

structSolution;

implSolution{
/// dp 这个看不懂
pubfnmin_side_jumps1(obstacles:Vec<i32>) -> i32{
letmut dp = [1,0,1i64];
// 起点都没障碍物，所以起点为0

for i in1..obstacles.len(){
let a = obstacles[i];
// 说明当前位置三个跑道都没有障碍物，因此
letmut new_dp = [0,0,0];
if a == 0{
 new_dp[0] = dp[0].min(1 + dp[1].min(dp[2]));
 new_dp[1] = dp[1].min(1 + dp[0].min(dp[2]));
 new_dp[2] = dp[2].min(1 + dp[0].min(dp[1]));
}elseif a == 1{
 new_dp[0] = i32::MAXasi64;
 new_dp[1] = dp[1].min(1 + dp[2]);
 new_dp[2] = dp[2].min(1 + dp[1]);
}elseif a == 2{
 new_dp[0] = dp[0].min(1 + dp[2]);
 new_dp[1] = i32::MAXasi64;
 new_dp[2] = dp[2].min(1 + dp[0]);
}else{
 new_dp[0] = dp[0].min(1 + dp[1]);
 new_dp[1] = dp[1].min(1 + dp[0]);
 new_dp[2] = i32::MAXasi64;
}

 dp = new_dp;
}

*dp[..].into_iter().min().unwrap()asi32
}

/// dp[i][j], 0 < i < 3, j < obstacles.len() 表示第i条跑道在第j点时的最少跳跃次数
/// 所以dp[i][j] 可能有：1.如果有障碍物的话，就不符合要求
/// 2.没有障碍物，就是dp[i-1][j]或者是dp[i][n]+1的最小值(因为跳跃到[i,j]位置不值可以从[i-1,j]跳跃而来，而且还可以从j处的其他跑道而来。所以统一下跳跃的次数就行了。)
pubfnmin_side_jumps(obstacles:Vec<i32>) -> i32{
// 起点都没障碍物，所以起点为0
letmut dp = [1,0,1i64];

for i in1..obstacles.len(){
let a = obstacles[i];// 障碍物
letmut new_dp = [0,0,0];
letmut min = i32::MAXasi64;

for i in0..3{
if a - 1 == i {
 new_dp[i asusize] = i32::MAXasi64;
}else{
 new_dp[i asusize] = dp[i asusize];
}

 min = min.min(new_dp[i asusize]);
}

// 因为任何点都可以从当前位置的其他点+1跳来，需要判断下是不是其他点+1跳过来的更短少

for i in0..3{
if a - 1 != i {
 new_dp[i asusize] = new_dp[i asusize].min(min + 1);
}
}

 dp = new_dp;
}

*dp[..].into_iter().min().unwrap()asi32
}
}