Deliberate practice: LeetCode actual combat task 10. Sum of two numbers

background

This text is organized by LSGO software technology team The second phase of Leetcode deliberate training camp Clock in task. In this training camp, five knowledge points (array, linked list, string, tree, greedy algorithm) are selected for classification practice. Each knowledge point selects three simple, two medium, and one difficult level questions, a total of 30 questions. This group of deliberate exercises are completed in 30 days.

Knowledge points of this task: linked list

Linked List is a kind of common basic data structure, which is a kind of linear table. However, it does not store data in linear order. Instead, it stores not only its own data fields but also the pointers of its subsequent nodes in each node.

The use of linked list structure can overcome the disadvantage that the array needs to know the size of the data in advance. The linked list structure can make full use of the memory space of the computer and realize flexible dynamic memory management. However, the linked list loses the advantage of random array reading. At the same time, due to the increase of the pointer field of the node, the space overhead of the linked list is relatively large.

There are many different types of linked list: one-way linked list, two-way linked list and circular linked list.

subject

Two non empty linked lists are given to represent two non negative integers. Their respective digits are stored in reverse order, and each node can only store one digit.

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

You can assume that neither of these numbers starts with 0 except for the number 0.

Example 1:

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

Example 2:

Input: (3 - > 7) + (9 - > 2)
Output: 2 - > 0 - > 1
 Cause: 73 + 29 = 102

Realization

C# language

Idea: imitate the addition operation we learned in primary school. If the sum of the bits exceeds decimal one, if there is carry in the sum of the tens, then carry will be added, and so on.

  • Status: Pass
  • Execution time: 144 ms, beating 97.98% of users in all C ා submissions
  • Memory consumption: 26.7 MB, beating 5.07% of users in all C 񖓿 submissions
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution 
{
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) 
    {
        ListNode result = new ListNode(-1);
        ListNode l3 = result;
        int flag = 0;
        while (l1 != null && l2 != null)
        {
            int a = l1.val;
            int b = l2.val;
            int c = a + b + flag;
            l3.next = new ListNode(c%10);

            flag = c >= 10 ? 1 : 0;
            l1 = l1.next;
            l2 = l2.next;
            l3 = l3.next;
        }
        
        while (l1 != null)
        {
            int a = l1.val + flag;

            l3.next = new ListNode(a%10);

            flag = a >= 10 ? 1 : 0;
            l1 = l1.next;
            l3 = l3.next;
        }
        
        while (l2 != null)
        {
            int b = l2.val + flag;

            l3.next = new ListNode(b%10);
            flag = b >= 10 ? 1 : 0;
            l2 = l2.next;
            l3 = l3.next;
        }

        if (flag == 1)
        {
            l3.next = new ListNode(flag);
        }
        return result.next;        
    }
}

Python implementation

  • Execution result: passed
  • Execution time: 108 ms, beating 16.54% of all Python submissions
  • Memory consumption: 13.6 MB, beating 8.73% of all Python submissions
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        result = ListNode(-1)
        l3 = result
        flag = 0
        while l1 is not None and l2 is not None:
            a = l1.val
            b = l2.val
            c = a + b + flag
            l3.next = ListNode(c % 10)
            flag = 1 if c >= 10 else 0
            l1 = l1.next
            l2 = l2.next
            l3 = l3.next

        while l1 is not None:
            a = l1.val + flag
            l3.next = ListNode(a % 10)
            flag = 1 if a >= 10 else 0
            l1 = l1.next
            l3 = l3.next

        while l2 is not None:
            b = l2.val + flag
            l3.next = ListNode(b % 10)
            flag = 1 if b >= 10 else 0
            l2 = l2.next
            l3 = l3.next

        if flag == 1:
            l3.next = ListNode(flag)

        return result.next

source

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

Activities in the past

LSGO software technology team will regularly carry out deliberate practice activities to improve programming skills, hoping that everyone can participate in deliberate practice and learn together!

I am a lifelong learner "laoma", a middle-aged uncle who has long practiced the concept of "group learning".

I advocate sharing and long for growth. I founded "LSGO software technology team" in 2010 and joined the famous open-source organization "Datawhale" in China. I am also a member of "Dre@mtech", "intelligent robot research center" and "big data and Philosophy Social Science Laboratory".

May we learn, progress, accompany and grow together.

Background reply "Search Search", random access to electronic resources!
Welcome to scan QR Code:

585 original articles published, 333 praised, 1.3 million visitors+
His message board follow

Tags: Python Programming Lambda Big Data

Posted on Tue, 10 Mar 2020 03:45:51 -0700 by vornn