目录
70. 爬楼梯 Climbing Stairs 🌟
71. 简化路径 Simplify Path 🌟🌟
72. 编辑距离 Edit Distance 🌟🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
70. 爬楼梯 Climbing Stairs
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2 输出:2 解释:有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2:
输入:n = 3 输出:3 解释:有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示:
1 <= n <= 45
代码: 题目本质就是斐波那切数列
fn climb_stairs(n: i32) -> i32 {
if n <= 1 {
return 1;
}
let mut dp = vec![0; n as usize + 1];
dp[0] = 1;
dp[1] = 1;
for i in 2..=n as usize {
dp[i] = dp[i - 1] + dp[i - 2];
}
dp[n as usize]
}
fn main() {
println!("{}", climb_stairs(2));
println!("{}", climb_stairs(3));
println!("{}", climb_stairs(5));
}
输出:
2
3
8
71. 简化路径 Simplify Path
给你一个字符串 path
,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/'
开头),请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中,一个点(.
)表示当前目录本身;此外,两个点 (..
) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,'//'
)都被视为单个斜杠 '/'
。 对于此问题,任何其他格式的点(例如,'...'
)均被视为文件/目录名称。
请注意,返回的 规范路径 必须遵循下述格式:
- 始终以斜杠
'/'
开头。 - 两个目录名之间必须只有一个斜杠
'/'
。 - 最后一个目录名(如果存在)不能 以
'/'
结尾。 - 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含
'.'
或'..'
)。
返回简化后得到的 规范路径 。
示例 1:
输入:path = "/home/" 输出:"/home" 解释:注意,最后一个目录名后面没有斜杠。
示例 2:
输入:path = "/../" 输出:"/" 解释:从根目录向上一级是不可行的,因为根目录是你可以到达的最高级。
示例 3:
输入:path = "/home//foo/" 输出:"/home/foo" 解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。
示例 4:
输入:path = "/a/./b/../../c/" 输出:"/c"
提示:
1 <= path.length <= 3000
-
path
由英文字母,数字,'.'
,'/'
或'_'
组成。 -
path
是一个有效的 Unix 风格绝对路径。
代码:
fn simplify_path(path: &str) -> String {
let dirs = path.split("/");
let mut stack = Vec::new();
for dir in dirs {
match dir {
"" | "." => continue,
".." => {
if stack.len() > 0 {
stack.pop();
}
},
_ => stack.push(dir),
}
}
let mut res = String::from("/");
res.push_str(&stack.join("/"));
res
}
fn main() {
println!("{}", simplify_path("/home/"));
println!("{}", simplify_path("/../"));
println!("{}", simplify_path("/home//foo/"));
println!("{}", simplify_path("/a/./b/../../c/"));
}
输出:
/home
/
/home/foo
/c
72. 编辑距离 Edit Distance
给你两个单词 word1
和 word2
, 请返回将 word1
转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
输入:word1 = "horse", word2 = "ros" 输出:3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2:
输入:word1 = "intention", word2 = "execution" 输出:5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
提示:
0 <= word1.length, word2.length <= 500
-
word1
和word2
由小写英文字母组成
代码:
fn min_distance(word1: String, word2: String) -> i32 {
let m = word1.len();
let n = word2.len();
let mut dp = vec![0; n + 1];
let word1 = word1.as_bytes();
let word2 = word2.as_bytes();
// 初始化第一行
for j in 1..=n {
dp[j] = j as i32;
}
for i in 1..=m {
let mut pre = dp[0];
dp[0] = i as i32;
for j in 1..=n {
let temp = dp[j];
if word1[i - 1] == word2[j - 1] {
dp[j] = pre;
} else {
dp[j] = pre.min(dp[j - 1]).min(dp[j]) + 1;
}
pre = temp;
}
}
dp[n]
}
fn main() {
println!("{}", min_distance("horse".to_string(), "ros".to_string()));
println!("{}", min_distance("intention".to_string(), "execution".to_string()));
}
输出:
3
5
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页: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)暂停更 |
|
文章来源:https://www.toymoban.com/news/detail-535539.html |
Java每日一练 专栏(2023.3.11~2023.5.18)暂停更文章来源地址https://www.toymoban.com/news/detail-535539.html |
到了这里,关于Rust每日一练(Leetday0024) 爬楼梯、简化路径、编辑距离的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!