目录
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 <= 3000path由英文字母，数字，'.'，'/'或'_'组成。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 <= 500word1和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/