返回
Go Algorithm

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:]
// 检查队空
len(queue) == 0

注意：默认 s=s[0 : len(s)]，取下限不取上限，前闭后开，数学表示为：[ )

字典

基本用法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 创建
m := make(map[string]int)
// 设置kv
m["hello"] = 1
// 删除k
delete(m, "hello")
// 遍历
for k, v := range m{
    println(k, v)
}

注意

  • map 键需要可比较，不能为 slice、map、function
  • map 值都有默认值，可以直接操作默认值，如：m[age]++ ，值由 0 变为 1
  • 比较两个 map 需要遍历其中的 kv 是否相同，因为有默认值关系，所以需要检查 val 和 ok 两个值

标准库

sort

1
2
3
4
5
6
7
8

// int排序
sort.Ints([]int{})
// 字符串排序
sort.Strings([]string{})
// 自定义排序
sort.Slice(s, func(i, j int) bool {
    return s[i] < s[j] // 小的在前，升序
})

math

1
2
3
4
5
6
7
8
9

// int32 最大最小值
math.MaxInt32 // 实际值：1<<31-1
math.MinInt32 // 实际值：-1<<31
// int64 最大最小值（int默认是int64）
math.MaxInt64
math.MinInt64
// 求绝对值
num := -3.14
absValue := math.Abs(num)

copy

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 删除a[i]: 用 copy 将i+1到末尾的值前移一个单位,然后更新长度
copy(a[i:], a[i+1:])
a = a[:len(a)-1]

// make创建切片时指定具体长度，则通过索引赋值
a := make([]int, n)
a[0] = x
// make创建切片时指定长度为0，则通过append()追加元素
a := make([]int, 0)
a = append(a, x)

slices

1
2
3
4
5
6

names := []string{"alice", "Bob", "VERA"}
// 1. 翻转切片
slices.Reverse(names)
fmt.Println(names)  // [VERA Bob alice]
// 2. 找切片中最大元素值
maxV := slices.Max(candies)

rand

1
2
3
4

// 使用当前时间的纳秒作为随机种子
rand.Seed(time.Now().UnixNano())
// 生成指定范围的随机数[0-n) 左闭右开
randIdx := rand.Intn(len(nums))

strings

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 1.Join合并：使用指定的分隔符将字符串切片连接成一个单一的字符串
words := []string{"Hello", "world", "from", "Go"}
result := strings.Join(words, ",") // 输出: Hello,world,from,Go

// 2.Split拆分：用于将一个字符串按照指定的分隔符拆分成一个字符串切片
data := "apple,banana,orange,grape"
list := strings.Split(data, ",") // 输出: [apple banana orange grape]

// 3.Fields拆分：用于将一个字符串按照空格拆分一个字符串切片(连续空格视作一个空格)
strs := strings.Fields(s)

// func ReplaceAll(s, old, new string) string 
// ReplaceAll 返回字符串 s 的副本，其中所有不重叠的 old 实例都替换为 new
// 4. 清除字符串s中所有空格
s = strings.ReplaceAll(s, " ", "")

// 5. Contains包含: 判断字符串s中是否包含子串str。包含或者str为空则返回true
isContains := strings.Contains(s, str)

fmt

1
2
3
4
5
6

// 将切片转为字符串(空格分割各元素)
nums := []int{1, 11, 111}
strNums := fmt.Sprint(nums)
fmt.Printf("%T\n", nums) // []int
fmt.Printf("%T\n", strNums) // string
fmt.Println(strNums) // [1 11 111]

常用技巧

类型转换

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

s = "12345"  // s[0] 类型是byte（字符串通过索引下标访问的字符是字节型）

num := int(s[0] - '0') // 1 (byte -> int)
b := byte(num + '0') // '1' (int -> byte)

str := string(s[0]) // "1" (byte -> string)
b := byte(str) // '1' (string -> byte)

bs := []byte(s) // ['1', '2', ... , '5'] (string -> []byte)
str := string(bs) // "1" ([]byte -> string)

// 字符串 <-> 数字
num, err := strconv.Atoi() // 字符串转数字可能会失败
str := strconv.Itoa() // 数字 -> 字符串

刷题注意点

  • leetcode 中，全局变量不要当做返回值，否则刷题检查器会报错
  • 全局变量需要在函数体中重新初始化，不然变量值会在下一用例中继续使用

