【LeetCode】两数相加

「爱情、让人受尽委屈。」 2023-08-17 15:30 117阅读 0赞

题目要求：

@lc app=leetcode.cn id=2 lang=java
     
      [2] 两数相加
     
      https://leetcode-cn.com/problems/add-two-numbers/description/
     
      algorithms
      Medium (35.40%)
      Likes:    2913
      Dislikes: 0
      Total Accepted:    189.6K
      Total Submissions: 535.4K
      Testcase Example:  '[2,4,3]\n[5,6,4]'
     
      给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
      
      如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
      
      您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
      
      示例：
      
      输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
      输出：7 -> 0 -> 8
      原因：342 + 465 = 807
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */

最开始，我的想法是，先从链表中把数字取出，然后相加，再最后生成结果的链表集合，完活，代码实现如下：

class Solution {
    
        public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // 结果集链表
            ListNode resl = new ListNode(0);
            // 第一个数字
            double firstNum = 0;
            // 第二个数字
            double secNum = 0;
            
            // 读取数字
            firstNum = readListNode(l1,0);
            secNum = readListNode(l2,0);
    
            double i = firstNum + secNum;
            resl = outAddNode(i,1);
            return resl;
        }
    
        // 取数递归
        public static double readListNode(ListNode s,int depth){
            if (s == null){
                return 0;
            }
            double res = s.val;
            for (int j =0 ; j < depth; j++){
                res *= 10;
            }
            if (s.next != null){
                res += readListNode(s.next,depth+1);
            }
            return res;
        }
    
        // 取链表递归
        public static ListNode outAddNode(double i, int j){
            ListNode resl = new ListNode(0);
            double tmp = 1;
            for (int m = 0; m < j; m++) {
                tmp = tmp * 10;
            }
            if (i/(tmp/10)>0.1){
                resl.val =(int)((i % tmp) / (tmp/10));
            }
            if (i/(tmp)>=1) {
                j++;
                resl.next = outAddNode(i,j);
            }
            return resl;
        }
    }

利用正向思维的话，会先得出我这个样子的结论，但是这个并不完美，因为链表的长度是不可控制的，最开始的时候，我使用的是int类型来进行计算，可以完全满足题目给的demo的例子，但是走submit的case的时候到第30多个case的时候，数据大小就已经不够用了，出现了溢出之后的移位进位操作，数字完全对不上了，然后我就修改了数据类型为long类型，发现到了1503case的时候还是不够，后来又变化了double和float类型之后依然是有不足的时候，这个时候就体现出来了这种想法的弊端，那就是用有限的数据类型来处理无限的链表数字。

直接转换数字是一种不可行的思路，那么应该如何处理呢？由此我们可以想到我们最开始小学学习3位数加减法的时候，我们都是从个位一点一点算起的，由于链表是从个位开始的，我们是不是也可以从这样的角度出发，引入进位和逐个位进行遍历的概念，进行相加的操作呢？

来看一下初步实现：

class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            return add(l1,l2,0);
        }
    
        // 递归逐个位进行相加
        public ListNode add(ListNode l1, ListNode l2, int a){
            if(l1 == null && l2 == null && a == 0) return null;
            int x = l1==null ? 0 : l1.val;
            int y = l2==null ? 0 : l2.val;
            int sum = x + y + a;
            ListNode n = new ListNode(sum % 10);
            // 用进位进行叠加递归
            n.next = add(l1==null ? null : l1.next,
                         l2==null ? null : l2.next,
                         sum/10);
            return n;
        }
    }

这样的思路就可以所有的case都通过了。