Go‘s 数据结构

教程

Go实现栈与队列

一、链表

单链表：

type LinkNode struct {
    val  int
    next *LinkNode   
}

循环链表：

type Ring struct {
    next, prev *Ring       // 前驱和后驱节点
    Value      interface{} // 数据
}

初始化循环链表：

// 初始化空的循环链表，前驱和后驱都指向自己，因为是循环的
func (r *Ring) init() *Ring {
    r.next = r
    r.prev = r
    return r
}

数组实现链表：【静态链表】

package main

import "fmt"

type Node struct {
    Val  string
    Next int64
}

func main() {
    var nodes [5]Node        // 五个节点的数组
    nodes[0] = Node{"A", 3}  // 下一个节点的下标为3
    nodes[1] = Node{"B", 4}  // 下一个节点的下标为4
    nodes[2] = Node{"C", 1}  // 下一个节点的下标为1
    nodes[3] = Node{"D", 2}  // 下一个节点的下标为2
    nodes[4] = Node{"E", -1} // -1表示没有下一个节点
    node := nodes[0]
    for {
        fmt.Println(node.Val)
        if node.Next == -1 {
            break
        }
        node = nodes[node.Next]
    }
}

---

二、栈和队列

go语言中，并没有栈与队列相关的数据结构，但是我们可以借助切片来实现栈与队列的操作；接下来我们一起实现栈与队列基本操作。

栈基本操作：

// 创建空栈 O(1)
stack := make([]int, 0)

// 压栈push O(1)(触发扩容则为O(n))
stack = append(stack, 10)

// 取栈顶top O(1)
top = stack[len(stack) - 1]

// 弹栈pop O(1)
stack = stack[:len(stack) - 1]

// 检查栈是否为空empty O(1)
len(stack) == 0

队列基本操作：

// 创建队列 O(1)
queue := make([]int, 0)

// 入队push（放入队尾） O(1)(触发扩容则为O(n))
queue = append(queue, 10)

// 返回队头front O(1)
front = queue[0]

// 返回队尾back O(1)
back = queue[len(queue) - 1]

// 出队pop O(1)
quque = queue[1:]

// 检查队列是否为空 O(1)
len(queue) == 0

---

三、字典

3.1 字典

Golang 语言中字典 map 的实现由哈希表实现，具体可参考标准库 runtime 下的 map.go 文件。

go map 和 c++ stl map 比对

Go 语言的map与 C++ STL 中的map（实际分为std::map和std::unordered_map）的时间复杂度差异，核心源于底层数据结构的不同。下面从实现原理出发，对比两者的核心操作复杂度。

一、底层实现差异

• Go 的map：底层是哈希表（Hash Table），采用 “拉链法”（分离链表法）解决哈希冲突。具体来说，数据被分配到多个bucket中，每个bucket存储哈希值低位相同的键值对；若冲突严重，bucket会通过链表扩展（溢出桶）。
• C++ STL 的map：分为两种：
  • std::map：底层是红黑树（一种平衡二叉搜索树），键值对按键的大小有序存储。
  • std::unordered_map：底层是哈希表，与 Go 的map实现逻辑类似（拉链法解决冲突），键值对无序存储。

二、核心操作时间复杂度对比

1、插入（Insert）

• Go 的map：

  平均时间复杂度 O(1)，最坏情况 O(n)。

  原理：通过哈希函数计算键的哈希值，定位到对应的bucket，插入键值对。若bucket未满，直接插入；若哈希冲突导致bucket溢出，需遍历链表找空位（最坏情况链表长度为 n）。

  此外，当负载因子（元素数 / 桶数）过高时，会触发扩容（rehash）：重新分配更大的桶数组，复制旧元素到新桶，此时单次操作复杂度为 O (n)，但均摊到多次插入后，平均仍为 O (1)。

• C++ std::map：

  时间复杂度 O(log n)（n 为元素个数）。

  原理：红黑树的插入需要先查找插入位置（O (log n)），再插入节点并通过旋转保持平衡（最多 O (log n) 次旋转），整体复杂度由树的高度决定（红黑树高度为 O (log n)）。

• C++ std::unordered_map：

  平均时间复杂度 O(1)，最坏情况 O(n)，与 Go 的map一致。

  原理：哈希表插入逻辑与 Go 类似，扩容时同样可能触发 O (n) 的复制操作，但均摊后为 O (1)。

