欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

刻意练习:LeetCode实战 -- Task10. 两数相加

程序员文章站 2024-03-15 23:22:54
...

背景

本篇图文是LSGO软件技术团队组织的 第二期基础算法(Leetcode)刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级的题目,共计三十道题,利用三十天的时间完成这组刻意练习。

本次任务的知识点:链表

链表(Linked List) 是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里除了存放本身数据(data fields)之外还存放其后继节点的指针(Pointer)。

刻意练习:LeetCode实战 -- Task10. 两数相加

使用链表结构可以克服数组需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

链表有很多种不同的类型:单向链表,双向链表以及循环链表。


题目

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 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软件技术团队会定期开展提升编程技能的刻意练习活动,希望大家能够参与进来一起刻意练习,一起学习进步!


我是 终身学习者“老马”,一个长期践行“结伴式学习”理念的 中年大叔

我崇尚分享,渴望成长,于2010年创立了“LSGO软件技术团队”,并加入了国内著名的开源组织“Datawhale”,也是“aaa@qq.com”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习,一起进步,相互陪伴,共同成长。

后台回复「搜搜搜」,随机获取电子资源!
欢迎关注,请扫描二维码:
刻意练习:LeetCode实战 -- Task10. 两数相加