处理输入

fmt包

1

func Scan(a ...any) (n int, err error)
  1. 功能：扫描从标准输入读取的文本，将连续的空格分隔值存储到连续的参数中。换行符算作空格
  2. 输入：保存输入的变量，注意要传入地址
  3. 返回值：
    • 成功扫描的项目数
    • 错误信息
1

func Scanf(format string, a ...any) (n int, err error)
  1. 功能：扫描从标准输入读取的文本，将连续的空格分隔值存储到由格式确定的连续参数中。输入中的换行符必须与格式中的换行符匹配。有一个例外是%c总是扫描输入中的下一个字符，即使它是一个空格、制表符或换行符
  2. 输入：保存输入的变量，注意要传入地址
  3. 返回值：
    • 成功扫描的项目数
    • 错误信息
  4. 注意：
    • 遇到换行符会报错expected newline
    • fmt 库不能读取带空格的字符串，要想读取含空格的字符串，只能用 bufio 库中的一行一行读取的方法ReadLine()
1

func Scanln(a ...any) (n int, err error)
  1. 功能：Scanln类似于Scan，但在换行符处停止扫描，并且在最后一项之后必须有一个换行符或EOF
  2. 输入：保存输入的变量，注意要传入地址
  3. 返回值：
    • 成功扫描的项目数
    • 错误信息
  4. 注意：
    • 遇到换行符会报错expected newLine
    • fmt 库不能读取带空格的字符串，要想读取含空格的字符串，只能用 bufio 库中的一行一行读取的方法ReadLine()

总结：

  • scanf：按照给定的格式依次读取数据（包括非法数据），不能换行输入（如果要换行需要在前面加一个scanln吸收掉回车符，就像c语言中的getchar）

  • scan：比scanf高级，依次读取数据，遇到回车会忽略，可以换行输入（如果要先用了scan输入，再用scanf输入的话，需要在中间加一个scanln）

  • scanln：类似scan，但是遇到换行（回车）立马结束输入，如果要换行输入必须用多个scanln

读取一行已知长度的数组

1
2
3
4
5
6
7
8
9

length := 0
// 读取数组长度
fmt.Scan(&length)
// 初始化切片
nums := make([]int, length)
// 读入元素
for i := 0; i < len(nums); i++ {
    fmt.Scan(&nums[i])
}

读取多行已知长度的数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

nums := make([][]int, 0)
for {
    length := 0
    // 读取数组长度
    if _, err := fmt.Scan(&length); err != nil {
        return
    }
    // 初始化一行
    row := make([]int, length)
    // 读入元素
    for i := 0; i < length; i++ {
        fmt.Scan(&row[i])
    }
    // 将该一维切片追加到二维切片nums中
    nums = append(nums, row)
}

读取一行未知长度的数组， 利用 scanf 不接收换行符的性质

1
2
3
4
5
6
7
8

nums := make([]int, 0)
for {
    temp := 0
    if _, err := fmt.Scanf("%d", &temp); err != nil {
        return
    }
    nums = append(nums, temp)
}

bufio包

读取多行未知长度的数组， 利用 bufio

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

nums := make([][]int, 0)
reader := bufio.NewReader(os.Stdin)
for {
    row := make([]int, 0)
    // 按单个字符串读取一行,指定终止为换行符
    line, err := reader.ReadString('\n')
    // 判输入是否结束
    if err != nil {
        break
    }
    // 按空格拆分返回字符串切片
    strs := strings.Fields(line)
    // 遍历所有字符串
    for _, str := range strs {
        // 转为数字
        temp, _ := strconv.Atoi(str)
        row = append(row, temp)
    }
    nums = append(nums, row)
}

总结

  • 已知长度用 scan 方便，不用写格式
  • 单行未知长度用 scanf，到换行符自动结束
  • 多行未知长度用 bufio.NewReader创建一个Reader实例，指定输入源为标准输入os.Stdin，再用Reader实列的ReadString方法指定\n截止，按字符串读取一行后，若遇到EOF则跳出输入循环，若没遇到，则用 strings.Fields 自动将字符串按空格分割为多个子字符串，最后用 strconv.Atoi 逐个将子字符串转为数字
© 2021 - 2024 YI · 0 Days
共叭叭了 2186927字 · 173篇文章

Built with Hugo
Theme Stack designed by Jimmy