2、删除（Delete）

• Go 的map：

  平均时间复杂度 O(1)，最坏情况 O(n)。

  原理：通过哈希定位bucket，遍历链表找到键并标记删除（或直接移除），最坏情况需遍历整个冲突链表（长度 n）。

• C++ std::map：

  时间复杂度 O(log n)。

  原理：红黑树中先查找节点（O (log n)），删除后通过旋转保持平衡（O (log n) 次操作）。

• C++ std::unordered_map：

  平均时间复杂度 O(1)，最坏情况 O(n)，与 Go 的map一致。

3、查找（Search）

• Go 的map：

  平均时间复杂度 O(1)，最坏情况 O(n)。

  原理：通过哈希定位bucket，遍历链表匹配键，最坏情况需遍历整个冲突链表。

• C++ std::map：

  时间复杂度 O(log n)。

  原理：红黑树的二分查找，时间与树高成正比。

• C++ std::unordered_map：

  平均时间复杂度 O(1)，最坏情况 O(n)，与 Go 的map一致。

4、遍历（Traverse）

• Go 的map：

  时间复杂度 O(n)。

  原理：需遍历所有bucket及其中的链表，访问每个元素一次（无论是否冲突，总元素数为 n）。

• C++ std::map：

  时间复杂度 O(n)。

  原理：红黑树的中序遍历，按键的顺序访问所有节点，每个节点访问一次。

• C++ std::unordered_map：

  时间复杂度 O(n)，与 Go 的map一致（遍历所有桶和元素）。

三、总结

操作	Go 的map（哈希表）	C++ std::map（红黑树）	C++ std::unordered_map（哈希表）
插入	平均 O (1)，最坏 O (n)	O(log n)	平均 O (1)，最坏 O (n)
删除	平均 O (1)，最坏 O (n)	O(log n)	平均 O (1)，最坏 O (n)
查找	平均 O (1)，最坏 O (n)	O(log n)	平均 O (1)，最坏 O (n)
遍历	O(n)	O(n)	O(n)

关键结论

• Go 的map与 C++ 的std::unordered_map是 “同类”（哈希表实现），核心操作的时间复杂度完全一致，适合对插入 / 删除 / 查找效率要求高的场景（平均 O (1)）。
• C++ 的std::map（红黑树）的优势是键值对有序，但操作复杂度为 O (log n)，适合需要按键排序的场景（如范围查询）。

在算法题中，若需 “无序映射”，Go 的map和 C++ 的std::unordered_map是等价选择；若需 “有序映射”，则 C++ 需用std::map，而 Go 需额外维护排序结构（如切片 + 排序）。

---

3.2 集合

技巧：用字典达到集合的效果

时间复杂度类似C++ std::unordered_set

声明：

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

添加元素:

set[curKey] = struct{}{}

ps: struct{}{}不占空间，所以set只占用key和自身数据结构的内存

检查存在：

if _, ok := set[curKey]; ok {
    // 元素存在
}

删除：

delete(set, curKey)

---

四、树

二叉树节点：

type TreeNode struct {
    Data  string    // 节点用来存放数据
    Left  *TreeNode // 左子树
    Right *TreeNode // 右字树
}

---

---

五、通用方法

5.1 sort

Go 语言的 sort 包提供了用于排序切片和自定义数据结构的强大工具和接口。这个包提供了几种不同的排序方法，让你能够有效地排序内置数据类型（如切片）以及通过实现 sort.Interface 来排序自定义数据类型。

1. 内置类型的排序 （但是没有现成的降序排序函数）

对于基本数据类型的切片，如 int、float64 和 string，Go 的 sort 包提供了直接的排序函数：

• 排序整数：使用 sort.Ints 函数

  a := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
  sort.Ints(a)

• 排序浮点数：使用 sort.Float64s 函数

  f := []float64{3.1, 3.14, 2.71}
  sort.Float64s(f)

• 排序字符串：使用 sort.Strings 函数

  s := []string{"Go", "Bravo", "Gopher", "Alpha"}
  sort.Strings(s)

这些函数都是对切片进行原地排序，即不创建切片的副本进行排序，而是直接在原切片上进行排序。

2. 自定义排序

如果你需要对自定义的数据结构进行排序，可以通过实现 sort.Interface 接口来实现。这个接口定义了三个方法：

