当前位置: 首页 > news >正文

LeetCode2. 两数相加

写在前面:

题目链接:LeetCode2两数相加
编程语言:C++
题目难度:中等

一、题目描述

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
在这里插入图片描述

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

提示:

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

二、题目分析&解题思路&代码实现

2.1 常规老实人解法

解之前先吐槽一番,计算两个数相加的结果,给个单向链表也就算了,存的还是数字的反序,意味着本来要计算,123+23,还得
先将链表遍历一遍

3->2->1
3->2

反序一次得到正序 (后面才意识到不用反序)

1,2 ,3
2,3

接下来就开始进行
加法运算

要么先将 1,2 ,3 和2,3 先转换为 123、23 ,然后计算得出结果为 146,然后再逐一的进行再把每一位取出来,并且按照逆序 构建成 一个 6->4->1 单向链表再返回回去;

要么直接进行按位相加,自己设计进位,最后 组成 6,4,1 这样有一个序列然后构建链表,再返回。

各位献丑了,且看我写了半小时的代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* listResult = new ListNode();vector<int> vct1;vector<int> vct2;ListNode* nodeTemp = l1;//先将l1、l2遍历一遍while(nodeTemp != nullptr){vct1.push_back(nodeTemp->val);nodeTemp = nodeTemp->next;}ListNode* nodeTemp1 = l2;while(nodeTemp1 != nullptr){vct2.push_back(nodeTemp1->val);nodeTemp1 = nodeTemp1->next;}vector<int> vctResult;int i = 0;int j = 0;int iTemp = 0;bool isTen = false;//是否进位//开始按位相加 从 个位开始while(i<vct1.size() && j<vct2.size()){iTemp = vct1[i] + vct2[j];if(isTen){iTemp +=1;}if(iTemp >= 10){isTen = true;iTemp = iTemp -10;}   else{isTen = false;}      vctResult.push_back(iTemp);i++;j++;}//两个链表长度不相等,那么剩下的直接继续按位加即可while( i <vct1.size()){if(isTen)//注意上一个while 后可能还有进位 1{if(vct1[i] + 1 ==10)//继续进位{vctResult.push_back(0);isTen = true;}else{vctResult.push_back(vct1[i]+1);isTen = false;}i++;}else{//没有进位直接插入即可vctResult.push_back(vct1[i]);i++;}}//同理将剩下的都插入,和上面进位机制一样while( j< vct2.size()){if(isTen){if(vct2[j] + 1 ==10){vctResult.push_back(0);isTen = true;}else{vctResult.push_back(vct2[j]+1);isTen = false;}j++;}else{vctResult.push_back(vct2[j]);j++;}}if(isTen)//注意可能最后还有一次进位{vctResult.push_back(1);}//接下来构建出链表bool head = true;ListNode* nodenext = new ListNode();for(int k = 0; k < vctResult.size();k++){ListNode* node = new ListNode();node->val = vctResult[k];node->next = nullptr;if(head){listResult = node;//保存头,做返回值返回nodenext = node;head = false;}else{nodenext->next = node;nodenext = nodenext->next;}}return listResult;}
};

运行结果:
跑了几次好一点的就是下面这样了
在这里插入图片描述

2.1.2 优化后

写道最后,才发现不需要用两个vector 遍历,直接遍历链表即可,我们常固性思维觉得加法就是这样:
在这里插入图片描述
其实我们做个镜像对比:
在这里插入图片描述
这不就是我们刚好要的答案吗?
因此我们现在直接简化为:
遍历两个链表

3 -> 2 -> 1
3->2

将刚才的代码额外的两次遍历与两个vector 开辟 干掉:

在这里插入图片描述

直接做进位的加法,我们将上述的代码优化为:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* listResult = new ListNode();ListNode* nodeTemp = l1;ListNode* nodeTemp1 = l2;vector<int> vctResult;int i = 0;int j = 0;int iTemp = 0;bool isTen = false;//是否进位//开始按位相加 从 个位开始while(nodeTemp!=nullptr && nodeTemp1!=nullptr){iTemp = nodeTemp->val + nodeTemp1->val;if(isTen){iTemp +=1;}if(iTemp >= 10){isTen = true;iTemp = iTemp -10;}   else{isTen = false;}      vctResult.push_back(iTemp);nodeTemp = nodeTemp->next;nodeTemp1 = nodeTemp1->next;}//两个链表长度不相等,那么剩下的直接继续按位加即可while( nodeTemp!= nullptr){if(isTen)//注意上一个while 后可能还有进位 1{if(nodeTemp->val + 1 ==10)//继续进位{vctResult.push_back(0);isTen = true;}else{vctResult.push_back(nodeTemp->val+1);isTen = false;}nodeTemp=nodeTemp->next;}else{//没有进位直接插入即可vctResult.push_back(nodeTemp->val);nodeTemp=nodeTemp->next;;}}//同理将剩下的都插入,和上面进位机制一样while( nodeTemp1 != nullptr){if(isTen){if(nodeTemp1->val + 1 ==10){vctResult.push_back(0);isTen = true;}else{vctResult.push_back(nodeTemp1->val+1);isTen = false;}nodeTemp1 = nodeTemp1->next;}else{vctResult.push_back(nodeTemp1->val);nodeTemp1 = nodeTemp1->next;}}if(isTen)//注意可能最后还有一次进位{vctResult.push_back(1);}//接下来构建出链表bool head = true;ListNode* nodenext = new ListNode();for(int k = 0; k < vctResult.size();k++){ListNode* node = new ListNode();node->val = vctResult[k];node->next = nullptr;if(head){listResult = node;//保存头,做返回值返回nodenext = node;head = false;}else{nodenext->next = node;nodenext = nodenext->next;}}return listResult;}
};

