The sum of two numbers [of moderate difficulty]

Topics

Two non-empty linked lists are given to represent two non-negative integers. Among them, their respective digits are stored in reverse order, and each of their nodes can only store one digit.

If we add the two numbers together, we return a new list to represent their sum.

You can assume that neither of these numbers will begin with zero except the number 0.

Examples:

Input: (2 - > 4 - > 3) + (5 - > 6 - > 4)
Output: 7 - > 0 - > 8
Cause: 342 + 465 = 807

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

II. Answer

1. Algorithmic ideas

It's a question of storing numbers in a linked list and adding them up. It's not difficult. According to personal thinking, there are two ways to learn from:

[1] Add each other one by one, add each one first, put the flag generated by carry, and then add 10 bits to add flag, and then empty the flag after adding flag. It is worth noting that some boundary problems need to be handled carefully.

[2] Conversion and addition, Java provides BigInteger, no matter how large integers can be added, the idea is to convert the list into a string (pay attention to reverse), and then into BigInteger, after the addition can be converted back, very simple.

 

2. Code

[1] JAVA implementation:

    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;  //Grasp the penultimate
            listNode = listNode.next;
        }
        if(daoshudier.next.val == 0){
            daoshudier.next = null;
        }
        return p;
    }

[2] Python implementation:

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        '''
            //Calculate the sum of the additions of two linked lists
        :param l1: Chain 1
        :param l2: List 2
        :return: The results of the addition of two linked lists
        '''
        listNode = ListNode(0)
        rsp = listNode
        daoshudier = listNode   # This pointer points to the penultimate node
        p = l1
        length = 0  # Length of linked list
        length1 = 0
        length2 = 0
        flag = 0    # Carry mark, the sum of two digits, the result will not exceed two digits
        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
        # Pre-return judgment
        return rsp


    def getGeWei(self, num: int):
        '''
            //Get two-digit digits
        :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):
        '''
            //Get ten digits of two digits
        :param num:
        :return:
        '''
        if num > 99:
            return None
        if num < 10 and num >= 0:   # There are no ten digits in a single digit. Ten digits are zero.
            return 0
        elif num > 9 and num <= 99:
            return int(list(str(num)).pop(0))

3. Operation results

Figure 1 - JAVA code execution results (the fastest 2 ms in the submission record, Tian Na)

Figure 2 - Python execution results

4. Summary

Using JAVA and Python two languages to write a simple algorithm, but the problem arises, JAVA execution 23ms in the analysis diagram did not appear, meaning that I write this JAVA code poorly. If you follow the Python set to use JAVA writing efficiency should be higher, but I have to lament that JAVA is more flexible than Python, there are many can be optimized.

After several days of writing, let me understand that the general algorithm problem is not difficult, but flexibility is really true. Over the past few days, I have a further understanding of debugging, and I have another idea about code optimization. Come on. Make persistent efforts

Tags: Programming Java Python

Posted on Wed, 04 Sep 2019 21:16:52 -0700 by monkuar