Golang每日一练(leetDay0022)

简介: Golang每日一练(leetDay0022)

64. 最小路径和 Minimum Path Sum


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


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


示例 1:

40a40316e332106ec04f13cb3af1b391.jpeg


输入: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))
}


输出:

7

12

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

true

false

false

true

true

false

false

true

false

true

false

false

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



输出:

[4 3 2 2]

[4 3 2 2]

[4 3 2 2]




目录
相关文章
|
5月前
|
Shell Linux 算法
Shell编程——弱数据类型的脚本语言快速入门指南
Shell编程——弱数据类型的脚本语言快速入门指南
81 0
Shell编程——弱数据类型的脚本语言快速入门指南
|
5月前
|
Go Linux Shell
Linux 终端命令之文件浏览(2) more
Linux 终端命令之文件浏览(2) more
57 0
Linux 终端命令之文件浏览(2) more
|
5月前
|
Shell 机器学习/深度学习 Linux
Linux 终端操作命令(2)内部命令
Linux 终端操作命令(2)内部命令
50 0
Linux 终端操作命令(2)内部命令
|
5月前
|
C++ 算法 存储
力扣 C++|一题多解之动态规划专题(2)
力扣 C++|一题多解之动态规划专题(2)
57 0
力扣 C++|一题多解之动态规划专题(2)
|
5月前
|
Python 索引
Python Numpy入门基础(一)创建数组
Python Numpy入门基础(一)创建数组
62 0
Python Numpy入门基础(一)创建数组
|
5月前
|
Java 容器 程序员
Java语言程序设计试卷6套
Java语言程序设计试卷6套
540 0
Java语言程序设计试卷6套
|
5月前
|
Java Go C++
Golang每日一练(leetDay0120) 反转字符串中的元音字母、前K个高频元素
Golang每日一练(leetDay0120) 反转字符串中的元音字母、前K个高频元素
63 0
Golang每日一练(leetDay0120) 反转字符串中的元音字母、前K个高频元素
|
5月前
|
Go 机器学习/深度学习 Rust
Golang每日一练(leetDay0119) 反转字符串I\II Reverse String
Golang每日一练(leetDay0119) 反转字符串I\II Reverse String
79 0
Golang每日一练(leetDay0119) 反转字符串I\II Reverse String
|
29天前
|
Go
Golang语言之管道channel快速入门篇
这篇文章是关于Go语言中管道(channel)的快速入门教程,涵盖了管道的基本使用、有缓冲和无缓冲管道的区别、管道的关闭、遍历、协程和管道的协同工作、单向通道的使用以及select多路复用的详细案例和解释。
53 4
Golang语言之管道channel快速入门篇
|
29天前
|
Go
Golang语言文件操作快速入门篇
这篇文章是关于Go语言文件操作快速入门的教程,涵盖了文件的读取、写入、复制操作以及使用标准库中的ioutil、bufio、os等包进行文件操作的详细案例。
46 4
Golang语言文件操作快速入门篇