LeetCode 刷题之两数相加

LeetCode 刷题之两数相加

Chris Yue No Comment
Posts

闲来无事在 GitHub 上乱逛(似乎 GitHub 快成为一个社区网站了),才发现有 LeetCode 这么个网站。最近着实有点无聊,杀时间的网站挺适合我。

做了几道题,感觉还有点意思,有刷怪升级那味儿。刷题的过程当中有些想法,很值得为自己总结一下。

首先先说两数相加。题目:

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

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

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

示例:

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

解题思路

个位加了之后,接下来的十位,实际上跟个位的做法,并没有本质上的区别

另外,在一次递归中,下次递归所获取的结果,正好就是这次递归返回结果的 next

所以用递归是最容易理解的方式:

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        static $e = 0; // 进位
        if (null === $l1 && null === $l2) {
            if (0 === $e) {
                return null;
            }

            $e = 0;
            
            return new ListNode(1);
        }

        switch (null) {
            case $l1:
                $l = $l2;
                break;
            case $l2:
                $l = $l1;
                break;
            default:
                $l = new ListNode($l1->val + $l2->val);
        }

        $l->val += $e;
        $e = 0;
        if ($l->val > 9) {
            $l->val %= 10;
            $e = 1;
        }

        $ll = $this->addTwoNumbers($l1->next ?? null, $l2->next ?? null);
        if (null !== $ll) {
            $l->next = $ll;
        }

        return $l;
    }
}

提交了代码之后,才知道原来 LeetCode 还可以评价代码的质量(运行效率/内存占用打败了 xx% 用户),上面的代码效率和内存还行,但应该还有进步的空间。不过我并不想把这两个指标当成一个绝对指标,包括以后的 LeetCode 刷题心得分享,都是以『最容易理解』为首要目的。当然也不是说完全不顾效率和内存。

做完这道题,我实际花费的时间还是挺多的,懒于总结是我最吃亏的地方,从今往后还是要注意总结。对于上面的题目,我的总结是,对于链式数据结构的处理,是否一开始就用递归的方式思考,会更省时间呢?期待下一个链式数据的题目。

LeetCode 刷题之两数相加 by Chris Yue is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

微信赞赏码

写作累,服务器还越来越贵
求分担,祝愿好人一生平安
天使打赏人

发表评论

27 − 25 =