Leetcode 2:两数相加(最详细解决方案!!!)
发布日期:2021-06-29 16:00:43
浏览次数:3
分类:技术文章
本文共 2314 字,大约阅读时间需要 7 分钟。
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)输出:7 -> 0 -> 8原因:342 + 465 = 807
解题思路
首先想到的解决思路是将链表中的数转化为数据类型,然后加起来(可能会发生越界问题),再转化为链表。
class Solution: def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ def get_num(l): num = 0 t = 1 while l != None: l, val = l.next, l.val num += val*t t *= 10 return num l3 = get_num(l1) + get_num(l2) ret = t = ListNode(0) if l3 == 0: return ret while l3 != 0: n = l3 % 10 t.next = ListNode(n) t = t.next l3 //= 10 return ret.next
但是这个解法是如此的丑陋!!!
那么能不能不把链表中的数据转化为ListNode
,而直接在它的基础上进行加法呢?我们这样去做的话,会遇到这样的一个问题,当两个数的和大于10
的时候,他们相加的结果就会进位,所以要解决的问题就是这个进位问题。
class Solution: def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ cur = ret = ListNode(0) add = 0 while l1 or l2 or add: val = (l1.val if l1 else 0) + (l2.val if l2 else 0) + add add = val // 10 cur.next = ListNode(val % 10) cur = cur.next l1 = l1.next if l1 else None l2 = l2.next if l2 else None return ret.next
我们通过添加一个变量add
去记录这个进位的值。这样我们的代码变得比之前简洁了很多。
我在这里同时给出对应的c++
版本。
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dumHead = new ListNode(0); ListNode* p = dumHead; int add = 0; while (l1 || l2 || add) { int val = get_value(l1) + get_value(l2) + add; add = val / 10; p->next = new ListNode(val % 10); p = p->next; l1 = get_p(l1); l2 = get_p(l2); } ListNode* ret = dumHead->next; delete dumHead; return ret; }private: int get_value(ListNode* l) { if (l != nullptr) return l->val; else return 0; } ListNode* get_p(ListNode* l) { if (l != nullptr) return l->next; return nullptr; }};
我将该问题的其他语言版本添加到了我的
如有问题,希望大家指出!!!
转载地址:https://coordinate.blog.csdn.net/article/details/80435080 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月03日 15时34分28秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
awk 的内置变量 NF、NR、FNR、FS、OFS、RS、ORS
2019-04-29
CentOS系统内核升级攻略
2019-04-29
linux系统时区修改(Debian的主机和docker)
2019-04-29
docker-compose 安装
2019-04-29
crontab 定时任务
2019-04-29
查看docker veth pair与宿主机上网卡的对应关系
2019-04-29
使用 GitLab CI 进行持续集成的一些踩坑
2019-04-29
企业云盘给贸易业带来新的效益
2019-04-29
Linux入门常用命令
2019-04-29
Spring整理
2019-04-29
SpringMvc加强
2019-04-29
初识Vue全家桶 Nuxt.js(一)
2019-04-29
基本路由及动态路由(二)
2019-04-29
视图:默认模板+默认布局(自定义布局)+nuxt.js页面(三)
2019-04-29
基于nuxt下asyncData,fetch发送axios请求(四)
2019-04-29
插件机制+自定义axios(五)
2019-04-29
Redis的学习之路
2019-04-29
Windows下Redies+GUI安装,使用Jedis与spring boot 整合
2019-04-29