• Len() 返回集合中的元素个数
• Less(i, j int) bool 报告索引 i 的元素是否应该比索引 j 的元素排在前面
• Swap(i, j int) 交换索引 i 和 j 位置的元素

通过实现这三个方法，你可以定义自定义类型的排序行为。

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

type ByAge []*Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
    people := []*Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    sort.Sort(ByAge(people))
    for _, person := range people {
        fmt.Println(person.Name, person.Age)
    }
}

在这个例子中，Person 结构体按照 Age 字段进行排序。

更简单的办法 - sort.Slice

非常推荐这个做法，可以优先用这个就好了

1. 核心语法：sort.Slice(切片名, func(i, j int) bool { return 比较规则 })
2. 排序规则：
   • 升序：切片名[i] < 切片名[j]
   • 降序：切片名[i] > 切片名[j]

示例：

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

func main() {
    people := []*Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })
    for _, person := range people {
        fmt.Println(person.Name, person.Age)
    }
}

benchmark - 对比两种方式的执行速度

package main

import (
    "sort"
    "testing"
)

// 测试数据规模：小/中/大三种场景，覆盖算法题常见数据量
const (
    smallSize  = 1000     // 小数据量
    midSize    = 100000   // 中等数据量
    largeSize  = 10000000 // 大数据量
)

// 生成随机int切片（保证每次测试的输入数据一致）
func generateSlice(size int) []int {
    slice := make([]int, size)
    for i := range slice {
        slice[i] = size - i // 逆序切片，让排序有足够的操作量
    }
    return slice
}

// -------------------------- 手动实现 sort.Interface 接口 --------------------------
type IntSlice []int

