GO语言-切片底层探索(上)

目录

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,发现果然如此。

这其中隐藏着切片的两个底层实现:

  1. 切片是引用类型,会进行引用传递;
  2. 切片会随着元素数量的增加,进行扩容,改变其的底层数组的指向;

在我的算法实现中最终的返回值是一个二维切片,在二叉树遍历的过程中不断将路径上的节点加入
到一维切片path中。如果最后遍历的是叶子节点并且路径上的所有值的总和等于要求的值,就将一维切片path直接加入到二维切片中。而问题就出现在这里,我是直接将一维切片加入到二维切片中的,而切片是引用类型,后续对path切片的修改会影响到已加入二维切片中的切片(注意:这里的影响不是一定的,需要加一个条件,和加入二维切片中的path指向的是同一个底层数组的切片才会进行影响),这也是为什么我之前110个测试能够通过,而这一个无法通过的原因,是有一定的概率的。

因为切片是引用类型的,所以导致了已经加入二维切片中的一维切片被修改了,那么,为什么修改后的结果是[[-6,-3,-6,-5]]而不是[[-6,-3,-6,-5,1]]等具有其他的切片呢?

这是因为切片的扩容机制,导致了指向的底层数组发生了变更,具体如下图:

4.总结:

导致我们最后输出答案是[[-6,-3,-6,-5]]的原因如下:

  1. 切片是引用类型,会进行引用传递;
  2. 切片会随着元素数量的增加,进行扩容,改变其的底层数组的指向;

现在再看这两句话,是不是清晰明确了很多。

下一篇文章将介绍关于切片的底层扩容机制

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 "fmt"type 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
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/274144.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于java+springboot+mybatis+laiyu实现学科竞赛管理系统

基于javaspringbootmybatislaiyu实现学科竞赛管理系统 博主介绍:5年java开发经验,专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末获…

深圳恒峰智慧|便携式森林消防泵:守护森林安全的必备装备

随着人类对自然资源的不断开发和利用,森林面积逐渐减少,森林火灾的发生率也在逐年上升。为了保护森林资源,预防和减少森林火灾的发生,便携式森林消防泵成为了守护森林安全的重要装备。 一、便携式森林消防泵的特点 1. 轻便易携带&…

Python 单元测试

本篇为Python的单元测试的方法及示例 目录 概念 结果 示例 对函数进行测试 创建函数文件 创建测试文件 测试结果 对类进行测试 创建待测试类 创建测试文件 文档测试 创建函数 进行测试 总结 概念 用来对一个函数、一个类或者一个模块来进行正确性校验工作 结果 …

加密 / MD5算法 /盐值

目录 加密的介绍 MD5算法 盐值 加密的介绍 加密介绍:在MySQL数据库中, 我们常常需要对密码, 身份证号, 手机号等敏感信息进行加密, 以保证数据的安全性。 如果使用明文存储, 当黑客入侵了数据库时, 就可以轻松获取到用户的相关信息, 从而对用户或者企业造成信息…

算法——哈希王

242.有效的字母异位词 力扣题目链接(opens new window) 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 示例 1: 输入: s "anagram", t "nagaram" 输出: true 示例 2: 输入: s "rat", t "car&qu…

【Consul】注册Consul服务时报错404

【Consul】注册Consul服务时报错404 大家好 我是寸铁👊 总结了一篇golang注册Consul服务时报错404✨ 喜欢的小伙伴可以点点关注 💝 问题背景 今天寸铁想注册一个服务到Consul服务中心,却发现报错了,错误码是404,下面和…

react中的useEffect的使用

目录 React的useEffect深度解析与实战应用 一、useEffect的基本使用 二、useEffect的依赖项数组 三、避免无限循环 四、使用清空函数进行清理 React的useEffect深度解析与实战应用 React Hooks 是 React 16.8 版本引入的新特性,它允许我们在不编写 class 的情况…

SQLiteC/C++接口详细介绍-sqlite3类(一)

上一篇:SQLiteC/C接口简介 下一篇:SQLiteC/C接口详细介绍(二) 引言: SQLite C/C 数据库接口是一个流行的SQLite库使用形式,它允许开发者在C和C代码中嵌入 SQLite 基本功能的解决方案。通过 SQLite C/C 数据…

Elasticsearch 通过索引阻塞实现数据保护深入解析

