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)) }
输出：
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]
