论坛网站建设开源工具,求职简历免费下载模板,下载ppt模板免费,wordpress显示作者所有文章go语言切片函数参数传递append()函数扩容 给你二叉树的根节点 root 和一个整数目标和 targetSum #xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 二叉树递归go代码#xff1a;
var ans [][]int
func pathSum(root *TreeNode, targetSum int) ( [][…go语言切片函数参数传递append()函数扩容 给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 二叉树递归go代码
var ans [][]int
func pathSum(root *TreeNode, targetSum int) ( [][]int) {ans : make([][]int, 0) path : []int{}dfs(root, targetSum,path)return ans
}
func dfs(node *TreeNode, left int,path []int) {if node nil {return}left - node.Valpath append(path, node.Val)if node.Left nil node.Right nil left 0 {ans append(ans, append([]int(nil), path...))//在二维切片中添加一维切片return}dfs(node.Left, left,path)dfs(node.Right, left,path)
}我的疑惑由这道题的代码产生可以看到在dfs递归函数中使用了参数path切片作为变量而学过Go的都知道切片slice是引用类型那么在函数传递时是引用传递吗。 可以知道path记录的是目前遍历过的数据而我的疑惑就是对切片path一直添加了数据那么为什么作为参数传进path后在下层递归函数中的修改不会影响到上层path以下是我查阅许多资料的解释。
1.Go中切片的结构体 如图所示切片结构体包含了三部分第一部分是指向底层数组的指针其次是切片的大小len和切片的容量cap。
2.切片的扩容机制
切片的容量(cap)表示切片可以使用的底层数组的最大长度。当切片的长度(len)超过了容量时切片就会自动扩容即分配一个更大的底层数组并将原有的数据复制过去。这个过程是由append函数完成的我们不需要手动操作。 根据Go语言源码中的注释切片扩容的规则如下 如果原始容量小于1024则新容量是原始容量的2倍 如果原始容量大于等于1024则新容量是原始容量的1.25倍 如果连续扩容5次且没有触发上述两种情况则新容量是原始容量的1.5倍 如果分配失败则触发内存溢出。 **切片在函数内部进行扩容或缩容操作时会导致切片指向一个新的底层数组此时在函数内部和外部就不再共享同一个底层数组了。**因此当追加超出原本容量时再改变切片内容后对原来的数组是没有影响的
3.Go中的append函数 如上图可以看到如果进行append后
切片没有进行扩容那么会直接添加或修改切片指向底层数组中后一位的值故底层数组会受到改变而如果进行扩容则会导致切片指向一个新的底层数组对原来的数组是没有影响的
4.Go函数传参只有值传递一种方式传地址必须加上*——其实也是传地址变量的值
看过有些博客说Go中切片是传地址但其实这是错误的 Go官方文档声明Go中函数传参只有传值传地址必须加上*这其实也是传地址变量的值
再回到切片作为函数参数的问题上因为Go里面函数传参只有值传递一种方式所以当切片作为参数时其实也是切片的拷贝但是在拷贝的切片中其包含的指针成员变量的值是一样的也就是说它们指向的底层数组数据源是一样因此在调用函数内修改形参能影响实参。
通常我们把在传值拷贝过程中修改形参能直接修改实参的数据类型称为引用类型。 Go语言中所有的传参都是值传递传值都是一个副本一个拷贝。
因为拷贝的内容有时候是非引用类型int、string、struct等这些这样就在函数中就无法修改原内容数据有的是引用类型指针、map、slice、chan等这些这样就可以修改原内容数据。
这里要注意的是引用类型和传引用是两个概念。
总结
slice切片或者array数组作为函数参数传递的时候本质是传值而不是传地址。因为slice依赖其底层的array修改slice本质是修改array而array又是有大小限制当超过slice的容量即数组越界的时候需要通过动态规划的方式创建一个新的数组块。把原有的数据复制到新数组这个新的array则为slice新的底层依赖。
传值的过程复制一个新的切片这个切片也指向原始变量的底层数组。函数中无论是直接修改切片还是append创建新的切片都是基于共享切片底层数组的情况作为基础最外面的原始切片是否改变取决于函数内的操作和切片本身容量是否修改了底层数组。
如果要修改切片的值那么一定对底层数组做了修改为影响到函数外的切片如果是append操作则要看切片是否扩容 切片没有进行扩容那么会直接添加或修改切片指向底层数组中后一位的值故底层数组会受到改变函数外切片改变而如果进行扩容则会导致切片指向一个新的底层数组一切修改都对函数外的原切片无影响 .
当然如果为了修改原始变量可以指定参数的类型为指针类型。传递的就是slice的内存地址。函数内的操作都是根据内存地址找到变量本身。
递归代码分析
func dfs(node *TreeNode, left int,path []int) {if node nil {return}left - node.Valpath append(path, node.Val)if node.Left nil node.Right nil left 0 {ans append(ans, append([]int(nil), path...))//在二维切片中添加一维切片return}dfs(node.Left, left,path)dfs(node.Right, left,path)
}故在该递归函数dfs中我们首先要知道每次递归都是从左到右递归完一条路径才会返回故第一次递归时就会导致path达到叶子节点。且由path代表路径的定义易知path的长度代表着当前遍历结点的深度。 在每一次传递的参数path都是传的切片值而不是path的地址故都是不同的切片值只是指向的底层数组一样且每次在函数内部进行append时可能扩容也可能不扩容
如果append后导致path扩容会导致切片指向一个新的底层数组此时在函数内部path和外部path就不再共享同一个底层数组了因此不会影响上层递归函数的path如果append后没有导致path扩容那么会直接添加或修改切片指向底层数组中后一位的值 如果是第一次遍历到当前深度那么就会在底层数组中添加值那么直接添加并判断当前结点有无子树若没有子树则加入ans中如果已经遍历过当前深度那么应该修改底层数组的切片后一位的值这样确实会影响path的底层数组但对所求的答案ans没有影响因为修改之前的path路径已经在之前的递归中添加进了ans中对之后的递归中的path也没有影响因为之后的path在遍历到当前深度进行append时也会修改该深度的path值