func (s IntSlice) Len() int           { return len(s) }
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }
func (s IntSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

// 手动接口排序的基准测试
func BenchmarkSortInterface_Small(b *testing.B)  { benchmarkSortInterface(b, smallSize) }
func BenchmarkSortInterface_Mid(b *testing.B)    { benchmarkSortInterface(b, midSize) }
func BenchmarkSortInterface_Large(b *testing.B)  { benchmarkSortInterface(b, largeSize) }

func benchmarkSortInterface(b *testing.B, size int) {
    for i := 0; i < b.N; i++ {
        b.StopTimer() // 停止计时：生成切片不纳入耗时
        slice := generateSlice(size)
        b.StartTimer() // 开始计时：仅统计排序耗时

        sort.Sort(IntSlice(slice))
    }
}

// -------------------------- 使用 sort.Slice 排序 --------------------------
// sort.Slice 排序的基准测试
func BenchmarkSortSlice_Small(b *testing.B)  { benchmarkSortSlice(b, smallSize) }
func BenchmarkSortSlice_Mid(b *testing.B)    { benchmarkSortSlice(b, midSize) }
func BenchmarkSortSlice_Large(b *testing.B)  { benchmarkSortSlice(b, largeSize) }

func benchmarkSortSlice(b *testing.B, size int) {
    for i := 0; i < b.N; i++ {
        b.StopTimer()
        slice := generateSlice(size)
        b.StartTimer()

        sort.Slice(slice, func(i, j int) bool {
            return slice[i] < slice[j]
        })
    }
}

❯ go test -bench=. -benchmem
goos: darwin
goarch: arm64
pkg: learning/demo
cpu: Apple M1 Pro
BenchmarkSortInterface_Small-10           296790              4407 ns/op              24 B/op          1 allocs/op
BenchmarkSortInterface_Mid-10               3013            376021 ns/op              24 B/op          1 allocs/op
BenchmarkSortInterface_Large-10               34          37278604 ns/op              24 B/op          1 allocs/op
BenchmarkSortSlice_Small-10               276732              4389 ns/op              56 B/op          2 allocs/op
BenchmarkSortSlice_Mid-10                   3123            369093 ns/op              57 B/op          2 allocs/op
BenchmarkSortSlice_Large-10                   32          33910585 ns/op              56 B/op          2 allocs/op
PASS
ok      learning/demo   37.167s

看起来性能下不错，使用sort.slice分配内存多了一倍，因为要反射构造一个新的接口变量，后续基于这个接口变量来排序，但是可以接受。

3. 性能和稳定性

• 性能：Go 的排序算法主要是快速排序，它的平均时间复杂度是 O(n log n)。在最坏的情况下，也就是当输入数组已经接近排序完成时，快速排序的性能会降低，但 Go 实现中通过引入其他算法（如堆排序）作为补充来优化这种情况。
• 稳定排序：如果你需要保持等值元素的相对顺序，可以使用 sort.Stable 方法。这确保如果 Less 方法报告元素 i 和 j 相等（即 !Less(i, j) && !Less(j, i)），它们的相对顺序不会改变。

sort.Stable(ByAge(people))

这提供了在复杂数据排序时更细粒度的控制，特别是当数据的次序有实际意义时。

---

5.2 堆（优先级队列）container/heap

在 Go 语言中，优先级队列（Priority Queue）通常通过最小堆或最大堆实现。Go 标准库的 container/heap 包提供了堆的基础操作，可以帮助我们构建自定义的优先级队列。

1. 基本原理

在 Go 中，container/heap 包实现的是最小堆（Min-Heap）。这意味着堆顶（即堆中第一个元素）总是最小的元素。如果我们需要实现最大堆（Max-Heap），可以通过对元素的比较操作进行反转来实现。

2. 使用 container/heap 实现优先级队列

要使用 container/heap 实现优先级队列，需要实现 heap.Interface 接口。该接口要求以下方法：

• Len() int：返回堆中元素的数量。
• Less(i, j int) bool：决定索引 i 的元素是否应排在索引 j 的元素之前。在最小堆中，Less(i, j) 应该返回 true 表示 i 小于 j。
• Swap(i, j int)：交换索引 i 和索引 j 的元素。
• Push(x interface{})：将元素 x 推入堆。
• Pop() interface{}：从堆中移除并返回堆顶元素。

3. 示例：最小堆优先级队列

以下是一个简单的示例，演示如何使用 container/heap 实现一个整数优先级队列（最小堆）：

package main

import (
    "container/heap"
    "fmt"
)

// IntHeap 定义了一个整数堆，实现了 heap.Interface 接口
type IntHeap []int

// Len 方法返回堆的长度
func (h *IntHeap) Len() int { return len(*h) }

// Less 方法定义元素的优先级，最小堆需要 h[i] < h[j], 最大堆需要h[i] > h[j]
func (h *IntHeap) Less(i, j int) bool { return (*h)[i] < (*h)[j] }

// Swap 方法交换两个元素
func (h *IntHeap) Swap(i, j int) { (*h)[i], (*h)[j] = (*h)[j], (*h)[i] }

// Push 方法将元素推入堆（实现堆的插入操作）
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

// Pop 方法从堆中移除并返回堆顶元素
func (h *IntHeap) Pop() interface{} {
    x := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return x
}

func main() {
    h := &IntHeap{2, 1, 5}
    heap.Init(h) // 初始化堆

    // 向堆中添加元素
    heap.Push(h, 3)
    heap.Push(h, 6)
    heap.Push(h, 4)

    // 弹出所有元素
    fmt.Printf("Priority Queue(%d):\n", h.Len())
    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
    fmt.Println()
}

heap.Push和heap.Pop都会自动重建堆，只需要记住：

• 这个接口的堆顶索引为0
• heap.Push：放到末尾，自动重建操作为，先调用接口方法type.Push()，然后当前末尾元素“上浮”
• heap.Pop：出堆顶，自动重建操作为，先首尾元素交换，再调用type.Pop()弹出末尾元素（就是交换前堆顶的值），然后当前堆顶元素“下沉”
• 所以需要注意实现type.Push()和type.Pop()，都是在末尾操作

应用：215. 数组中的第K个最大元素

---

5.3 双向链表 container/list

基本用法（核心 API 与操作）

container/list是双向链表，核心结构体是*list.List（链表对象）和*list.Element（节点对象），常用 API 如下：

1. 初始化链表

import "container/list"

// 创建一个新的双向链表
l := list.New() // 返回 *list.List

2. 新增元素（头部 / 尾部 / 指定位置） O1

// 1. 尾部添加（返回新增节点 *list.Element）
e1 := l.PushBack(100) // 链表: [100]

// 2. 头部添加
e2 := l.PushFront(200) // 链表: [200, 100]

// 3. 在指定节点前/后插入
// 在 e2（200） 后面插入 300
e3 := l.InsertAfter(300, e2) // 链表: [200, 300, 100]
// 在 e1（100） 前面插入 400
e4 := l.InsertBefore(400, e1) // 链表: [200, 300, 400, 100]

3. 删除元素 O1

// 通过节点删除（返回被删除元素的值）
val := l.Remove(e3) // 删除 300，链表变为 [200, 400, 100]
println(val.(int)) // 输出 300（注意：需类型断言，因返回值是 interface{}）

4. 遍历链表 On

// 从头部开始遍历（e.Next() 移动到下一个节点）
for e := l.Front(); e != nil; e = e.Next() {
    // 节点值通过 e.Value 获取，需类型断言（根据实际存储类型转换）
    fmt.Println(e.Value.(int)) 
}
// 输出：200、400、100

// 从尾部开始遍历（e.Prev() 移动到上一个节点）
for e := l.Back(); e != nil; e = e.Prev() {
    fmt.Println(e.Value.(int))
}
// 输出：100、400、200

5. move相关操作 O1

package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()
    e1 := l.PushBack(100)   // 链表: [100]
    e2 := l.PushFront(200)  // 链表: [200(e2), 100(e1)]
    e3 := l.InsertAfter(300, e2)  // 链表: [200(e2), 300(e3), 100(e1)]
    e4 := l.InsertBefore(400, e1) // 链表: [200(e2), 300(e3), 400(e4), 100(e1)]

    // 1. MoveToFront: 将e4移到头部
    l.MoveToFront(e4)
    printList(l) // 结果: [400(e4), 200(e2), 300(e3), 100(e1)]

    // 2. MoveToBack: 将e2移到尾部（基于上一步结果操作）
    l.MoveToBack(e2)
    printList(l) // 结果: [400(e4), 300(e3), 100(e1), 200(e2)]

    // 3. MoveBefore: 将e1移到e3前面（基于上一步结果操作）
    l.MoveBefore(e1, e3)
    printList(l) // 结果: [400(e4), 100(e1), 300(e3), 200(e2)]

    // 4. MoveAfter: 将e4移到e3后面（基于上一步结果操作）
    l.MoveAfter(e4, e3)
    printList(l) // 结果: [100(e1), 300(e3), 400(e4), 200(e2)]
}

