Golang每日一练(leetDay0024) 爬楼梯、简化路径、编辑距离-阿里云开发者社区

Golang每日一练(leetDay0024) 爬楼梯、简化路径、编辑距离

2024-01-30 45

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

本文涉及的产品

资源编排，不限时长

简介： Golang每日一练(leetDay0024) 爬楼梯、简化路径、编辑距离

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))
}

输出：

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 风格绝对路径。

代码：

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

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 由小写英文字母组成

代码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))
}