Go语言LeetCode吟唱

遇到大根堆和小根堆的吟唱#

container/heap 只提供算法，堆的「大小」由 Less 方法决定：

Less(i, j) 返回 h[i] < h[j] → 小根堆（堆顶最小）
Less(i, j) 返回 h[i] > h[j] → 大根堆（堆顶最大）

小根堆#

sort.IntSlice 自带的 Less 就是 <，所以嵌入它即可得到小根堆，连 Len/Less/Swap 都不用写：

import (
    "container/heap"
    "sort"
)

type minHeap struct {
    sort.IntSlice // 自带 Len / Less(<) / Swap，天然小根堆
}

func (h *minHeap) Push(v any) {
    h.IntSlice = append(h.IntSlice, v.(int))
}

func (h *minHeap) Pop() any {
    a := h.IntSlice
    v := a[len(a)-1]
    h.IntSlice = a[:len(a)-1]
    return v
}

// 用法
func main() {
    h := &minHeap{}
    heap.Init(h)
    heap.Push(h, 3)
    heap.Push(h, 1)
    heap.Push(h, 2)
    for h.Len() > 0 {
        print(heap.Pop(h).(int)) // 输出 1 2 3
    }
}

大根堆#

复用 sort.IntSlice，只把 Less 反向重写即可：

import (
    "container/heap"
    "sort"
)

type maxHeap struct {
    sort.IntSlice
}

// 反转比较，堆顶变最大
func (h maxHeap) Less(i, j int) bool {
    return h.IntSlice[i] > h.IntSlice[j]
}

func (h *maxHeap) Push(v any) {
    h.IntSlice = append(h.IntSlice, v.(int))
}

func (h *maxHeap) Pop() any {
    a := h.IntSlice
    v := a[len(a)-1]
    h.IntSlice = a[:len(a)-1]
    return v
}

// 用法
func main() {
    h := &maxHeap{}
    heap.Init(h)
    heap.Push(h, 3)
    heap.Push(h, 1)
    heap.Push(h, 2)
    for h.Len() > 0 {
        print(heap.Pop(h).(int)) // 输出 3 2 1
    }
}

不依赖 sort.IntSlice#

如果想完全手写（比如存的不是 int，或不想引入 sort），需要实现 heap.Interface 的全部 5 个方法。下面是大根堆，把 Less 改成 < 就是小根堆：

import "container/heap"

type Heap []int

func (h Heap) Len() int            { return len(h) }
func (h Heap) Less(i, j int) bool  { return h[i] > h[j] } // > 大根堆；< 小根堆
func (h Heap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }

func (h *Heap) Push(v any) {
    *h = append(*h, v.(int))
}

func (h *Heap) Pop() any {
    old := *h
    n := len(old)
    v := old[n-1]
    *h = old[:n-1]
    return v
}

遇到哈希表的吟唱#

HashMap → 直接用 `map`#

// 声明并初始化
m := make(map[string]int)

// 常用操作
m["apple"] = 1          // 写入
v := m["apple"]         // 读取，不存在返回零值
v, ok := m["apple"]     // 安全读取，ok=false 表示不存在
delete(m, "apple")      // 删除

// 遍历
for k, v := range m {
    fmt.Println(k, v)
}

HashSet → 用 `map[T]struct{}`#

Go 没有内置 Set，惯用做法是 value 用 struct{}{}（占 0 字节）：

set := make(map[int]struct{})

// 添加
set[1] = struct{}{}
set[2] = struct{}{}

// 判断是否存在
_, ok := set[1]   // ok = true
_, ok := set[99]  // ok = false

// 删除
delete(set, 1)

也有人图省事用 map[int]bool，但 struct{} 更省内存

LeetCode 常见场景#

① 统计频次（HashMap）

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)  // 值 -> 下标
    for i, v := range nums {
        if j, ok := seen[target-v]; ok {
            return []int{j, i}
        }
        seen[v] = i
    }
    return nil
}

② 去重 / 判断是否存在（HashSet）

func containsDuplicate(nums []int) bool {
    set := make(map[int]struct{})
    for _, v := range nums {
        if _, ok := set[v]; ok {
            return true  // 已存在，有重复
        }
        set[v] = struct{}{}
    }
    return false
}

③ 字符频次（数组代替 HashMap，更快）

// 只有小写字母时，用数组比 map 快很多
freq := [26]int{}
for _, c := range "hello" {
    freq[c-'a']++
}

对比总结#

	类型	写入	查询	删除
HashMap	`map[K]V`	`m[k]=v`	`v,ok:=m[k]`	`delete(m,k)`
HashSet	`map[K]struct{}`	`s[k]=struct{}{}`	`_,ok:=s[k]`	`delete(s,k)`

查询一定要用 _, ok := m[k] 的双返回值形式，否则 key 不存在时只会返回零值，容易出 bug。