Go 切片踩坑整合
tbghg

又踩个坑,正好把之前那个整理到一块

2022/12/15

刷这道题的时候113. 路径总和 II,大体来说就是先定义了一个二维切片,dfs闭包遍历,切片path代表当前的路径,如果路径符合,`result = append(result,path)`,但是后来发现因为path的值会改变,导致result的值会跟着改变,毕竟result的底层数组装的是[]int结构体。

有什么解决办法呢?

1
2
3
4
// 原来的
result = append(result, append(path))
// 正确的(好家伙,一直没想到)
result = append(result, append([]int(nil), path...))

2022/07/09

今日刷力扣,写一个二叉树的前序遍历代码如下:

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

type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
var result []int
traversal(root, result)
return result
}

func traversal(node *TreeNode, result []int) {
if node == nil {
return
}
result = append(result, node.Val)
traversal(node.Left, result)
traversal(node.Right, result)
}

go的传递方式只有值传递一种,但切片是引用类型,在调用函数时将实际参数的地址传递到函数中,那么在函数中对参数所进行的修改,将影响到实际参数。

但是本题力扣上运行时输出结果却为[](正确输出:1 2 3),便引起了笔者的思考

首先打印result前后的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func preorderTraversal(root *TreeNode) []int {
var result []int
fmt.Printf("初始地址:%p\n", result)
traversal(root, result)
fmt.Printf("返回的地址:%p\n", result)
return result
}

func traversal(node *TreeNode, result []int) {
fmt.Printf("传入函数的地址为:%p\n", result)
if node == nil {
return
}
result = append(result, node.Val)
fmt.Println(result)
fmt.Printf("append后的地址为:%p\n", result)
traversal(node.Left, result)
traversal(node.Right, result)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
初始地址:0x0
传入函数的地址为:0x0
[1]
append后的地址为:0xc0000140a0
传入函数的地址为:0xc0000140a0
传入函数的地址为:0xc0000140a0
[1 2]
append后的地址为:0xc0000140b0
传入函数的地址为:0xc0000140b0
[1 2 3]
append后的地址为:0xc000074020
传入函数的地址为:0xc000074020
传入函数的地址为:0xc000074020
传入函数的地址为:0xc0000140b0
返回的地址:0x0

从第二行可以看出传递的确实是指针,在递归的时候result的值确实再改变,而值得我们注意的是append前后地址的变化。

当切片需要扩容时会创建新的数组,这会导致和原有切片的分离,也就是说现在改变的切片已经不再是原来的地址了,但是append时我们将它重新赋给了result,所以traversal函数内的result始终指向正确的地址,而preorderTraversal中的result仍时原来的地址,所以最终的结果为[],关于切片的底层实现详见链接

解决方法:

第一种是traversal中返回result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func preorderTraversal(root *TreeNode) []int {
var result []int
result = traversal(root, result)
return result
}

func traversal(node *TreeNode,result []int) []int {
if node == nil {
return result
}
result = append(result, node.Val)
result = traversal(node.Left, result)
result = traversal(node.Right, result)
return result
}

第二种为力扣给出的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
func preorderTraversal(root *TreeNode) (vals []int) {
var preorder func(*TreeNode)
preorder = func(node *TreeNode) {
if node == nil {
return
}
vals = append(vals, node.Val)
preorder(node.Left)
preorder(node.Right)
}
preorder(root)
return
}
 评论
评论插件加载失败
正在加载评论插件