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/
|
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）暂停更 |
