中文:在线入门指引
http://go-tour-zh.appspot.com/basics/1
中文:文档首页
https://go-zh.org/doc/
中文首页
https://go-zh.org/
英文首页
https://golang.org/

Go 中文主页

先把这个教程看完 - Go 指南

然后就去写代码

完毕


go 语言常用的一些代码 (刷题

自定义排序

[【Go语言】基本类型排序和 slice 排序](https://itimetraveler.github.io/2016/09/07/【Go语言】基本类型排序和 slice 排序/)

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
39
40
41
42
package main

import (
"fmt"
"sort"
)

type Person struct {
Name string
Age int
}

// 按照 Person.Age 从大到小排序
type PersonSlice [] Person

func (a PersonSlice) Len() int { // 重写 Len() 方法
return len(a)
}
func (a PersonSlice) Swap(i, j int){ // 重写 Swap() 方法
a[i], a[j] = a[j], a[i]
}
func (a PersonSlice) Less(i, j int) bool { // 重写 Less() 方法, 从大到小排序
return a[j].Age < a[i].Age
}

func main() {
people := [] Person{
{"zhang san", 12},
{"li si", 30},
{"wang wu", 52},
{"zhao liu", 26},
}

fmt.Println(people)

sort.Sort(PersonSlice(people)) // 按照 Age 的逆序排序
fmt.Println(people)

sort.Sort(sort.Reverse(PersonSlice(people))) // 按照 Age 的升序排序
fmt.Println(people)

}

比较大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}

模拟C++的Vector

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
/**
* 一维
* 初始长度为空
*/
ans := make([]int, 0) // 相当于C++ vector<int> ans;
ans = append(ans, 23) // 相当于C++ ans.push_back(23);

/**
* 二维切片
* LeetCode 5280
*/
func groupThePeople(groupSizes []int) [][]int {
ans := make([][]int, 0) // 相当于C++ vector<vector<int> > ans;

cnt := make([][]int, 500) // 相当于C++ vector<int> cnt[500];

for i, v := range groupSizes {
cnt[v] = append(cnt[v], i) // 相当于C++ cnt[v].push_back(i);
if len(cnt[v]) == v {
ans = append(ans, cnt[v]) // 相当于C++ ans.push_back(cnt[v]);
cnt[v] = make([]int, 0) // 相当于C++ cnt.clear();
}
}
return ans
}

刷题板子

LCS

1
2
3
4
5
6
7
8
9
10
11
12
int dp[1005][1005];
int lcs(string word1, string word2) {
int ls1 = word1.size(), ls2 = word2.size();
for(int i = 1; i<=ls1; i++) for(int j = 1; j<=ls2; j++) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[ls1][ls2];
}

二进制枚举

1
2
3
// 双层二进制枚举
for(int j = 1; j < (1 << n); j += 1)
for(int x = j; x; x = (x - 1) & j) // 这里有个优化

并查集

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
39
40
41
42
// 并查集
type unionSet struct {
fa []int
// length_ []int
}

// func (u *unionSet) length(x int) int {
// return u.length_[u.find(x)]
// }

func NewUnionSet(n int) unionSet {
fa := make([]int, n)
for i := range fa {
fa[i] = i
}
// length_ := make([]int, n)
// for i := range length_ {
// length_[i] = 1
// }
return unionSet{fa}
}

func (u *unionSet) Find(x int) int {
if x != u.fa[x] {
u.fa[x] = u.Find(u.fa[x])
}
return u.fa[x]
}

func (u *unionSet) Join(x, y int) {
fx, fy := u.Find(x), u.Find(y)

if fx != fy {
u.fa[fy]=fx
// if u.length(fx) > u.length(fy) {
// u.fa[fy]=fx
// } else {
// u.fa[fx]=fy
// }
// u.length_[fx], u.length_[fy] = u.length(fx) + u.length(fy), u.length(fx) + u.length(fy)
}
}

自定义结构体+排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 自定义结构体+排序
type box struct {
num int
size int
}

type boxSlice []box
func(t boxSlice) Len() int {return len(t)}
func(t boxSlice) Less(i, j int) bool {return t[i].size > t[j].size}
func(t boxSlice) Swap(i, j int) {t[i], t[j] = t[j], t[i]}

// eg:
a := []box
sort.Sort(boxSlice(a))

LIS

1
2
3
4
5
6
7
8
9
10
11
12
// lis
lis := []int{}
for _, v := range arr {
p := sort.SearchInts(lis, v+1) // 二分查找 第一个 >= v+1 的位置
// v 最长上升子序列。
// v+1 最长不下降子序列。
if p < len(lis) {
lis[p] = v
} else {
lis = append(lis, v)
}
}

BIT(树状数组)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type BIT struct {
sum [100009]int
}

func lowbit(x int) int {
return x&-x
}

func (bit *BIT) up(i, v int) {
for ;i<=100000; i+=lowbit(i) {
bit.sum[i]+=v
}
}

func (bit *BIT) get(i int) int {
ans := 0
for ; i>0; i-=lowbit(i) {
ans += bit.sum[i]
}
return ans
}

离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func lisanhua(nums []int) []int {
temp := make([]int, len(nums)) // 这里的cap 要提前申请好。
copy(temp, nums)

sort.Ints(temp)
lt := 0
for i := range temp {
if i > 0 && temp[i] == temp[i-1] {
continue
}

temp[lt] = temp[i]
lt++
}

for i := range nums {
nums[i] = sort.SearchInts(temp, nums[i]) + 1
}

return nums
}