Rust每日一练(Leetday0019) 跳跃游戏、合并区间、插入区间

2024-01-19 11:48| 来源: 网络整理| 查看: 265

55. 跳跃游戏 Jump Game 🌟🌟

56. 合并区间 Mmerge Intervals 🌟🌟

57. 插入区间 Insert Interval 🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练专栏

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

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 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) -> 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) -> 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] 可被视为重叠区间。

提示：

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章