一般电商网站做集群,wordpress付费下载主题,农机网站模版,北京网站设计精选柚v米科技目录
1.前言
2. 算法题目 错误代码
3. 错误分析
4.总结#xff1a;
5.正确代码#xff1a;
6.本地测试代码#xff1a; 1.前言
今天在力扣上写算法#xff0c;遇到了一个比较奇怪的错误。由于自己使用了递归切片#xff0c;导致一开始没有看明白…目录
1.前言
2. 算法题目 错误代码
3. 错误分析
4.总结
5.正确代码
6.本地测试代码 1.前言
今天在力扣上写算法遇到了一个比较奇怪的错误。由于自己使用了递归切片导致一开始没有看明白直到在自己电脑上进行debug的时候才反应过来原因出在了哪里下面会先进行错误的分析和纠正之后进行切片底层原理的探索由于篇幅较长为了小伙伴们的阅读体验分为上下两篇进行。
下篇GO语言-切片底层探索下-CSDN博客
2. 算法题目 错误代码
力扣题目113. 路径总和 II
自己的题解:
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func pathSum(root *TreeNode, targetSum int) [][]int {var array [][]intif root nil{return array}var addPath func(node *TreeNode,sum int,path []int)addPath func(node *TreeNode,sum int,path []int){if node.Left nil node.Right nil{sum node.Valif sum targetSum{path append(path,node.Val)array append(array,path)//打印的值,下图中的标准输出fmt.Println(path,array)}return}sum node.Valpath append(path,node.Val)if node.Left ! nil{addPath(node.Left,sum,path)}if node.Right ! nil{addPath(node.Right,sum,path)}}addPath(root,0,[]int{})return array
}
运行错误示例和图示 3. 错误分析 我们可以发现在代码中 node节点左右都为空的判断中打印输出的明明是[[-6,-3,-6,-6]]但是最后输出却变成了[[-6,-3,-6,-5]]导致输出结果不符合预期。第一次看到这样的情况感觉很奇怪重新梳理一遍自己代码的逻辑没有发现错误。最后将猜测可能是切片容器的问题于是在自己本地进行debug,发现果然如此。
这其中隐藏着切片的两个底层实现
切片是引用类型会进行引用传递切片会随着元素数量的增加进行扩容改变其的底层数组的指向
在我的算法实现中最终的返回值是一个二维切片在二叉树遍历的过程中不断将路径上的节点加入 到一维切片path中。如果最后遍历的是叶子节点并且路径上的所有值的总和等于要求的值就将一维切片path直接加入到二维切片中。而问题就出现在这里我是直接将一维切片加入到二维切片中的而切片是引用类型后续对path切片的修改会影响到已加入二维切片中的切片注意这里的影响不是一定的需要加一个条件和加入二维切片中的path指向的是同一个底层数组的切片才会进行影响这也是为什么我之前110个测试能够通过而这一个无法通过的原因是有一定的概率的。
因为切片是引用类型的所以导致了已经加入二维切片中的一维切片被修改了那么为什么修改后的结果是[[-6,-3,-6,-5]]而不是[[-6,-3,-6,-5,1]]等具有其他的切片呢
这是因为切片的扩容机制导致了指向的底层数组发生了变更具体如下图
4.总结
导致我们最后输出答案是[[-6,-3,-6,-5]]的原因如下
切片是引用类型会进行引用传递切片会随着元素数量的增加进行扩容改变其的底层数组的指向
现在再看这两句话是不是清晰明确了很多。
下一篇文章将介绍关于切片的底层扩容机制
5.正确代码
我们不要将符合条件的path切片直接加入到二维切片中而是要进行copy复制防止发生引用传递
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func pathSum(root *TreeNode, targetSum int) [][]int {var array [][]intif root nil{return array}var addPath func(node *TreeNode,sum int,path []int)addPath func(node *TreeNode,sum int,path []int){if node.Left nil node.Right nil{sum node.Valif sum targetSum{path append(path, node.Val)//这里对path的值进行复制copyPath : make([]int, len(path))copy(copyPath, path)array append(array, copyPath)}return}sum node.Valpath append(path,node.Val)if node.Left ! nil{addPath(node.Left,sum,path)}if node.Right ! nil{addPath(node.Right,sum,path)}}addPath(root,0,[]int{})return array
}
通过通过 6.本地测试代码
本地测试代码的示例做了一些变更大家可以自行测试 package mainimport fmttype TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func Constructor(value int, leftNode *TreeNode, rightNode *TreeNode) *TreeNode {return TreeNode{Val: value,Left: leftNode,Right: rightNode,}
}func main() {node_61 : Constructor(-6, nil, nil)node1 : Constructor(1, nil, nil)node7 : Constructor(7, nil, nil)node_5 : Constructor(-5, node1, node7)node_62 : Constructor(-6, node_61, node_5)node11 : Constructor(11, node_61, node_5)node4 : Constructor(-6, nil, nil)node0 : Constructor(-6, node4, node11)node_3 : Constructor(-3, node_62, node0)node_63 : Constructor(-6, nil, node_3)fmt.Println(result, pathSum(node_63, -21))
}func pathSum(root *TreeNode, targetSum int) [][]int {var array [][]intif root nil {return array}var addPath func(node *TreeNode, sum int, path []int)addPath func(node *TreeNode, sum int, path []int) {if node.Left nil node.Right nil {sum node.Valif sum targetSum {//未修改哈!path append(path, node.Val)array append(array, path)fmt.Println(path, array)}return}sum node.Valpath append(path, node.Val)if node.Left ! nil {addPath(node.Left, sum, path)}if node.Right ! nil {addPath(node.Right, sum, path)}}addPath(root, 0, []int{})return array
}
