刻意练习:LeetCode实战 -- Task10. 两数相加
背景
本篇图文是LSGO软件技术团队组织的 第二期基础算法(Leetcode)刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级的题目,共计三十道题,利用三十天的时间完成这组刻意练习。
本次任务的知识点:链表
链表(Linked List) 是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里除了存放本身数据(data fields)之外还存放其后继节点的指针(Pointer)。
使用链表结构可以克服数组需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
链表有很多种不同的类型:单向链表,双向链表以及循环链表。
题目
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
示例 2:
输入:(3 -> 7) + (9 -> 2)
输出:2 -> 0 -> 1
原因:73 + 29 = 102
实现
C# 语言
思路:模仿我们小学时代学的加法运算。个位相加超过十进一,十位相加有进位则加上进位,依次类推。
- 状态:通过
- 执行用时: 144 ms, 在所有 C# 提交中击败了 97.98% 的用户
- 内存消耗: 26.7 MB, 在所有 C# 提交中击败了 5.07% 的用户
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution
{
public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
ListNode result = new ListNode(-1);
ListNode l3 = result;
int flag = 0;
while (l1 != null && l2 != null)
{
int a = l1.val;
int b = l2.val;
int c = a + b + flag;
l3.next = new ListNode(c%10);
flag = c >= 10 ? 1 : 0;
l1 = l1.next;
l2 = l2.next;
l3 = l3.next;
}
while (l1 != null)
{
int a = l1.val + flag;
l3.next = new ListNode(a%10);
flag = a >= 10 ? 1 : 0;
l1 = l1.next;
l3 = l3.next;
}
while (l2 != null)
{
int b = l2.val + flag;
l3.next = new ListNode(b%10);
flag = b >= 10 ? 1 : 0;
l2 = l2.next;
l3 = l3.next;
}
if (flag == 1)
{
l3.next = new ListNode(flag);
}
return result.next;
}
}
Python 实现
- 执行结果:通过
- 执行用时 :108 ms, 在所有 Python 提交中击败了 16.54% 的用户
- 内存消耗 :13.6 MB, 在所有 Python 提交中击败了 8.73 %的用户
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
result = ListNode(-1)
l3 = result
flag = 0
while l1 is not None and l2 is not None:
a = l1.val
b = l2.val
c = a + b + flag
l3.next = ListNode(c % 10)
flag = 1 if c >= 10 else 0
l1 = l1.next
l2 = l2.next
l3 = l3.next
while l1 is not None:
a = l1.val + flag
l3.next = ListNode(a % 10)
flag = 1 if a >= 10 else 0
l1 = l1.next
l3 = l3.next
while l2 is not None:
b = l2.val + flag
l3.next = ListNode(b % 10)
flag = 1 if b >= 10 else 0
l2 = l2.next
l3 = l3.next
if flag == 1:
l3.next = ListNode(flag)
return result.next
来源
- https://leetcode-cn.com/problems/add-two-numbers/
往期活动
LSGO软件技术团队会定期开展提升编程技能的刻意练习活动,希望大家能够参与进来一起刻意练习,一起学习进步!
- Python基础刻意练习活动即将开启,你参加吗?
- Task01:变量、运算符与数据类型
- Task02:条件与循环
- Task03:列表与元组
- Task04:字符串与序列
- Task05:函数与Lambda表达式
- Task06:字典与集合
- Task07:文件与文件系统
- Task08:异常处理
- Task09:else 与 with 语句
- Task10:类与对象
- Task11:魔法方法
- Task12:模块
我是 终身学习者“老马”,一个长期践行“结伴式学习”理念的 中年大叔。
我崇尚分享,渴望成长,于2010年创立了“LSGO软件技术团队”,并加入了国内著名的开源组织“Datawhale”,也是“aaa@qq.com”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。
愿我们一起学习,一起进步,相互陪伴,共同成长。
后台回复「搜搜搜」,随机获取电子资源!
欢迎关注,请扫描二维码: