前言#
今天也是两道题，两道都是中等，其中一道是变体
题目1#
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。提示：
1 <= nums.length <= 1040 <= nums[i] <= 105
分析#
这道题暴力解法很简单，双层for循环，时间复杂度为O(n ^ 2)，根据官方的尿性，这个方案我们可以直接跳过。
前面我们说过，这个数组只是一维的，那么大部分情况下我们都可以在O(n)的情况下实现。
我们怎么知道这条路可以走到头呢？只要最后一步可以跳出即可。如果这个元素的值是0，那这条路就是断了。
前面我们还说过，看到最长、最短、最大、最小我们可以思考下是否可以用动态规划实现。
那么我们这道题能不能呢？当然可以。
那么走流程：
- 确认目标，根据求什么设什么，
dp[i]表示当前最大可以跳的距离； - 找关系：很明显当前这一步和之前一步有关系，之前一步可能可以跳的比当前这一步的远，所以选择最远那个，所以存在
dp[i] = max(dp[i - 1], nums[i] + i)的关系。 - 初始值：因为我们需要
dp[i - 1]，所以初始需要处理第一个 - 优化：我们只需要上一个元素，所以我们并不需要记录整个数组，所以我们搞个变量记录下即可。
解#
pub fn can_jump(nums: Vec<i32>) -> bool {
let len = nums.len();
if len <= 1 {
return true;
}
let mut l = nums[0] as usize;
for i in 1..len {
if l < i {
return false;
}
l = l.max(i + nums[i] as usize)
}
return true;
}代码没啥好说的
测试用例#
#[cfg(test)]
mod tests {
use super::{can_jump, improve_can_jump};
#[test]
fn test_can_jump() {
assert_eq!(can_jump([2, 3, 1, 1, 4].to_vec()), true);
assert_eq!(can_jump([3, 2, 1, 0, 4].to_vec()), false);
assert_eq!(can_jump([0].to_vec()), true);
assert_eq!(can_jump([2, 0, 0].to_vec()), true);
assert_eq!(can_jump([1, 2, 0, 1].to_vec()), true);
assert_eq!(
can_jump(
[
2, 0, 6, 9, 8, 4, 5, 0, 8, 9, 1, 2, 9, 6, 8, 8, 0, 6, 3, 1, 2, 2, 1, 2, 6, 5,
3, 1, 2, 2, 6, 4, 2, 4, 3, 0, 0, 0, 3, 8, 2, 4, 0, 1, 2, 0, 1, 4, 6, 5, 8, 0,
7, 9, 3, 4, 6, 6, 5, 8, 9, 3, 4, 3, 7, 0, 4, 9, 0, 9, 8, 4, 3, 0, 7, 7, 1, 9,
1, 9, 4, 9, 0, 1, 9, 5, 7, 7, 1, 5, 8, 2, 8, 2, 6, 8, 2, 2, 7, 5, 1, 7, 9, 6
]
.to_vec()
),
true
);
}
}题目2#
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。示例 2:
输入: nums = [2,3,0,1,4]
输出: 2提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000- 题目保证可以到达
nums[n-1]
分析#
结合上一题的解法，我们这题基本上没多大变化，因为每次都是最远跳跃距离意味着整体最少跳跃次数。
但是，这道题需要我们绕个弯（还是那句话：数理思维）。
这道题有个重点，跳跃的距离和当前正在跳是冲突的，简单地说就是步伐和正在走的这一步的关系，你的脚已经在半空中了，你可以调整步伐，但是只能在脑子里调整，当前这一步要怎么走已经是确定好的了。
放到这道题中就是，你这一个元素要跳的这段距离我们都得走一遍（正在走的那一步），然后取里面绝对路径可以跳的最远那货即可（也就是调整步伐，自然是选最远的）。
解#
pub fn jump(nums: Vec<i32>) -> i32 {
let len = nums.len();
if len <= 1 {
return 0
}
let mut l = 0 as usize;
// 步数还是得记的，因为这里我们是算的距离
// count不能跟着最远距离迭代而迭代，它需要min
let mut count = 0;
let mut last_l = 0 as usize;
for i in 0..len - 1 {
let num = i + nums[i] as usize;
l = l.max(num);
if last_l == i {
count += 1;
last_l = l;
}
}
count
}测试用例#
#[cfg(test)]
mod tests {
use super::jump;
#[test]
fn test_jump () {
assert_eq!(jump([2,3,1,1,4].to_vec()), 2);
assert_eq!(jump([2,3,0,1,4].to_vec()), 2);
assert_eq!(jump([2,1].to_vec()), 1);
assert_eq!(jump([2,3,1].to_vec()), 1);
assert_eq!(jump([1,3,2].to_vec()), 2);
assert_eq!(jump([7,0,9,6,9,6,1,7,9,0,1,2,9,0,3].to_vec()), 2)
}
}总结#
第一道题我们可以想出来，不过第二道题就比较灵活了，需要绕弯，尤其是当我们做完第一题之后直接做第二道题，很容易就进入坑里，思维还停留在第一道题里。
还是得多做啊