// 辅助函数：打印链表元素
func printList(l *list.List) {
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Printf("%v ", e.Value)
    }
    fmt.Println()
}

6. 其他常用操作 O1

l.Len() // 获取链表长度（当前示例为 3）
l.Front() // 获取头节点（200 对应的 e2）
l.Back() // 获取尾节点（100 对应的 e1）

---

5.4 数学计算

以下是 Go 语言 math 包中常用的函数的总结，包括说明、使用方法以及时间复杂度：

---

1. math.Abs(x float64) float64

说明: 计算并返回 x 的绝对值。

使用:

import "math"

x := -5.3
result := math.Abs(x)  // result = 5.3

时间复杂度: O(1) – 绝对值的计算是一个简单的单步操作。

2. math.Ceil(x float64) float64

说明: 向上取整，将 x 向上舍入到最接近的整数值。

使用:

import "math"

x := 5.3
result := math.Ceil(x)  // result = 6.0

时间复杂度: O(1) – 向上取整也是一个简单的单步操作。

3. math.Floor(x float64) float64

说明: 向下取整，将 x 向下舍入到最接近的整数值。

使用:

import "math"

x := 5.7
result := math.Floor(x)  // result = 5.0

时间复杂度: O(1) – 向下取整也是一个单步操作。

4. math.Pow(x, y float64) float64

说明: 计算 x 的 y 次方。

使用:

import "math"

x := 2.0
y := 3.0
result := math.Pow(x, y)  // result = 8.0

时间复杂度: O(log y) – 使用快速幂算法实现，次方计算的时间复杂度与 y 的大小有关，通常为 O(log y)。

5. math.Sqrt(x float64) float64

说明: 计算 x 的平方根。

使用:

import "math"

x := 16.0
result := math.Sqrt(x)  // result = 4.0

时间复杂度: O(1) – 由于平方根使用高效算法实现，在硬件和算法优化下通常为常数时间。

6. math.Max(x, y float64) float64

说明: 返回 x 和 y 中的最大值。

使用:

import "math"

x := 5.0
y := 8.0
result := math.Max(x, y)  // result = 8.0

