Golang每日一练(leetDay0022)

2023-05-27 110

版权

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

简介： Golang每日一练(leetDay0022)

64. 最小路径和 Minimum Path Sum

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]

输出：7

解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]

输出：12

提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 200

0 <= grid[i][j] <= 100

代码1：动态规划

package main
import (
  "fmt"
)
func minPathSum(grid [][]int) int {
  m, n := len(grid), len(grid[0])
  dp := make([][]int, m)
  for i := range dp {
    dp[i] = make([]int, n)
  }
  dp[0][0] = grid[0][0]
  for i := 1; i < m; i++ {
    dp[i][0] = dp[i-1][0] + grid[i][0]
  }
  for j := 1; j < n; j++ {
    dp[0][j] = dp[0][j-1] + grid[0][j]
  }
  for i := 1; i < m; i++ {
    for j := 1; j < n; j++ {
      dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    }
  }
  return dp[m-1][n-1]
}
func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}
func main() {
  grid := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}
  fmt.Println(minPathSum(grid))
  grid = [][]int{{1, 2, 3}, {4, 5, 6}}
  fmt.Println(minPathSum(grid))
}

输出：

代码2：DFS

package main
import (
  "fmt"
)
func minPathSum(grid [][]int) int {
  m, n := len(grid), len(grid[0])
  return dfs(grid, m-1, n-1)
}
func dfs(grid [][]int, i, j int) int {
  if i == 0 && j == 0 {
    return grid[0][0]
  }
  res, left := 1<<31, 1<<31
  if i > 0 {
    res = dfs(grid, i-1, j)
  }
  if j > 0 {
    left = dfs(grid, i, j-1)
  }
  if res > left {
    res = left
  }
  return res + grid[i][j]
}
func main() {
  grid := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}
  fmt.Println(minPathSum(grid))
  grid = [][]int{{1, 2, 3}, {4, 5, 6}}
  fmt.Println(minPathSum(grid))
}

写成闭包函数：

package main
import (
  "fmt"
)
func minPathSum(grid [][]int) int {
  var dfs func(i, j int) int
  dfs = func(i, j int) int {
    if i == 0 && j == 0 {
      return grid[0][0]
    }
    res, left := 1<<31, 1<<31
    if i > 0 {
      res = dfs(i-1, j)
    }
    if j > 0 {
      left = dfs(i, j-1)
    }
    if res > left {
      res = left
    }
    return res + grid[i][j]
  }
  return dfs(len(grid)-1, len(grid[0])-1)
}
func main() {
  grid := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}
  fmt.Println(minPathSum(grid))
  grid = [][]int{{1, 2, 3}, {4, 5, 6}}
  fmt.Println(minPathSum(grid))
}

65. 有效数字 Valid Number

有效数字（按顺序）可以分成以下几个部分：

一个小数或者整数

（可选）一个 'e' 或 'E' ，后面跟着一个整数

小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）

下述格式之一：

至少一位数字，后面跟着一个点 '.'

至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字

一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）

至少一位数字

部分有效数字列举如下：["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ，如果 s 是一个有效数字，请返回 true 。

示例 1：

输入：s = "0"

输出：true

示例 2：

输入：s = "e"

输出：false

示例 3：

输入：s = "."

输出：false

提示：

1 <= s.length <= 20

s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

代码：

package main
import (
  "fmt"
  "strings"
)
func isNumber(s string) bool {
  s = strings.TrimSpace(s)
  if len(s) == 0 {
    return false
  }
  hasNum := false
  hasDot := false
  hasE := false
  for i, ch := range s {
    if ch >= '0' && ch <= '9' {
      hasNum = true
    } else if ch == '.' {
      if hasDot || hasE || i == len(s)-1 || (i == 0 && len(s) == 1) {
        return false
      }
      hasDot = true
    } else if ch == 'e' || ch == 'E' {
      if hasE || !hasNum || i == len(s)-1 || i == 0 {
        return false
      }
      hasE = true
      hasNum = false
    } else if ch == '+' || ch == '-' {
      if i != 0 && (s[i-1] != 'e' && s[i-1] != 'E') {
        return false
      }
    } else {
      return false
    }
  }
  return hasNum
}
func main() {
  fmt.Println(isNumber("0"))
  fmt.Println(isNumber(" 0.1 "))
  fmt.Println(isNumber("abc"))
  fmt.Println(isNumber("1 a"))
  fmt.Println(isNumber("2e10"))
  fmt.Println(isNumber(" -90e3   "))
  fmt.Println(isNumber(" 1e"))
  fmt.Println(isNumber("e3"))
  fmt.Println(isNumber(" 6e-1"))
  fmt.Println(isNumber(" 99e2.5 "))
  fmt.Println(isNumber("53.5e93"))
  fmt.Println(isNumber(" --6 "))
  fmt.Println(isNumber("-+3"))
  fmt.Println(isNumber("95a54e53"))
}

输出：

true

false

true

false

true

false

true

false

代码2：

用正则表达式判断

package main
import (
  "fmt"
  "regexp"
)
func isNumber(s string) bool {
  pattern := "^\\s*([+-]?((\\d+\\.?)|(\\.\\d+)|(\\d+\\.\\d+)))((e|E)[+-]?\\d+)?\\s*$"
  matched, _ := regexp.MatchString(pattern, s)
  return matched
}
func main() {
  fmt.Println(isNumber("0"))
  fmt.Println(isNumber(" 0.1 "))
  fmt.Println(isNumber("abc"))
  fmt.Println(isNumber("1 a"))
  fmt.Println(isNumber("2e10"))
  fmt.Println(isNumber(" -90e3   "))
  fmt.Println(isNumber(" 1e"))
  fmt.Println(isNumber("e3"))
  fmt.Println(isNumber(" 6e-1"))
  fmt.Println(isNumber(" 99e2.5 "))
  fmt.Println(isNumber("53.5e93"))
  fmt.Println(isNumber(" --6 "))
  fmt.Println(isNumber("-+3"))
  fmt.Println(isNumber("95a54e53"))
}

66. 加一 Plus One

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]

输出：[1,2,4]

解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]

输出：[4,3,2,2]

解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]

输出：[1]

提示：

1 <= digits.length <= 100

0 <= digits[i] <= 9

代码：

package main
import (
  "fmt"
)
func plusOne(digits []int) []int {
  n := len(digits)
  for i := n - 1; i >= 0; i-- {
    if digits[i] < 9 {
      digits[i]++
      return digits
    }
    digits[i] = 0
  }
  return append([]int{1}, digits...)
}
func plusOne2(digits []int) []int {
  n := len(digits)
  for i := n - 1; i >= 0; i-- {
    if digits[i] < 9 {
      digits[i]++
      for j := i + 1; j < n; j++ {
        digits[j] = 0
      }
      return digits
    }
  }
  return append([]int{1}, make([]int, n)...)
}
func plusOne3(digits []int) []int {
  var carry int // 进位
  n := len(digits)
  digits[n-1]++
  for i := n - 1; i >= 0; i-- {
    digits[i] += carry
    carry = digits[i] / 10
    digits[i] %= 10
  }
  if carry > 0 {
    digits = append([]int{1}, digits...)
  }
  return digits
}
func main() {
  digits := []int{4, 3, 2, 1}
  fmt.Println(plusOne(digits))
  digits2 := []int{4, 3, 2, 1}
  fmt.Println(plusOne2(digits2))
  digits3 := []int{4, 3, 2, 1}
  fmt.Println(plusOne3(digits3))
}