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. 两数相加
写在前面: 题目链接:LeetCode2两数相加 编程语言:C 题目难度:中等 一、题目描述 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 …...
基于无线传感网络(WSN)的目标跟踪技术(Matlab代码实现)
目录 💥1 概述 📚2 运行结果 🎉3 参考文献 👨💻4 Matlab代码 💥1 概述 无线传感器网络由于其自组织性、鲁棒性及节点数量巨大的特点,非常适合于目标跟踪。无线传感器网络中的移动目标跟踪实际上就是…...
百度发布首个可信AI工具集TrustAI,助力数据分析与增强
百度发布首个集分析与增强于一体的可信AI工具集TrustAI,该工具集旨在帮助用户快速、准确地对各种类型的数据进行分析和增强,从而提高数据的价值和可信度。 随着人工智能技术的快速发展,数据的价值和重要性日益凸显。然而,在数据处…...
电力系统负荷与电价预测优化模型(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
asp.net+C#超市商品进销存管理系统
本超市商品管理系统主要超市内部提供服务,系统分为管理员员工两部分。 本研究课题重点主要包括了下面几大模块:管用户登录,员工管理,商品管理,进货管理,销售管理,供应商信息,会员信…...
轻量级K8s发行版的五大优势,助力企业快速拥抱边缘计算
随着物联网和移动设备的普及,边缘计算已成为当前信息技术领域的热门话题。为了满足这一需求,越来越多的企业开始探索使用容器化技术来打造轻量级的K8s发行版。这种发行版可以更加灵活地部署在物理边缘,提供更快速、更稳定的服务。 在这篇文章…...
【深入理解redis】数据结构
文章目录 动态字符串SDS字符串编码类型 intsetDictZipListZipList的连锁更新问题 QuickListSkipListRedisObjectStringListSet结构ZSETHash Redis 共有 5 种基本数据结构:String(字符串)、List(列表)、Set(…...
《计算机网络—自顶向下方法》 第三章Wireshark实验:DNS协议分析
域名系统 DNS(Domain Name System) 是互联网使用的命名系统,用于把便于大家使用的机器名字转换为 IP 地址。许多应用层软件经常直接使用 DNS,但计算机的用户只是间接而不是直接使用域名系统。 互联网采用层次结构的命名树作为主机的名字,并使…...
JUC(十二)-线程中断相关问题(LockSupport,sleep,InterruptException)
JUC线程中断相关问题总结 线程中断相关问题总结 JUC线程中断相关问题总结一、 sleep 和线程中断之间的关系和特点结论测试验证代码如下 二、 LockSupport 和线程中断之间的关系结论测试验证代码如下 一、 sleep 和线程中断之间的关系和特点 结论 线程调用 Thread.sleep之后会进…...
Kotlin高级协程
Kotlin高级协程 一.前言二.先从线程说起三.协程的设计思想四.协程特点:优雅的实现移步任务五.协程基本使用六.协程和线程相比有什么特点,如何优雅的实现异步任务 一.前言 在文章正式上干货之前,先说一点背景吧;我是 Kotlin 协程官…...
车载软件架构——闲聊几句AUTOSAR BSW(四)
我是穿拖鞋的汉子,魔都中坚持长期主义的工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 我们并不必要为了和谐,而时刻保持通情达理;我们需要具备的是,偶尔有肚量欣然承认在某些方面我们可能会有些不可理喻。该有主见的时候能掷地有声地镇得住场…...
Linux:rpm查询安装 yum安装
环境: 需要插入安装镜像 镜像内有所需的安装库 我这里使用的虚拟机直接连接光盘 连接的光盘挂载在/dev/cdrom 由于我们无法直接进入,所以选择把/dev/cdrom挂载到别的地方即可 mount /dev/cdrom /123 将/dev/cdrom 挂载到 /123 目录下 Packages下就是…...
Android音视频开发之音频录制和播放
1.封装音频录制工具类: 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维校验阵可以写成 令码字为系…...
代码命名规范是真优雅呀!代码如诗
日常编码中,代码的命名是个大的学问。能快速的看懂开源软件的代码结构和意图,也是一项必备的能力。那它们有什么规律呢? Java项目的代码结构,能够体现它的设计理念。Java采用长命名的方式来规范类的命名,能够自己表达…...
你不知道的自动化?使用自动化测试在项目中创造高业务价值...
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 脱离数据支撑谈价…...
通过实现一个简单的 JavaScript 猜数字大小的游戏,介绍如何进行布局样式处理
JavaScript 猜数字大小是一个非常简单、却又经典的游戏,可以锻炼玩家的逻辑思维能力。在这个游戏中,电脑会随机生成一个数字,玩家需要根据提示逐步猜出正确的数字。接下来,我们将通过实现一个简单的 JavaScript 猜数字大小游戏来介…...
Java设计模式(二十二)策略模式
一、概述 策略模式是一种行为型设计模式,它允许在运行时选择算法的行为。策略模式通过将算法封装成独立的策略类,使得它们可以相互替换,而不影响使用算法的客户端。这样可以使客户端代码与具体算法的实现细节解耦,提高了代码的可…...
【沐风老师】一步一步教你在3dMax中进行UVW贴图和展开UVW的方法
将简单或程序材质应用于对象并不难。但是当表面需要在其上显示某种纹理时,它会变得更加复杂。任何纹理贴图都放在材质的 Diffuse 插槽中,但渲染的结果可能无法预测。这就是为什么我们需要了解 3DMAX 如何将纹理应用于 3D 对象,什么是 UVW 贴图…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...
