GO 算法题常用技巧 & ACM模式模板笔记#

一、ACM 模式 I/O 模板#

很多 OJ 平台使用 ACM 模式，需要自行处理输入输出

1. fmt.Scan 基础模板#

fmt.Scan 会自动跳过空白字符（空格、换行、制表符），逐个读取数据，参数必须传指针（加 &）

1
package main
2

3
import "fmt"
4

5
func main() {
6
    var n int
7
    fmt.Scan(&n)
8

9
    for i := 0; i < n; i++ {
10
        var a, b int
11
        fmt.Scan(&a, &b)
12
        fmt.Println(a + b)
13
    }
14
    // 示例输出
15
    // 3
16
    // 7
17
    // 11
18
}

2. bufio.Scanner 快读模板（大数据量防超时必备）#

数据量大时 fmt.Scan 容易超时，使用 bufio 加速读取，按空白字符拆分输入：

1
package main
2

3
import (
4
    "bufio"
5
    "fmt"
6
    "os"
7
    "strconv"
8
)
9

10
func main() {
11
    scanner := bufio.NewScanner(os.Stdin)
12
    // 按空白字符分割（空格、换行都算作分隔符）
13
    scanner.Split(bufio.ScanWords)
14
    // 扩大缓冲区适配大数据
15
    scanner.Buffer(make([]byte, 1024*1024), 1024*1024)
16

17
    // 读取 int 的辅助函数
18
    readInt := func() int {
19
        scanner.Scan()
20
        num, _ := strconv.Atoi(scanner.Text())
21
        return num
22
    }
23

24
    n := readInt()
25
    for i := 0; i < n; i++ {
26
        a := readInt()
27
        b := readInt()
28
        fmt.Println(a + b)
29
    }
30
    // 示例输出
31
    // 3
32
    // 7
33
    // 11
34
}

二、排序技巧#

1. 基础切片排序#

sort.Ints：int 切片升序快捷排序
sort.Slice + 闭包：自定义排序规则

1
package main
2

3
import (
4
    "fmt"
5
    "sort"
6
    "math"
7
)
8

9
func main() {
10
    nums := []int{3, 1, 4, 1, 5, 9}
11

12
    // 升序（快捷写法）
13
    sort.Ints(nums)
14
    fmt.Println(nums) // [1 1 3 4 5 9]
15

16
    // 降序（自定义 less 函数）
17
    sort.Slice(nums, func(i, j int) bool {
18
        return nums[i] > nums[j]
19
    })
20
    fmt.Println(nums) // [9 5 4 3 1 1]
21

22
    // 按绝对值降序排序
23
    nums1 := []int{1, -3, 5, -9, 4, -1}
24
    sort.Slice(nums1, func(i, j int) bool {
25
        absI := math.Abs(float64(nums1[i]))
26
        absJ := math.Abs(float64(nums1[j]))
27
        return absI > absJ
28
    })
29
    fmt.Println(nums1) // [-9 5 4 -3 1 -1]
30

31
    // 按绝对值升序排序
32
    nums2 := []int{1, -3, 5, -9, 4, -1}
33
    sort.Slice(nums2, func(i, j int) bool {
34
        absI := math.Abs(float64(nums2[i]))
35
        absJ := math.Abs(float64(nums2[j]))
36
        return absI < absJ
37
    })
38
    fmt.Println(nums2) // [1 -1 -3 4 5 -9]
39
}

less 函数规则：返回 true 表示 i 元素排在 j 元素前面

2. 结构体切片排序#

1
package main
2

3
import (
4
    "fmt"
5
    "sort"
6
)
7

8
type Student struct {
9
    Name  string
10
    Score int
11
}
12

13
func main() {
14
    students := []Student{
15
        {"Alice", 85},
16
        {"Bob", 92},
17
        {"Charlie", 78},
18
    }
19

20
    // 按分数降序排列
21
    sort.Slice(students, func(i, j int) bool {
22
        return students[i].Score > students[j].Score
23
    })
24

25
    for _, s := range students {
26
        fmt.Printf("%s: %d\n", s.Name, s.Score)
27
    }
28
    // 输出
29
    // Bob: 92
30
    // Alice: 85
31
    // Charlie: 78
32
}

3. 多级排序#

示例规则：先按分数降序，分数相同则按名字字典序升序

1
package main
2

3
import (
4
    "fmt"
5
    "sort"
6
)
7

8
type Student struct {
9
    Name  string
10
    Score int
11
}
12

13
func main() {
14
    students := []Student{
15
        {"Charlie", 85},
16
        {"Alice", 92},
17
        {"Bob", 85},
18
        {"Alice", 85},
19
    }
20

21
    sort.Slice(students, func(i, j int) bool {
22
        // 第一关键字：分数降序
23
        if students[i].Score != students[j].Score {
24
            return students[i].Score > students[j].Score
25
        }
26
        // 第二关键字：名字字典序升序
27
        return students[i].Name < students[j].Name
28
    })
29

30
    for _, s := range students {
31
        fmt.Printf("%s: %d\n", s.Name, s.Score)
32
    }
33
    // 输出
34
    // Alice: 92
35
    // Alice: 85
36
    // Bob: 85
37
    // Charlie: 85
38
}

