找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法题:两数相加

admin 2019-6-7 06:34 158人围观 C++相关

        “ LeeCode第二题,难度中等”

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

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

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

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

    节点类:
      public class ListNode {    int val;    ListNode next;    ListNode(int x) { val = x; }}

      01



      Solution

        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//定义返回值的头 ListNode head = new ListNode(0);//将当前指针指向当前头 ListNode current = head;//进位的值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; current.next = new ListNode(sum % 10);//将指针指向next节点 current = current.next;//将l1和l2指向next节点if(l1 != null) l1 = l1.next;if(l2 != null) l2 = l2.next; }    //最后一次计算有进位,则最后一个节点的值为carryif(carry > 0){ current.next = new ListNode(carry); }return head.next;}

        执行代码:
          输入[2,4,3][5,6,4]输出[7,0,8]预期结果[7,0,8]

          提交代码:
            执行用时 : 9 ms, 在AddTwoNumbers的Java提交中击败了93.56% 的用户内存消耗 : 46.6MB, 在AddTwoNumbers的Java提交中击败了74.37% 的用户

            分析:

                解题思路与在草稿纸上计算2个整数相加差不多。注意进位,本题是2个数相加,carry的值最大为1。

            时间复杂度:O(max(m, n))。取2个链表的较长者。

            空间复杂度:O(max(m, n))。返回链表的长度=2个链表的较长者(+1)。

            原题链接:

            https://leetcode.com/problems/add-two-numbers/

            https://leetcode-cn.com/problems/add-two-numbers/



            点击留言~


            ----------------------------------------------------------------------------------------------------------------------
            我们尊重原创,也注重分享,文章来源于微信公众号:喜欢下雨所以爱上雷震子,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
            ----------------------------------------------------------------------------------------------------------------------

            鲜花

            握手

            雷人

            路过

            鸡蛋

            yafeilinux和他的朋友们微信公众号二维码

            微信公众号

            专注于Qt嵌入式Linux开发等。扫一扫立即关注。

            Qt开源社区官方QQ群二维码

            QQ交流群

            欢迎加入QQ群大家庭,一起讨论学习!

            我有话说......