Go语言缺少一些数据结构，可能不是刷题的最优选择。会遇到一些麻烦。本文总结使用Go语言刷题的过程中的小技巧。
Go 数据类型
栈
1
2
3
4
5
6
7
8
9
|
// 创建栈
stack:=make([]int,0)
// push压入
stack=append(stack,10)
// pop弹出
v:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
// 检查栈空
len(stack)==0
|
队列
1
2
3
4
5
6
7
8
9
|
// 创建队列
queue:=make([]int,0)
// enqueue入队
queue=append(queue,10)
// dequeue出队
v:=queue[0]
queue=queue[1:]
// 长度0为空
len(queue)==0
|
set集合
1
2
3
4
5
6
7
8
9
|
//创建集合
type empty struct{}
set := make(map[int]empty, 0)
//插入元素
set[0] = empty{}
//删除元素
delete(set, 0)
//集合元素个数
len(set)
|
深拷贝
在回溯中经常需要添加路径等信息，当数组中添加切片的时候，需要注意对切片深拷贝
1
2
3
4
5
6
|
ans = append(ans, path) // 错误做法
// 正确做法
tmp = make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
|
Go 排序
基础排序
1
2
3
4
|
// int排序
sort.Ints([]int{})
// 字符串排序
sort.Strings([]string{})
|
自定义排序
1
2
3
4
5
6
7
8
9
|
sort.Slice(s, func(i,j int) bool {return s[i]<s[j]})
// 第一个元素正排，第二个元素倒排
sort.Slice(nums, func(i, j int) bool {
if nums[i][0] == nums[j][0] {
return nums[i][1] > nums[j][1] // 倒排
}
return nums[i][0] < nums[j][0] // 正排
})
|
Go min/max 函数
整数最大最小值
1
2
3
4
5
6
|
// int32 最大最小值
math.MaxInt32 // 实际值：1<<31-1
math.MinInt32 // 实际值：-1<<31
// int64 最大最小值（int默认是int64）
math.MaxInt64
math.MinInt64
|
简单 min/max 实现
1
2
3
4
5
6
|
func min (a, b int) int {
if a > b {
return b
}
return a
}
|
不定参数的 min/max 实现
1
2
3
4
5
6
7
8
9
10
11
|
func min (nums ...int) {
minValue = math.MaxInt64
for _, num := nums {
if num < minValue {
minValue = num
}
}
return minValue
}
// 调用
min(3, 4, 2, 7)
|
Go 字典记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
// 自定义类型 Key 作为map函数的 key
type Key struct {
i int
j int
}
func ProblemXX(a string, b string) int {
var cache = map[Key]int // 定义变量
cache = make(map[Key]int) // 初始化
}
// 使用
v, ok = cache[Key{1, 2}]
if ok {
...
} else {
...
}
// 设置新 Key
cache[Key{1, 2}] = 0
|
Go 字符串操作
Go 修改某个字符串的值
1
2
3
4
5
6
7
8
|
// 错误做法
s:= "abcd"
s[1] = "c"
// 正确做法
sArr := strings.Split(s, "") // abcd -> ["a", "b", "c", "d"]
sArr[1] = "c" // 修改 ["a", "c", "c", "d"]
s = strings.Join(sArr, "") ["a", "c", "c", "d"] -> "accd"
|
Go 字符和数字转换
1
2
3
4
|
strconv.Atoi(string) // 字符串 -> 数字
strconv.Iota(int) // 数字 -> 字符串
string(97) // int -> string
string('a') // rune -> string
|
Go 字符遍历
1
2
3
4
5
6
7
8
9
10
11
|
// 按 ascii 字符遍历, 类型是 rune, 相当于 int32
theme := "狙击 start"
for i := 0; i < len(theme); i++ {
fmt.Printf("ascii: %c %d\n", theme[i], theme[i])
}
// 按 unicode 字符遍历, 相当于 int32
for _, s := range theme {
fmt.Printf("Unicode: %c %d\n", s, s)
}
|
string.Builder
1
2
3
4
5
6
|
var sb strings.Builder
func (b *Builder) Write(p []byte) (int, error)
func (b *Builder) WriteByte(c byte) error
func (b *Builder) WriteRune(r rune) (int, error)
func (b *Builder) WriteString(s string) (int, error)
func (b *Builder) String() string
|
做题笔记
二分查找
记住：left = mid + 1; right = mid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//二分框架
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := (left + right) / 2
if target == nums[mid] {
//此处视情况插入代码：
//若返回元素索引 --> return mid
//若返回上边界 --> left = mid + 1
//若返回下边界 --> right = mid
} else if target < nums[mid] {
right = mid
} else {
left = mid + 1
}
}
return left
}
|
heap堆
官方实现的小根堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
package main
import (
"container/heap"
"fmt"
)
// An IntHeap is a min-heap of ints.
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Printf("minimum: %d\n", (*h)[0])
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
}
// Output:
// minimum: 1
// 1 2 3 5
}
|