三、常用数学操作 & 溢出防范#

1. math 包常用函数#

⚠️ math 包函数基本只接收 float64 类型，int 需要手动类型转换

1
package main
2

3
import (
4
    "fmt"
5
    "math"
6
)
7

8
func main() {
9
    // 绝对值
10
    fmt.Println(math.Abs(-5.0))
11
    x := -5
12
    fmt.Println(int(math.Abs(float64(x)))) // int 类型取绝对值
13

14
    // 开方
15
    fmt.Println(math.Sqrt(9))
16

17
    // 幂运算
18
    fmt.Println(math.Pow(2, 3))
19

20
    // 向下取整、向上取整
21
    fmt.Println(int(math.Floor(3.7))) // 3
22
    fmt.Println(int(math.Ceil(3.2)))  // 4
23
}

2. 整数边界常量#

1
package main
2

3
import (
4
    "fmt"
5
    "math"
6
)
7

8
func main() {
9
    // int32 边界
10
    fmt.Println(math.MaxInt32) // 2147483647
11
    fmt.Println(math.MinInt32) // -2147483648
12

13
    // int64 边界
14
    fmt.Println(math.MaxInt64) // 9223372036854775807
15

16
    // int32 溢出演示
17
    var n int32 = math.MaxInt32
18
    n = n + 1
19
    fmt.Println(n) // -2147483648，发生溢出
20

21
    // 防溢出计算：先转为 int64 再运算
22
    var a, b int32 = 100000, 100000
23
    result := int64(a) * int64(b)
24
    fmt.Println(result) // 10000000000
25

26
    // 无穷大初始化技巧
27
    minVal := math.MaxInt32
28
    nums := []int{5, 2, 8, 1, 9}
29
    for _, v := range nums {
30
        if v < minVal {
31
            minVal = v
32
        }
33
    }
34
    fmt.Println(minVal) // 1
35
}

刷题建议：优先使用原生 int（64位系统等价 int64）降低溢出风险；大数运算显式用 int64
Go1.21+ 可使用内置 min/max 函数，不要混用 math.Max/math.Min

四、优先队列模板（container/heap）#

Go 标准库无现成优先队列，需实现 heap.Interface 接口

1. 小顶堆模板#

1
package main
2

3
import (
4
    "container/heap"
5
    "fmt"
6
)
7

8
// IntHeap 实现 heap.Interface
9
type IntHeap []int
10

11
func (h IntHeap) Len() int           { return len(h) }
12
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // 小顶堆核心规则
13
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
14

15
func (h *IntHeap) Push(x interface{}) {
16
    *h = append(*h, x.(int))
17
}
18

19
func (h *IntHeap) Pop() interface{} {
20
    old := *h
21
    n := len(old)
22
    x := old[n-1]
23
    *h = old[:n-1]
24
    return x
25
}
26

27
func main() {
28
    h := &IntHeap{}
29
    heap.Init(h)
30

31
    // 入堆
32
    heap.Push(h, 3)
33
    heap.Push(h, 1)
34
    heap.Push(h, 4)
35
    heap.Push(h, 1)
36
    heap.Push(h, 5)
37

38
    // 查看堆顶元素（最小值）
39
    fmt.Println((*h)[0]) // 1
40
    // 堆长度
41
    fmt.Println(h.Len()) // 5
42

43
    // 依次弹出元素
44
    for h.Len() > 0 {
45
        fmt.Printf("%d ", heap.Pop(h))
46
    }
47
    // 输出：1 1 3 4 5
48
    fmt.Println()
49
}

2. 大顶堆修改方法#

仅修改 Less 函数比较方向即可：

1
func (h IntHeap) Less(i, j int) bool {
2
    return h[i] > h[j] // 大顶堆核心规则
3
}

优先队列使用要点#

入堆：heap.Push(h, val)，不要直接调用 h.Push
出堆：heap.Pop(h)，不要直接调用 h.Pop
查看堆顶：(*h)[0]，直接访问底层切片首位
判空：h.Len() > 0

五、整体刷题小结#

I/O：小规模输入可用 fmt.Scan；大数据量直接用 bufio 快读避免超时
排序：优先 sort.Slice + 闭包自定义 less 函数，支持单条件/结构体/多级排序
数值计算：注意类型转换和溢出问题，大数运算用 int64
优先队列：套用 heap 模板，通过修改 Less 函数实现大小顶堆
基础工具：善用 math 包函数，注意 float64 类型限制；可用 MaxInt32 表示无穷大