Go-LeetCode-使用 Golang 刷 LeetCode 系列
Day 1 : Two Sum 两数之和
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现
。
你可以按任意顺序
返回答案。
示例:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]
题目大意
在数组中找到 2 个数之和等于给定值的数字,结果返回 2 个数字在数组中的下标。
解题思路
这道题最普通的解法就是使用 暴力搜索
,时间是 O(n^2)。
最优的做法是引入 map
时间复杂度是 O(n)。
顺序扫描数组,对每一个元素,在 map 中找能组合给定值的另一半数字,如果找到了,直接返回 2 个数字的下标即可。如果找不到,就把这个数字存入 map 中,等待扫到“另一半”数字的时候,再取出来返回结果。
Code
package main
import (
"fmt"
)
func main() {
numberArray := [10]int{12, 56, 1, 23, 45, 234, 5, 2, 9}
target := 10
fmt.Println(getIndex(numberArray, target))
fmt.Println(twoSum(numberArray, target))
}
// Brute-force search 暴力搜索
func getIndex(numberArray [10]int, target int) []int {
for i := 0; i < len(numberArray); i++ {
for y := i + 1; y < len(numberArray); y++ {
if numberArray[i]+numberArray[y] == target {
// fmt.Printf("target= %d , index=[%d,%d](%d,%d)\n", target, i, y, numberArray[i], numberArray[y])
return []int{i, y}
}
}
}
return nil
}
// 最优解
// 顺序扫描数组,对每一个元素,在 map 中找能组合给定值的另一半数字,
// 如果找到了,直接返回 2 个数字的下标即可。
// 如果找不到,就把这个数字存入 map 中,等待扫到“另一半”数字的时候,再取出来返回结果。
func twoSum(numberArray [10]int, target int) []int {
m := make(map[int]int)
for i := 0; i < len(numberArray); i++ {
another := target - numberArray[i]
if _, ok := m[another]; ok {
return []int{m[another], i}
}
m[numberArray[i]] = i
}
return nil
}
Day 2 : Reverse Integer 整数反转
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。注意:假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。
示例
Input: 123
Output: 321
Input: -123
Output: -321
解题思路
要求反转 10 进制数。
这一题需要注意一点,反转以后的数字要求在 [−231, 231 − 1]范围内,超过这个范围的数字都要输出 0。
Code
package main
import (
"fmt"
)
func main() {
x := 123
fmt.Println(bfsReverse(123456789))
fmt.Println(reverse(x))
}
// 解法一
func reverse(x int) int {
tmp := 0
for x != 0 {
tmp = tmp*10 + x%10 // x%10 取得最低位 加上 (上一轮取得的×10)
x = x /10
}
if tmp > 1<<31-1 || tmp < -(1<<31) {
return 0
}
return tmp
}