Go-LeetCode-使用 Golang 刷 LeetCode

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 位的有符号整数，则其数值范围为 [−2^{31, 2}31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

示例

Input: 123
Output: 321

Input: -123
Output: -321

解题思路

要求反转 10 进制数。
这一题需要注意一点，反转以后的数字要求在 [−2^{31, 2}31 − 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
}