268. 丢失的数字 Missing Number
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
提示：
n == nums.length1 <= n <= 10^40 <= nums[i] <= nnums中的所有数字都 独一无二
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
代码1：求和
package main import "fmt" func missingNumber(nums []int) int { n := len(nums) sum := n * (n + 1) / 2 // 求出 0 到 n 的总和 for _, num := range nums { sum -= num // 减去 nums 中所有数的总和 } return sum // 剩余的就是缺失的数字 } func main() { nums := []int{3, 0, 1} fmt.Println(missingNumber(nums)) nums = []int{0, 1} fmt.Println(missingNumber(nums)) nums = []int{9, 6, 4, 2, 3, 5, 7, 0, 1} fmt.Println(missingNumber(nums)) nums = []int{0} fmt.Println(missingNumber(nums)) }
代码2：哈希表
package main import "fmt" func missingNumber(nums []int) int { numMap := make(map[int]bool) // 定义一个 map，用于记录数组中的数字 for _, num := range nums { numMap[num] = true // 将 nums 数组中的数添加到 map 的键中 } for i := 0; i <= len(nums); i++ { if !numMap[i] { // 如果 i 不在 map 的键中，则说明该数字缺失 return i } } return -1 // 不可能到达这里，只是为了编译不报错 } func main() { nums := []int{3, 0, 1} fmt.Println(missingNumber(nums)) nums = []int{0, 1} fmt.Println(missingNumber(nums)) nums = []int{9, 6, 4, 2, 3, 5, 7, 0, 1} fmt.Println(missingNumber(nums)) nums = []int{0} fmt.Println(missingNumber(nums)) }
代码3：位运算
package main import "fmt" func missingNumber(nums []int) int { missing := len(nums) // 初始化为缺失的数字，因为 nums 是缺失一个数字的序列，所以就是 len(nums) for i, num := range nums { missing ^= i ^ num // 使用异或运算寻找缺失的数字 } return missing } func main() { nums := []int{3, 0, 1} fmt.Println(missingNumber(nums)) nums = []int{0, 1} fmt.Println(missingNumber(nums)) nums = []int{9, 6, 4, 2, 3, 5, 7, 0, 1} fmt.Println(missingNumber(nums)) nums = []int{0} fmt.Println(missingNumber(nums)) }
输出：
2
2
8
1
273. 整数转换英文表示 Integer To English Words
将非负整数 num 转换为其对应的英文表示。
示例 1：
输入：num = 123
输出："One Hundred Twenty Three"
示例 2：
输入：num = 12345
输出："Twelve Thousand Three Hundred Forty Five"
示例 3：
输入：num = 1234567
输出："One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
提示：
0 <= num <= 2^31 - 1
代码：
package main import ( "fmt" "strings" ) var belowTwenty = []string{ "", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen", } var tens = []string{ "", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety", } var thousands = []string{ "", "Thousand", "Million", "Billion", } func numberToWords(num int) string { if num == 0 { return "Zero" } res := "" i := 0 for num > 0 { if num%1000 != 0 { res = helper(num%1000) + thousands[i] + " " + res } num /= 1000 i++ } return strings.TrimSpace(res) } func helper(num int) string { if num == 0 { return "" } else if num < 20 { return belowTwenty[num] + " " } else if num < 100 { return tens[num/10] + " " + helper(num%10) } else { // num >= 100 return belowTwenty[num/100] + " Hundred " + helper(num%100) } } func main() { fmt.Println(numberToWords(123)) fmt.Println(numberToWords(12345)) fmt.Println(numberToWords(1234567)) }
输出：
One Hundred Twenty Three
Twelve Thousand Three Hundred Forty Five
One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
