[中等难度]两数相加

原创
2019/09/05 10:37
阅读数 260

一、题目

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

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

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

示例:

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

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

二、解答

1. 算法思路

这是一道用链表存各位数,然后相加的题,没什么难度。按照个人思路,有两种方法可以借鉴:

        [1] 逐位相加,先加各位,进位产生的放到flag;然后十位相加在加上flag,加完flag要清空;依次加..... 值得注意的是有些边界问题需要小心处理。

        [2] 转换相加法,Java提供BigInteger,无论多大的整数都可以相加,思路就是将链表转换成字符串(要注意reverse),进而转换成BigInteger,加完后转换回来即可,挺简单的。

 

2. 代码

[1] JAVA实现:

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode listNode = new ListNode(0);
        ListNode p = listNode;
        ListNode daoshudier = listNode;
        StringBuilder numStr1 = new StringBuilder();
        StringBuilder numStr2 = new StringBuilder();

        while (l1 != null){
            numStr1.append(l1.val);
            l1 = l1.next;
        }
        while (l2 != null){
            numStr2.append(l2.val);
            l2 = l2.next;
        }
        numStr1.reverse();
        numStr2.reverse();

        BigInteger num1 = new BigInteger(numStr1.toString());
        BigInteger num2 = new BigInteger(numStr2.toString());
        BigInteger ansTmp = num1.add(num2);

        String ans = ansTmp.toString();

        for(int i = ans.length() - 1; i > -1; i--){
            listNode.val = (int)ans.charAt(i) - 48;
            listNode.next = new ListNode(0);
            daoshudier = listNode;  //抓稳倒数第二个
            listNode = listNode.next;
        }
        if(daoshudier.next.val == 0){
            daoshudier.next = null;
        }
        return p;
    }

[2] Python实现:

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        '''
            计算两个链表相加的和
        :param l1: 链表1
        :param l2: 链表2
        :return: 两个链表相加后的结果
        '''
        listNode = ListNode(0)
        rsp = listNode
        daoshudier = listNode   # 该指针指向倒数第二个节点
        p = l1
        length = 0  # 链表的长度
        length1 = 0
        length2 = 0
        flag = 0    # 进位的标志,两个个位数字相加,结果不会超过两位数
        while p != None:
            length1 += 1
            p = p.next
        p = l2
        while p != None:
            length2 += 1
            p = p.next
        if length1 > length2:
            length = length1
        else:
            length = length2

        for i in range(length):
            if l1 != None and l1.val != None:
                tmp1 = l1.val
            else:
                tmp1 = 0
            if l2 != None and l2.val != None:
                tmp2 = l2.val
            else:
                tmp2 = 0
            rs = tmp1 + tmp2 + flag
            listNode.val = self.getGeWei(rs)
            listNode.next = ListNode(0)
            daoshudier = listNode
            listNode = listNode.next
            flag = self.getShiWei(rs)
            if l1 != None:
                l1 = l1.next
            if l2 != None:
                l2 = l2.next
        listNode.val += flag
        if listNode.val == 0:
            daoshudier.val += flag
            if daoshudier.val > 9:
                listNode.val = self.getShiWei(daoshudier.val)
            else:
                daoshudier.next = None
        # 返回前判断
        return rsp


    def getGeWei(self, num: int):
        '''
            获得二位数的个位数字
        :param num:
        :return:
        '''
        if num > 99:
            return None
        if num < 10 and num >= 0:
            return num
        elif num > 9 and num <= 99:
            return int(list(str(num)).pop(-1))

    def getShiWei(self, num: int):
        '''
            获得二位数字的十位数字
        :param num:
        :return:
        '''
        if num > 99:
            return None
        if num < 10 and num >= 0:   # 个位数字是没有十位的,十位为0
            return 0
        elif num > 9 and num <= 99:
            return int(list(str(num)).pop(0))

3.运行结果

图1 - JAVA代码执行结果(提交记录中最快的2ms,天呐)

图2 - Python执行结果

4.总结

使用JAVA和Python两种语言编写了简单的算法,但是问题来了,JAVA执行23ms的在分析图中没有出现,意思是我这个JAVA代码写的比较烂。如果照着Python这套来用JAVA写效率应该会高点,不过不得不感叹,JAVA比Python灵活,有很多可以优化的地方。

经过这几天的写题,让我明白了普通算法题也不是很难,不过灵活确实是真的。这几天的刷题对调试有了进一步的认识,同时对代码优化也抱有了另一种想法。加油!再接再厉

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部