55. 跳跃游戏 Jump Game
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 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 <= 3 * 10^40 <= nums[i] <= 10^5
代码1：
贪心算法，记录每个位置能跳到的最远距离，如果当前位置已经超过了当前能跳到的最远距离，说明无法到达终点，返回 false。
fn can_jump(nums: Vec<i32>) -> bool { let n = nums.len(); let mut max_pos = 0; for i in 0..n { if i > max_pos { return false; } max_pos = std::cmp::max(max_pos, i + nums[i] as usize); } true } fn main() { let nums = vec![2, 3, 1, 1, 4]; println!("{}", can_jump(nums)); let nums2 = vec![3, 2, 1, 0, 4]; println!("{}", can_jump(nums2)); }
代码2：
回溯算法，从第一个位置开始，依次尝试跳到后面的每一个位置，如果遇到无法跳到的位置，则回溯到上一个位置，直到跳到终点或无法回溯为止。
fn can_jump(nums: Vec<i32>) -> bool { backtrack(&nums, 0) } fn backtrack(nums: &[i32], pos: usize) -> bool { if pos == nums.len() - 1 { return true; } let furthest_jump = usize::min(pos + nums[pos] as usize, nums.len() - 1); for next_pos in (pos + 1..=furthest_jump).rev() { if backtrack(nums, next_pos) { return true; } } false } fn main() { let nums = vec![2, 3, 1, 1, 4]; println!("{}", can_jump(nums)); let nums2 = vec![3, 2, 1, 0, 4]; println!("{}", can_jump(nums2)); }
代码3：
动态规划，定义状态 dp[i] 表示能否从起点跳到第 i 个位置。转移方程为 dp[i] = dp[j] && j + nums[j] >= i，其中 j 为能够跳到的位置。
fn can_jump(nums: Vec<i32>) -> bool { let n = nums.len(); let mut dp = vec![false; n]; dp[0] = true; for i in 1..n { for j in 0..i { if dp[j] && j + nums[j] as usize >= i { dp[i] = true; break; } } } dp[n - 1] } fn main() { let nums = vec![2, 3, 1, 1, 4]; println!("{}", can_jump(nums)); let nums2 = vec![3, 2, 1, 0, 4]; println!("{}", can_jump(nums2)); }
代码4：
反向贪心算法，从终点开始向前遍历，记录能够跳到终点的最小位置，如果当前位置能够跳到这个最小位置，则更新最小位置，最后判断起点是否能够跳到这个最小位置即可。
fn can_jump(nums: Vec<i32>) -> bool { let n = nums.len(); let mut last_pos = n - 1; for i in (0..n - 1).rev() { if i + nums[i] as usize >= last_pos { last_pos = i; } } last_pos == 0 } fn main() { let nums = vec![2, 3, 1, 1, 4]; println!("{}", can_jump(nums)); let nums2 = vec![3, 2, 1, 0, 4]; println!("{}", can_jump(nums2)); }
输出：
true
false
56. 合并区间 Mmerge Intervals
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 10^4intervals[i].length == 20 <= starti <= endi <= 10^4
代码1：
排序 + 双指针 首先将区间按照起始位置从小到大排序，然后使用双指针对区间进行合并。具体来说，定义左右指针 left 和 right，初始时 left 指向第一个区间的起始位置，right 指向第一个区间的结束位置。然后依次遍历每个区间，如果当前区间的起始位置小于等于 right，则将 right 更新为当前区间的结束位置，否则将当前区间的起始位置和结束位置作为一个新区间加入结果集，并将左右指针更新为当前区间的起始位置和结束位置。最后将最后一个区间加入结果集即可。
fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> { intervals.sort_by_key(|v| v[0]); let mut res = Vec::new(); let mut left = intervals[0][0]; let mut right = intervals[0][1]; for i in 1..intervals.len() { if intervals[i][0] <= right { right = right.max(intervals[i][1]); } else { res.push(vec![left, right]); left = intervals[i][0]; right = intervals[i][1]; } } res.push(vec![left, right]); res } fn main() { let intervals = vec![vec![1, 3], vec![2, 6], vec![8, 10], vec![15, 18]]; println!("{:?}", merge(intervals)); let intervals = vec![vec![1, 4], vec![4, 5]]; println!("{:?}", merge(intervals)); }
代码2：
排序 + 栈 首先将区间按照起始位置从小到大排序，然后使用栈对区间进行合并。具体来说，依次遍历每个区间，如果当前区间的起始位置小于等于栈顶区间的结束位置，则将栈顶区间的结束位置更新为当前区间的结束位置，否则将当前区间加入栈中。最后将栈中所有区间加入结果集即可。
fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> { // 按照区间的起始位置排序 let mut intervals = intervals; intervals.sort_by_key(|interval| interval[0]); let mut stack: Vec<Vec<i32>> = Vec::new(); for interval in intervals { if stack.is_empty() || interval[0] > stack.last().unwrap()[1] { // 如果当前区间和栈顶区间不重叠，直接入栈 stack.push(interval); } else { // 否则，进行区间合并 let last = stack.last_mut().unwrap(); last[1] = last[1].max(interval[1]); } } stack } fn main() { let intervals = vec![vec![1, 3], vec![2, 6], vec![8, 10], vec![15, 18]]; println!("{:?}", merge(intervals)); let intervals = vec![vec![1, 4], vec![4, 5]]; println!("{:?}", merge(intervals)); }
代码3：
排序 + 遍历 首先将区间按照起始位置从小到大排序，然后依次遍历每个区间，如果当前区间的起始位置小于等于结果集中最后一个区间的结束位置，则将结果集中最后一个区间的结束位置更新为当前区间的结束位置，否则将当前区间加入结果集。最后输出结果集即可。
fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> { intervals.sort_by_key(|interval| interval[0]); let mut res: Vec<Vec<i32>> = Vec::new(); for interval in intervals { if res.is_empty() || interval[0] > res[res.len()-1][1] { res.push(interval); } else { let last = res.last_mut().unwrap(); last[1] = std::cmp::max(last[1], interval[1]); } } return res; } fn main() { let intervals = vec![vec![1, 3], vec![2, 6], vec![8, 10], vec![15, 18]]; println!("{:?}", merge(intervals)); let intervals = vec![vec![1, 4], vec![4, 5]]; println!("{:?}", merge(intervals)); }
输出：
[[1, 6], [8, 10], [15, 18]]
[[1, 5]]
57. 插入区间 Insert Interval
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
示例 3：
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
示例 4：
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
示例 5：
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]
提示：
0 <= intervals.length <= 10^4intervals[i].length == 20 <= intervals[i][0] <= intervals[i][1] <= 10^5intervals根据intervals[i][0]按 升序 排列newInterval.length == 20 <= newInterval[0] <= newInterval[1] <= 10^5
代码1：双指针
由于区间列表是按照起始端点排序的，因此可以使用双指针的方法，分别找到新区间需要插入的位置和合并重叠的区间。
fn insert(intervals: Vec<Vec<i32>>, mut new_interval: Vec<i32>) -> Vec<Vec<i32>> { let n = intervals.len(); let mut res: Vec<Vec<i32>> = Vec::new(); // 找到新区间需要插入的位置 let mut i = 0; while i < n && intervals[i][1] < new_interval[0] { res.push(intervals[i].clone()); i += 1; } // 合并重叠的区间 while i < n && intervals[i][0] <= new_interval[1] { new_interval[0] = std::cmp::min(intervals[i][0], new_interval[0]); new_interval[1] = std::cmp::max(intervals[i][1], new_interval[1]); i += 1; } res.push(new_interval); // 合并剩余的区间并再次合并重叠的区间 while i < n { res.push(intervals[i].clone()); i += 1; } // 再次合并重叠的区间 let mut i = 1; while i < res.len() { if res[i][0] <= res[i-1][1] { res[i-1][1] = std::cmp::max(res[i][1], res[i-1][1]); res.remove(i); } else { i += 1; } } return res; } fn main() { let intervals1 = vec![vec![1, 3], vec![6, 9]]; let new_interval1 = vec![2, 5]; let merged1 = insert(intervals1, new_interval1); println!("{:?}", merged1); // 输出 [[1,5],[6,9]] let intervals2 = vec![vec![1, 2], vec![3, 5], vec![6, 7], vec![8, 10], vec![12, 16]]; let new_interval2 = vec![4, 8]; let merged2 = insert(intervals2, new_interval2); println!("{:?}", merged2); // 输出 [[1,2],[3,10],[12,16]] let intervals3: Vec<Vec<i32>> = vec![]; let new_interval3 = vec![5, 7]; let merged3 = insert(intervals3, new_interval3); println!("{:?}", merged3); // 输出 [[5,7]] let intervals4: Vec<Vec<i32>> = vec![vec![1, 5]]; let new_interval4 = vec![2, 3]; let merged4 = insert(intervals4, new_interval4); println!("{:?}", merged4); // 输出 [[1,5]] let intervals5: Vec<Vec<i32>> = vec![vec![1, 5]]; let new_interval5 = vec![2, 7]; let merged5 = insert(intervals5, new_interval5); println!("{:?}", merged5); // 输出 [[1,7]] }
代码2：暴力插入
遍历区间列表，找到新区间需要插入的位置，然后插入新区间。再遍历一遍区间列表，合并重叠的区间。
fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> { let mut res: Vec<Vec<i32>> = vec![]; let mut start = new_interval[0]; let mut end = new_interval[1]; let mut flag = false; for inter in intervals { if inter[1] < start { res.push(inter); } else if inter[0] > end { if !flag { res.push(vec![start, end]); flag = true; } res.push(inter); } else { start = std::cmp::min(start, inter[0]); end = std::cmp::max(end, inter[1]); } } if !flag { res.push(vec![start, end]); } return res; } fn main() { let intervals1 = vec![vec![1, 3], vec![6, 9]]; let new_interval1 = vec![2, 5]; let merged1 = insert(intervals1, new_interval1); println!("{:?}", merged1); // 输出 [[1,5],[6,9]] let intervals2 = vec![vec![1, 2], vec![3, 5], vec![6, 7], vec![8, 10], vec![12, 16]]; let new_interval2 = vec![4, 8]; let merged2 = insert(intervals2, new_interval2); println!("{:?}", merged2); // 输出 [[1,2],[3,10],[12,16]] let intervals3: Vec<Vec<i32>> = vec![]; let new_interval3 = vec![5, 7]; let merged3 = insert(intervals3, new_interval3); println!("{:?}", merged3); // 输出 [[5,7]] let intervals4: Vec<Vec<i32>> = vec![vec![1, 5]]; let new_interval4 = vec![2, 3]; let merged4 = insert(intervals4, new_interval4); println!("{:?}", merged4); // 输出 [[1,5]] let intervals5: Vec<Vec<i32>> = vec![vec![1, 5]]; let new_interval5 = vec![2, 7]; let merged5 = insert(intervals5, new_interval5); println!("{:?}", merged5); // 输出 [[1,7]] }
输出：
[[1, 5], [6, 9]]
[[1, 2], [3, 10], [12, 16]]
[[5, 7]]
[[1, 5]]
[[1, 7]]
🌟每日一练刷题专栏🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
