1. 首页
  2. LeetCode

每日一道 LeetCode (45):两数相加

每日一道 LeetCode (45):两数相加

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:两数相加

题目来源:https://leetcode-cn.com/problems/add-two-numbers/

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

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

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

解题方案

先说一下,这道题的难度是中等难度,我又转回去了,从开头顺着往下做题了,昨天实际上题号已经是 200+ 了,我发现接下来的题大多数都变成了 SQL 题和 bash 脚本的题,所以决定返回到最开始,顺着往下做。

这道题看下来感觉不大像是中等难度的题,感觉还没有前两天的二进制数的题难,二进制数的题看了基本属于一脸懵逼的不知道要干什么,这道题读完了以后基本思路是有的。

直接对两个链表进行迭代,然后按位加起来就完了,如果有进位就记录下来,在下次迭代的时候把进位加上去。

因为这道题题目给出来的直接就是逆序的数字,所以直接顺序的从前往后迭代就好了,也没什么滑头。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode pre = new ListNode(0);
    ListNode curr = pre;
    // 定义进位
    int carry = 0;
    while (l1 != null || l2 != null) {
        int x = (l1 != null) ? l1.val : 0;
        int y = (l2 != null) ? l2.val : 0;
        int sum = x + y + carry;
        // 进位标记
        carry = sum / 10;
        // 构造下一个节点
        curr.next = new ListNode(sum % 10);
        // 将指针指向下一个节点
        curr = curr.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return pre.next;
}

这个计算方案中需要注意的只有一点,先定义了一个头结点 pre ,至于为什么要定义这个 pre ,因为在下面做迭代的时候,需要移动指针的,如果没有这个 pre 结点,下面迭代的时候指针就动不了了。

然后我去翻了下答案,发现就这一种解法,剩下的都是这种方案的变种解法,要么是定义两个其他的数据结构,比如说队列,先迭代的把数据放到队列里面,然后再迭代队列进行计算。

还有先迭代链表,把这两个整数直接搞成 int 型的,然后再加起来,最后再迭代这个数字转成链表,但是这种方案需要考虑类型溢出的问题,或许可能要搞成 double 类型或者 long 类型的,计算的时候还要注意精度问题。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code