43. 字符串相乘 Multiply Strings
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
提示：
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。
代码：
package main import "fmt" func multiply(num1 string, num2 string) string { if num1 == "0" || num2 == "0" { return "0" } m, n := len(num1), len(num2) ansArr := make([]int, m+n) for i := m - 1; i >= 0; i-- { x := int(num1[i] - '0') for j := n - 1; j >= 0; j-- { y := int(num2[j] - '0') ansArr[i+j+1] += x * y } } for i := m + n - 1; i > 0; i-- { ansArr[i-1] += ansArr[i] / 10 ansArr[i] %= 10 } idx := 0 for ansArr[idx] == 0 { idx++ } ansBytes := make([]byte, m+n-idx) for i := 0; i < m+n-idx; i++ { ansBytes[i] = byte(ansArr[idx+i] + '0') } return string(ansBytes) } func main() { fmt.Println(multiply("123", "456")) }
输出：
56088
44. 通配符匹配 Wildcard Matching
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输出: false
代码：
package main import "fmt" func isMatch(s string, p string) bool { si, pi := 0, 0 sSi, pSi := -1, -1 for si < len(s) { if pi < len(p) && (s[si] == p[pi] || p[pi] == '?') { si++ pi++ } else if pi < len(p) && p[pi] == '*' { sSi = si pSi = pi pi++ } else if pSi == -1 { return false } else { sSi++ si = sSi pi = pSi + 1 } } for pi < len(p) && p[pi] == '*' { pi++ } return pi == len(p) } func main() { fmt.Println(isMatch("aa", "*")) fmt.Println(isMatch("adceb", "*a*b")) fmt.Println(isMatch("acdcd", "a*c?b")) }
输出：
true
true
false
45. 跳跃游戏 II Jump Game II
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
代码：
package main import "fmt" func jump(nums []int) int { end, maxPos, steps := 0, 0, 0 for i := 0; i < len(nums)-1; i++ { maxPos = max(maxPos, i+nums[i]) if i == end { end = maxPos steps++ } } return steps } func max(a, b int) int { if a > b { return a } return b } func main() { fmt.Println(jump([]int{2, 3, 1, 1, 4})) fmt.Println(jump([]int{2, 3, 0, 1, 4})) }
输出：
2
2