目录 前言 1、索引阻塞的种类 2、什么时候使用阻塞? 场景1:进行系统维护场景。 场景2:保护数据不被随意更改场景。 场景3:优化资源使用的场景。 场景4:遵守安全规则场景。 3、添加索引阻塞API 4、解除设置 AP…

吴恩达机器学习笔记 十八 制定一个性能评估标准 学习曲线 高偏差 高方差

一个模型的好坏的评估基准可以从下面几个方面考虑: 1.考虑人类在这个问题上的表现 2.对比竞争算法的表现 3.根据经验猜测 判断是高偏差还是高方差 训练样本数量越多,越难完美地拟合每个样本,因此 J_train 会逐渐增大一点点,但泛…

原创检测工具,高效了解文章质量

原创检测工具,高效了解文章质量!想要知道一篇文章的质量怎么样,我们可以通过了解文章的原创度高低来分析,那么文章的原创度高低我们又是如何来知晓的呢?那当然是用原创检测工具去查询出来的。虽然我们可以把文章内容放…

20240309web前端_第一周作业_豆瓣电影

作业四&#xff1a;豆瓣电影 成果展示&#xff1a; 完整代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0…

Word转PDF保持图片原有清晰度

目录 1、需要的软件 2、配置Acrobat PDFMaker 3、配置Acrobat Distiller 4、更改Acrobat PDFMaker中的首选项 5、将word转换成pdf 1、需要的软件 利用Adobe Acrobat DC工具。 打开word&#xff0c;选择Acrobat的插件&#xff0c;选择首选项。 如果没有出现Acrobat插件也…

C++的类与对象(三):构造函数、析构函数、对象的销毁顺序

目录 类的6个默认成员函数 构造函数 语法 特性 析构函数 特性 对象的销毁顺序​​​​​​​​​​​​​​ 类的6个默认成员函数 问题&#xff1a;一个什么成员都没的类叫做空类&#xff0c;空类中真的什么都没有吗&#xff1f; 基本概念&#xff1a;任何类在什么都不…

2024年最便宜的阿里云服务器购买图文教程,2核2G61元,2核4G99元

2024年&#xff0c;阿里云推出了多款价格非常便宜的云服务器和轻量应用服务器&#xff0c;其中轻量应用服务器2核2G3M带宽50G系统盘只要61元/1年&#xff0c;2核4G4M带宽60G系统盘只要165元/1年。云服务器2核2G3M带宽40G系统盘只要99元/1年&#xff0c;2核4G5M带宽80G系统盘只要…

功能测试转自动化测试好不好转型?

手工测试做了好多年&#xff0c;点点点成了每天必须做的事情。但是随着自动化测试趋势的日渐明显&#xff0c;以及受到薪资、技能的双重考验&#xff0c;掌握自动化测试成为了必备技能。 手工转自动化测试&#xff0c;不是一蹴而就的。“预先善其事&#xff0c;必先利其器”&a…

FTP,SFTP,FTPS,SSL,TSL简介,区别,联系,使用场景说明

文章目录 简介FTPFTPSSFTP加密场景选择FTPS还是SFTPFTP、SFTP、FTPS区别、联系和具体使用场景如何使用FTP、SFTP和FTPSSSLTLSSSL和TLS区别和联系&#xff0c;以及使用场景SSL和TLS技术上的区别一些问题隐式的TLS&#xff08;FTPS/SSL&#xff09;或者显式的TLS&#xff08;FTPS…

LeetCode 707. 设计链表 (JAVA)

1.题目 2. 思路分析 1.我们要设置一个虚拟头节点&#xff0c;因为这个虚拟头节点对于增加节点操作和删除节点操作都很方便。 2.仔细读题&#xff0c;题目中说链表中的节点下标是从0开始的。也就是说第一个节点下标为0。 3.增加节点和删除节点的操作我们都要获取到它前一个的节…

洗衣洗鞋店小程序对接水洗唛打印,一键预约,支付无忧

随着社会的进步和科技的发展&#xff0c;我们的生活幸福感与日俱增。为了让我们从琐碎中解脱出来&#xff0c;干洗店洗鞋店行业也日新月异。今天&#xff0c;我为大家推荐这款优秀的干洗店小程序系统&#xff0c;让您的洗衣洗鞋服务体验更上一层楼。 干洗店管理系统是一款专为洗…

HTML静态网页成品作业(HTML+CSS)——家乡漳州介绍设计制作(1个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有1个页面。 二、作品演示 三、代…