当前位置:网站首页>力扣题(2)—— 两数相加
力扣题(2)—— 两数相加
2022-07-30 22:06:00 【世界的隐喻】
两数相加
题目内容
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例
示例 1:
输入: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
题目数据保证列表表示的数字不含前导零
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/add-two-numbers
题解一:暴力解法
根据示例的解释,最先想到的方法就是将链表转为数字,然后数字相加再翻转,最后生成新链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 循环输出 l1 链表的数字添加到列表中
l1_list = []
while True:
if l1 is None:
break
l1_list.append(l1.val)
l1 = l1.next
# 循环输出 l2 链表的数字添加到列表中
l2_list = []
while True:
if l2 is None:
break
l2_list.append(l2.val)
l2 = l2.next
# 将 l1 列表中的数字连接形成字符串
a = ""
for i in l1_list:
a += str(i)
# 将 l2 列表中的数字连接形成字符串
b = ""
for i in l2_list:
b += str(i)
# 将 l1 ,l2 形成的字符串翻转之后形成相加之后的数字
c = int(a[::-1]) + int(b[::-1])
c = str(c) # 数字转换为字符串
# 翻转最后的字符串,循环形成新的链表
for i in range(0, len(c)):
if i == 0:
res = ListNode(val = int(c[i]), next = None)
else:
res = ListNode(val = int(c[i]), next = res)
return res
力扣通过的时间大约是104 ms
题解二
根据示例一可以发现其实这是一个从最高位向最低位运算的竖式运算,并且根据示例三可以发现题目的竖式计算是最高位对齐的竖式计算。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 循环输出 l1 链表的数字添加到列表中
l1_list = []
while True:
if l1 is None:
break
l1_list.append(l1.val)
l1 = l1.next
# 循环输出 l2 链表的数字添加到列表中
l2_list = []
while True:
if l2 is None:
break
l2_list.append(l2.val)
l2 = l2.next
res = []
l1_length = len(l1_list)
l2_length = len(l2_list)
num_ten = 0
# 考虑 l1 和 l2 链表不一样长的情况
min_length = min(l1_length, l2_length)
max_length = max(l1_length, l2_length)
for i in range(0, min_length): # 尾(头部)对齐
num = l1_list[i] + l2_list[i] + num_ten
num_ten = num // 10 # 10位数上的数字,即需要进位的数字
num_one = num % 10 # 个位数上的数字
res.append(num_one) # 根据竖式运算法则,保留个位数字,十位数进位
for i in range(min_length, max_length): # 长出的部分进行进位
if l1_length > min_length:
num = l1_list[i] + num_ten
num_ten = num // 10 # 10位数上的数字
num_one = num % 10 # 个位数上的数字
res.append(num_one)
elif l2_length > min_length:
num = l2_list[i] + num_ten
num_ten = num // 10 # 10位数上的数字
num_one = num % 10 # 个位数上的数字
res.append(num_one)
if num_ten != 0:
res.append(num_ten)
# 翻转并形成链表
res = res[::-1]
for i in range(0, len(res)):
if i == 0:
ans = ListNode(val = int(res[i]), next = None)
else:
ans = ListNode(val = int(res[i]), next = ans)
return ans
力扣通过的时间大约是56 ms
边栏推荐
猜你喜欢
CISP-PTE Zhenti Demonstration
CISP-PTE真题演示
手动从0搭建ABP框架-ABP官方完整解决方案和手动搭建简化解决方案实践
大家都在用的plm项目管理软件有哪些
TransGAN代码复现—九天毕昇平台
MySQL 8.0.29 解压版安装教程(亲测有效)
Jetson AGX Orin 平台关于c240000 I2C总线和GMSL ses地址冲突问题
cmd (command line) to operate or connect to the mysql database, and to create databases and tables
A simple rich text editor
系统结构考点之并行主存
随机推荐
The most powerful and most commonly used SQL statements in history
mysql deadlock
折叠旧版应用程序
Navigation Bar----Personal Center Dropdown
openim支持十万超级大群
c语言进阶篇:指针(五)
socket: Kernel initialization and detailed process of creating streams (files)
Teach you how to build a permanently running personal server
代码越写越乱?那是因为你没用责任链
Niu Ke Xiaobaiyue Race 53 A-E
TransGAN code reproduction - Jiutian Bisheng Platform
MySQL 5.7 detailed download, installation and configuration tutorial
Qt 同时生成动态库和静态库
MySQL user authorization
【Network Security Column Directory】--Penguin Column Navigation
cnpm的安装与使用
proxy反向代理
The reason for not using bs4 is that the name is too long?Crawl lottery lottery information
LeetCode · 23. Merge K ascending linked lists · recursion · iteration
ClickHouse 数据插入、更新与删除操作 SQL