SkyzcStack|正材棧區

  • 首页
  • 文章归档
  • 默认分类
  • 关于页面

  • 搜索
Docker Algorithm Ag Golang LeetCode Golnag 传感器 ESP8266 Resume SkyzcYou 软考 C/C++ Interview Python 面试 Java Eclipse IDE Android MySQL Ubuntu Linux

Go-LeetCode-使用 Golang 刷 LeetCode

发表于 2021-07-30 | 分类于 Notes | 0 | 阅读次数 2052

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
}


  • 本文作者: SkyzcYou
  • 本文链接: /archives/go-leetcode--shi-yong-golangshua-leetcode
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# Docker # Algorithm # Ag # Golang # LeetCode # Golnag # 传感器 # ESP8266 # Resume # SkyzcYou # 软考 # C/C++ # Interview # Python # 面试 # Java # Eclipse # IDE # Android # MySQL # Ubuntu # Linux
Learn Go Programming - Golang Tutorial for Beginners
  • 文章目录
  • 站点概览
SkyzcYou

SkyzcYou

27 日志
4 分类
22 标签
RSS
Github E-mail
Creative Commons
© 2022 SkyzcYou
由 Halo 强力驱动
|
主题 - NexT.Gemini v5.1.4

黔ICP备17002491号 - 2