发布于 5年前

PHP 版 LeetCode 代码实现——2. Add Two Numbers (两个数字相加 )

题目描述

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

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

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

示例:

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

解决方案

方法:初等数学

思路

对两数相加方法的可视化: 342 + 465 = 807342+465=807, 每个结点都包含一个数字,并且数字按位逆序存储。

算法

就像你在纸上计算两个数字的和那样,我们首先从最低有效位也就是列表 l1l2 的表头开始相加。由于每位数字都应当处于 0…9 的范围内,我们计算两个数字的和时可能会出现“溢出”。例如,5 + 7 = 12。在这种情况下,我们会将当前位的数值设置为 2,并将进位 carry=1 带入下一次迭代。进位 carry必定是 0 或 1,这是因为两个数字相加(考虑到进位)可能出现的最大和为 9 + 9 + 1 = 19。

我们使用变量来跟踪进位,并从包含最低有效位的表头开始模拟逐位相加的过程。

伪代码如下:

  • 将当前结点初始化为返回列表的哑结点。
  • 将进位 carry初始化为 0。
  • 将 p 和 q 分别初始化为列表 l1 和 l2 的头部。
  • 遍历列表 l1 和 l2 直至到达它们的尾端。
    • 将 x 设为结点 p 的值。如果 p 已经到达 l1 的末尾,则将其值设置为 0。
    • 将 y 设为结点 q 的值。如果 q 已经到达 l2 的末尾,则将其值设置为 0。
    • 设定 sum = x + y + carry。
    • 更新进位的值,carry = sum / 10。
    • 创建一个数值为 (sum mod 10) 的新结点,并将其设置为当前结点的下一个结点,然后将当前结点前进到下一个结点。
    • 同时,将 p 和 q 前进到下一个结点。
  • 检查 carry = 1 是否成立,如果成立,则向返回列表追加一个含有数字 1 的新结点。
  • 返回哑结点的下一个结点。

请注意,我们使用哑结点来简化代码。如果没有哑结点,则必须编写额外的条件语句来初始化表头的值。

请特别注意以下情况:

测试用例 说明
l1=[0,1] l2=[0,1,2] 当一个列表比另一个列表长时。
l1=[] l2=[0,1] 当一个列表为空时,即出现空列表。
l1=[9,9] l2=[1] 求和运算最后可能出现额外的进位,这一点很容易被遗忘。

class Solution {
    private $carry = 0;

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {

        //go ahead an instantiate a ListNode for ->next
        $return = new ListNode($this->carry + $l1->val + $l2->val);

        //如果 val 大于等于 10,carry 将进位设置为1,val减去10
        if ($this->carry = intval($return->val > 9)) {
            $return->val -= 10;
        }

        //如果没有下一个数字了,就做完了。否则将 next 定义为 ListNotes 的下一个
        $return->next = (!$this->carry && is_null($l1->next) && is_null($l2->next))
            ? null
            : $this->addTwoNumbers($l1->next, $l2->next);

        //完成嵌套循环以定义所有内容后,返回结果
        return $return;
    }
}

>>> PHP 版 LeetCode 解题思路及代码实现

©2020 edoou.com   京ICP备16001874号-3