Bolo  当前访客:0 管理登录

GeekTom | Blog

Be profound be funny or be quiet .

02 - 两数相加

2019-12-12 21:57:46 geektomya
0  评论    138  浏览

❤️ ❤️ 想了想,还是按着顺序做吧,遇山挖山,遇海填海? ? !

题目描述

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

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

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

示例:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers

问题拆解

首先由给定的整数是按照逆序的方式存储在链表中,那么就有一个很简单的思路就是,将每个位置的相加,如果大于10,就用一个变量来存储标识这个结果会进位,然后在本位置填上两数相加值%10即可,然后后面的每个节点的操作类似。于是,按照思路最直接的方式,写了一个勉强可以解决改问题的代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode result = head;
        int max = 10;//超过10进位
        int result_val = 0;//得到最后值
        int temporary_val = 0;//标识进位情况
      
        while(l1 != null&&l2 !=null){
            result_val = temporary_val + l1.val + l2.val;
            if(result_val >= max){
                result_val = result_val - max;
                temporary_val = 1;
            }else{
                temporary_val = 0;   
            }
            result.val = result_val;
            l1 = l1.next;
            l2 = l2.next;
            if(l1 != null && l2 != null){
                result.next = new ListNode(0);
                result = result.next;
            }
    }

    while(l1 == null&&l2 != null){
        result.next = new ListNode(0);
        result = result.next;
        if(temporary_val == 0){
             result.val = l2.val;
        }else{
             result_val = l2.val + temporary_val;
             if(result_val >= max){
                  result_val = result_val - max;
                  result.val = result_val;
                 temporary_val = 1;
             }else{
                  result.val = result_val;
                  temporary_val = 0;
             }
        }
         l2 = l2.next;
    }

      while(l2 == null&&l1 != null){
        result.next = new ListNode(0);
        result = result.next;
          if(temporary_val == 0){
             result.val = l1.val;
        }else{
            result_val = l1.val + temporary_val;
             if(result_val >= max){
                  result_val = result_val - max;
                  result.val = result_val;
                 temporary_val = 1;
             }else{
                  result.val = result_val;
                  temporary_val = 0;
             }
        }
        l1 = l1.next;
    }

      if(l2 == null&&l1 == null){
           if(temporary_val == 1){
             result.next = new ListNode(0);
             result = result.next;  
             result.val = temporary_val;
        }
      }
        return head;
    }
}

没错。。。看见这么长的代码我自己都有点晕,但是我第一次做的时候真的用了这么菜的方法。。然后我又开始思考,这里面这么多重复的代码,怎么修改能使得代码精简呢?看了半天才发现,我只要把循环的条件改了就可以了呀,就这样,常常的尾巴消失,摇身一变,简练精悍!修改后的代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode result = head;
        int max = 10;//超过10进位
        int result_val = 0;//得到最后值
        int temporary_val = 0;//标识进位情况
      
        while(l1 != null || l2 !=null || temporary_val!=0){
            /* 
             *如果不先判断取值而直接在下面用`l1.val`或者l2.val`有可能发生空指针异常
             */
            int l1_Val = l1 != null ? l1.val : 0;
            int l2_Val = l2 != null ? l2.val : 0;
            result_val = temporary_val + l1_Val + l2_Val;
            temporary_val = result_val/max;//进位情况
            result.val = result_val%max;//相加最后值
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
            /* 
             * 这里的temporary_val == 1这个判断可能会被忽视,导致5 + 5 这种只有进位,没有下一节点 
             * 的情况出现计算错误       
             */
            if(l2 != null||l1 != null||temporary_val == 1){
            result.next = new ListNode(0);
            result = result.next; 
             }          
    }
        return head;
    }
}

最后附上大佬代码:执行用时为 2 ms 的范例

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int carry = 0;
        while(l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            int sumVal = l1Val + l2Val + carry;
            carry = sumVal / 10;
            
            ListNode sumNode = new ListNode(sumVal % 10);
            cursor.next = sumNode;
            cursor = sumNode;
            
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        
        return root.next;
    }
}


标题:02 - 两数相加
作者:geektomya
地址:HTTPS://blog.zhqy.xyz/articles/2019/11/30/1575125278150.html
彧语:乾坤未定,你我皆是黑马!!!

发表评论




目录

TOP
取消