时间复杂度: O(1) – 最大值的计算仅涉及一次比较操作，因此是常数时间。

1.21版本后，内置了**max()**，可以对多个相同的数值类型，取最大值，推荐使用

7. math.Min(x, y float64) float64

说明: 返回 x 和 y 中的最小值。

使用:

import "math"

x := 5.0
y := 8.0
result := math.Min(x, y)  // result = 5.0

时间复杂度: O(1) – 最小值的计算仅涉及一次比较操作，因此是常数时间。

1.21版本后，内置了**min()**，可以对多个相同的数值类型，取最小值，推荐使用

8. 最大值和最小值（浮点的和整形的）

math.MaxInt64：int64 类型的最大值（常量，9223372036854775807）。

math.MinInt64：int64 类型的最小值（常量，-9223372036854775808）。

math.MaxInt32：int32 类型的最大值（常量，2147483647）。

math.MinInt32：int32 类型的最小值（常量，-2147483648）。

math.MaxInt：当前系统中 int 类型的最大值（取决于系统位数，32 位系统为 2147483647，64 位系统为 9223372036854775807）。

math.MinInt：当前系统中 int 类型的最小值（与 MaxInt 对应，32 位为 -2147483648，64 位为 -9223372036854775808）。

math.MaxFloat64：float64 类型能表示的最大正值，约为 1.7976931348623157e+308。

math.MinFloat64：float64 类型能表示的最小正值（大于 0 的最小数），约为 2.2250738585072014e-308。

math.MaxFloat32：float32 类型能表示的最大正值，约为 3.4028234663852886e+38。

math.MinFloat32：float32 类型能表示的最小正值（大于 0 的最小数），约为 1.401298464324817e-45。

---

5.5 go浮点数判等

---

六、排序算法（例）

• 快排

查看输出

package main

import "fmt"

func partition(arr []int, left, right int) int { // [left, right]
    pivotVal := arr[left] // 取第一个数作为枢轴的值
    for left < right {
        for left < right && pivotVal <= arr[right] {
            right--
        }
    		arr[left] = arr[right]
        for left < right && pivotVal >= arr[left] {
            left++
        }
    		arr[right] = arr[left]
    }
    arr[left] = pivotVal
    return left
}

func quicksort(arr []int, left, right int) { // [left, right]
    if left < right {
        pivot := partition(arr, left, right)
        quicksort(arr, left, pivot-1)
        quicksort(arr, pivot+1, right)
    }
}

func main() {
    arr := []int{15, 22, 55, 34, 25, 16, 7, 58, 79, 10}
    quicksort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

输出为：

[7 10 15 16 22 25 34 55 58 79]

---

易错点

1. 列表传参数使用append函数

查看案例

列表是一个指针：

package main

import "fmt"

func main() {
    arr := [5]int{1, 2, 3, 4, 5}
    sli := arr[2:5]
    sli[1] = 100
    fmt.Println(sli) // 输出为[3 100 5]
    fmt.Println(arr) // 输出为[1 2 3 100 5]
}

但是下面逻辑出错：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    ans := make([]int, 0)
    inorder(root, ans)
    return ans
}

func inorder(root *TreeNode, ans []int) {
    if root == nil {
    return
    }
    inorder(root.Left, ans)
    ans = append(ans, root.Val)
    inorder(root.Right, ans)
}

在 Go 中，slice 是通过引用传递的，但是对于 append 函数的具体行为，需要特别注意：

• 当 append 导致 slice 容量增加时，会创建一个新的底层数组，原始的 slice 引用的数组不会被改变。
• 当 append 操作未超过原 slice 的容量时，它会在原数组的基础上修改数据，并影响所有引用该数组的 slice。
• 在 inorder 中对 ans 使用了 append，这可能导致 ans 的底层数组发生变化（扩容操作），尤其是在多次 append 后超过了原始容量。

• 当 append 导致扩容时，它返回的是一个指向新底层数组的新 slice。这意味着，虽然 ans 在 inorder 函数中被修改，但是这些修改不会反映到 inorderTraversal 函数中的 ans 上，因为它们可能指向不同的底层数组。

2. 代码块问题 （变量遮蔽）

查看案例

这种内部范围的变量覆盖了返回值变量

修改方法：
1.内部范围变量重命名
2.return err

---

others

max min函数 https://blog.csdn.net/caspar_notes/article/details/132843940