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
代码： 题目本质就是斐波那切数列
package main import "fmt" func climbStairs(n int) int { if n <= 1 { return 1 } dp := make([]int, n+1) dp[0], dp[1] = 1, 1 for i := 2; i <= n; i++ { dp[i] = dp[i-1] + dp[i-2] } return dp[n] } func main() { fmt.Println(climbStairs(2)) fmt.Println(climbStairs(3)) fmt.Println(climbStairs(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 风格绝对路径。
代码：
package main import ( "fmt" "strings" ) func simplifyPath(path string) string { dirs := strings.Split(path, "/") stack := make([]string, 0) for _, dir := range dirs { if dir == "" || dir == "." { continue } if dir == ".." { if len(stack) > 0 { stack = stack[:len(stack)-1] } } else { stack = append(stack, dir) } } return "/" + strings.Join(stack, "/") } func main() { fmt.Println(simplifyPath("/home/")) fmt.Println(simplifyPath("/../")) fmt.Println(simplifyPath("/home//foo/")) fmt.Println(simplifyPath("/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由小写英文字母组成
代码1：
package main import ( "fmt" ) func minDistance(word1 string, word2 string) int { m, n := len(word1), len(word2) dp := make([][]int, m+1) for i := 0; i <= m; i++ { dp[i] = make([]int, n+1) dp[i][0] = i } for j := 1; j <= n; j++ { dp[0][j] = j } for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if word1[i-1] == word2[j-1] { dp[i][j] = dp[i-1][j-1] } else { dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1 } } } return dp[m][n] } func min(a, b, c int) int { if a <= b && a <= c { return a } if b <= a && b <= c { return b } return c } func main() { word1 := "horse" word2 := "ros" fmt.Println(minDistance(word1, word2)) word1 = "intention" word2 = "execution" fmt.Println(minDistance(word1, word2)) }
代码2：滚动数组
package main import ( "fmt" ) func minDistance(word1 string, word2 string) int { m, n := len(word1), len(word2) dp := make([]int, n+1) for j := 1; j <= n; j++ { dp[j] = j } for i := 1; i <= m; i++ { pre := dp[0] dp[0] = i for j := 1; j <= n; j++ { temp := dp[j] if word1[i-1] == word2[j-1] { dp[j] = pre } else { dp[j] = min(pre, dp[j-1], dp[j]) + 1 } pre = temp } } return dp[n] } func min(a, b, c int) int { if a <= b && a <= c { return a } if b <= a && b <= c { return b } return c } func main() { word1 := "horse" word2 := "ros" fmt.Println(minDistance(word1, word2)) word1 = "intention" word2 = "execution" fmt.Println(minDistance(word1, word2)) }
代码3： 记忆化搜索
package main import ( "fmt" ) func minDistance(word1 string, word2 string) int { m, n := len(word1), len(word2) memo := make([][]int, m) for i := range memo { memo[i] = make([]int, n) for j := range memo[i] { memo[i][j] = -1 } } var dfs func(i, j int) int dfs = func(i, j int) int { if i+1 == 0 { return j + 1 } if j+1 == 0 { return i + 1 } if memo[i][j] != -1 { return memo[i][j] } if word1[i] == word2[j] { memo[i][j] = dfs(i-1, j-1) } else { memo[i][j] = min(dfs(i-1, j-1), dfs(i, j-1), dfs(i-1, j)) + 1 } return memo[i][j] } return dfs(m-1, n-1) } func min(a, b, c int) int { if a <= b && a <= c { return a } if b <= a && b <= c { return b } return c } func main() { word1 := "horse" word2 := "ros" fmt.Println(minDistance(word1, word2)) word1 = "intention" word2 = "execution" fmt.Println(minDistance(word1, word2)) }
输出：
3
5
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