在这里插入图片描述
可以看到时间和空间上都有所优化。

但是可以看到整个代码还是臭长臭长的,而且还开辟了一个新vector用于保存结果,空间复杂度也没有降低,还有没有更简介的写法呢?

2.3 写法简化&空间优化

之前还需要一个 bool 值来控制是否进位,每次还需要取余数等等,非常的繁琐
在这里插入图片描述
其实我们直接取两位和的个位数,为当前位的值,取 10 位上的数为进位即可
例如 5 + 9,

当前位为 14 % 10 = 4;
进位为:14 / 10 = 1;

而且之前会考虑链表长度不相等的情况,然后对余下的节点再做一次遍历,并且判断之前的进位:
在这里插入图片描述
换种思路,我们将空缺的部分补 上 0
在这里插入图片描述
这样来处理长度不一样的情况:

        int n1 = nodeTemp == nullptr ? 0: nodeTemp->val;int n2 = nodeTemp1 == nullptr ? 0:nodeTemp1->val;

完整代码示例:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head = nullptr;ListNode* tail = nullptr;ListNode* nodeTemp = l1;ListNode* nodeTemp1 = l2;int igientle = 0;//进位//开始按位相加 从 个位开始while(nodeTemp!=nullptr || nodeTemp1!=nullptr){//链表长度不够时补 0 ,int n1 = nodeTemp == nullptr ? 0: nodeTemp->val;int n2 = nodeTemp1 == nullptr ? 0:nodeTemp1->val;int temp = n1+n2+igientle;//两位的和再加上进位if(!head)//先将头节点保存好{head = new ListNode(temp % 10);//取余数tail = head;}  else{tail->next = new ListNode(temp%10);tail = tail->next;}igientle=temp/10;//进位   if(nodeTemp){nodeTemp = nodeTemp->next;}if(nodeTemp1){nodeTemp1 = nodeTemp1->next;}}if(igientle > 0)//最后还有进位时也加上{tail->next = new ListNode(igientle);}return head;}
};

运行结果:

在这里插入图片描述

相关文章:

LeetCode2. 两数相加

写在前面&#xff1a; 题目链接&#xff1a;LeetCode2两数相加 编程语言&#xff1a;C 题目难度&#xff1a;中等 一、题目描述 给你两个 非空 的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的&#xff0c;并且每个节点只能存储 一位 数字。 …...

基于无线传感网络(WSN)的目标跟踪技术(Matlab代码实现)

目录 &#x1f4a5;1 概述 &#x1f4da;2 运行结果 &#x1f389;3 参考文献 &#x1f468;‍&#x1f4bb;4 Matlab代码 &#x1f4a5;1 概述 无线传感器网络由于其自组织性、鲁棒性及节点数量巨大的特点,非常适合于目标跟踪。无线传感器网络中的移动目标跟踪实际上就是…...

百度发布首个可信AI工具集TrustAI,助力数据分析与增强

百度发布首个集分析与增强于一体的可信AI工具集TrustAI&#xff0c;该工具集旨在帮助用户快速、准确地对各种类型的数据进行分析和增强&#xff0c;从而提高数据的价值和可信度。 随着人工智能技术的快速发展&#xff0c;数据的价值和重要性日益凸显。然而&#xff0c;在数据处…...

电力系统负荷与电价预测优化模型(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

asp.net+C#超市商品进销存管理系统

本超市商品管理系统主要超市内部提供服务&#xff0c;系统分为管理员员工两部分。 本研究课题重点主要包括了下面几大模块&#xff1a;管用户登录&#xff0c;员工管理&#xff0c;商品管理&#xff0c;进货管理&#xff0c;销售管理&#xff0c;供应商信息&#xff0c;会员信…...

轻量级K8s发行版的五大优势,助力企业快速拥抱边缘计算

随着物联网和移动设备的普及&#xff0c;边缘计算已成为当前信息技术领域的热门话题。为了满足这一需求&#xff0c;越来越多的企业开始探索使用容器化技术来打造轻量级的K8s发行版。这种发行版可以更加灵活地部署在物理边缘&#xff0c;提供更快速、更稳定的服务。 在这篇文章…...

【深入理解redis】数据结构

文章目录 动态字符串SDS字符串编码类型 intsetDictZipListZipList的连锁更新问题 QuickListSkipListRedisObjectStringListSet结构ZSETHash Redis 共有 5 种基本数据结构&#xff1a;String&#xff08;字符串&#xff09;、List&#xff08;列表&#xff09;、Set&#xff08;…...

《计算机网络—自顶向下方法》 第三章Wireshark实验:DNS协议分析

域名系统 DNS(Domain Name System) 是互联网使用的命名系统&#xff0c;用于把便于大家使用的机器名字转换为 IP 地址。许多应用层软件经常直接使用 DNS&#xff0c;但计算机的用户只是间接而不是直接使用域名系统。 互联网采用层次结构的命名树作为主机的名字&#xff0c;并使…...

JUC(十二)-线程中断相关问题(LockSupport,sleep,InterruptException)

JUC线程中断相关问题总结 线程中断相关问题总结 JUC线程中断相关问题总结一、 sleep 和线程中断之间的关系和特点结论测试验证代码如下 二、 LockSupport 和线程中断之间的关系结论测试验证代码如下 一、 sleep 和线程中断之间的关系和特点 结论 线程调用 Thread.sleep之后会进…...

Kotlin高级协程

Kotlin高级协程 一.前言二.先从线程说起三.协程的设计思想四.协程特点&#xff1a;优雅的实现移步任务五.协程基本使用六.协程和线程相比有什么特点&#xff0c;如何优雅的实现异步任务 一.前言 在文章正式上干货之前&#xff0c;先说一点背景吧&#xff1b;我是 Kotlin 协程官…...

车载软件架构——闲聊几句AUTOSAR BSW(四)

我是穿拖鞋的汉子,魔都中坚持长期主义的工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 我们并不必要为了和谐,而时刻保持通情达理;我们需要具备的是,偶尔有肚量欣然承认在某些方面我们可能会有些不可理喻。该有主见的时候能掷地有声地镇得住场…...

Linux:rpm查询安装 yum安装

环境&#xff1a; 需要插入安装镜像 镜像内有所需的安装库 我这里使用的虚拟机直接连接光盘 连接的光盘挂载在/dev/cdrom 由于我们无法直接进入&#xff0c;所以选择把/dev/cdrom挂载到别的地方即可 mount /dev/cdrom /123 将/dev/cdrom 挂载到 /123 目录下 Packages下就是…...

Android音视频开发之音频录制和播放

1.封装音频录制工具类&#xff1a; public class RecorderAudioManagerUtils {private static volatile RecorderAudioManagerUtils mInstance;public static RecorderAudioManagerUtils getInstance() {if (mInstance null) {synchronized (RecorderAudioManagerUtils.class…...

Java之单例模式

目录 一.上节内容 1.什么是线程安全 2.线程不安全的原因 3.JMM(Java内存模型) 4.synchronized锁 5.锁对象 6.volatile关键字 7.wait()和notify() 8.Java中线程安全的类 二.单例模式 1.什么是单例 2.怎么设计一个单例 1.口头约定 2.使用编程语言的特性 三.饿汉模式…...

【分组码系列】线性分组码的网格图和维特比译码

线性分组码的网格图 由于码字的比特位是统计独立的,所以编码过程可以利用有限状态机来描述,它能精确地确定初始和最终状态。可以利用网格图进一步描述编码过程[36],采用维特比算法进行最大似然译码. 在GF(2)上定义线性分组码(n,k)。相应的(n-k)Xn维校验阵可以写成 令码字为系…...

代码命名规范是真优雅呀!代码如诗

日常编码中&#xff0c;代码的命名是个大的学问。能快速的看懂开源软件的代码结构和意图&#xff0c;也是一项必备的能力。那它们有什么规律呢&#xff1f; Java项目的代码结构&#xff0c;能够体现它的设计理念。Java采用长命名的方式来规范类的命名&#xff0c;能够自己表达…...

你不知道的自动化?使用自动化测试在项目中创造高业务价值...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 脱离数据支撑谈价…...

通过实现一个简单的 JavaScript 猜数字大小的游戏,介绍如何进行布局样式处理

JavaScript 猜数字大小是一个非常简单、却又经典的游戏&#xff0c;可以锻炼玩家的逻辑思维能力。在这个游戏中&#xff0c;电脑会随机生成一个数字&#xff0c;玩家需要根据提示逐步猜出正确的数字。接下来&#xff0c;我们将通过实现一个简单的 JavaScript 猜数字大小游戏来介…...

Java设计模式(二十二)策略模式

一、概述 策略模式是一种行为型设计模式&#xff0c;它允许在运行时选择算法的行为。策略模式通过将算法封装成独立的策略类&#xff0c;使得它们可以相互替换&#xff0c;而不影响使用算法的客户端。这样可以使客户端代码与具体算法的实现细节解耦&#xff0c;提高了代码的可…...

【沐风老师】一步一步教你在3dMax中进行UVW贴图和展开UVW的方法

将简单或程序材质应用于对象并不难。但是当表面需要在其上显示某种纹理时&#xff0c;它会变得更加复杂。任何纹理贴图都放在材质的 Diffuse 插槽中&#xff0c;但渲染的结果可能无法预测。这就是为什么我们需要了解 3DMAX 如何将纹理应用于 3D 对象&#xff0c;什么是 UVW 贴图…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...