What to save You, my interview — Swipe Leetcode from zero (No.002)

Write in front:

Xiaozhan has always felt that his programming ability is not strong, want to brush on the Internet, but afraid that he can not adhere to. Do you want to find someone to brush the questions together with your friends and Xiaozhan? Welcome to brush leetCode regularly with Xiaozhan, update a problem every Monday and Friday, and get a thorough understanding of each problem. Welcome to multiple solutions to a problem, looking for the best solution! Welcome to share your thoughts in the message area

Previous review :(attached is the python version of the frequently used sorting algorithm) the topic of the first issue, some friends share a new and better method, please read the top comment of the previous period.

(No.001) Swipe Leetcode from zero

Sorting algorithms for Programmer Interviews (PART 1)

Sorting algorithms for Programmer interviews

No.2 Add Two Numbers

The original:

Two linked lists store non-negative numbers. Both lists store numbers in reverse order (ones, tens, hundreds…). Ask to add two linked lists and return them as linked lists.

Such as:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.Copy the code

So before the analysis, first review the concept of the basic knowledge of linked list (big guy skipped, mainly is the basic data structure of Xiaozhan is not good)

① What is a linked list?

So for example, when we store a big wave of data, we use arrays a lot of the time, but when we do an insert, it’s a lot of trouble, we have a bunch of data 1,2,3,5,6,7 and we want to insert 4 between 3 and 5. What do we do with an array? Of course I’m going to go back one bit after 5, and then I’m going to insert 4, which is very cumbersome and inefficient, but if I use a linked list, I’m just going to insert 4 between 3 and 5.

A linked list consists of nodes connected as follows:

The Data section (data domain) stores data, and the next section (pointer domain) stores Pointers to the next node. Any linked list that starts with a header pointer head may not store data in its data field.

② Basic operation of linked list?

Initialize list, list length, Insert, delete, Add, find, reverse order. Specific will not unfold ~

How many of you have this first reaction? Raise your hand:

def addTwoNumbers(self, l1, l2):
        """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """
        len_max = max(len(l1),len(l2))
        carry = 0 # represents a carry, for example 9+8 = 17, carry = 1, and the default carry is 0
        for i in range(len_max):
            l3[i] = l1[i] + l2[i] + carry
            if l1[i] + l2[i] > 10:
                carry = 1
            else:
                carry = 0
        return l3
Copy the code

The above should be quite easy to understand, I won’t go to the specific (anyway, this code is wrong)

What went wrong? If you love thinking, you should note that there is no big problem with the way of thinking. After all, we have learned about addition. There are mainly the following small problems:

★ Lists, unlike list arrays, cannot be length by len()

★ Addition calculation thinking is not comprehensive, we took into account the existence of carry, but did not take into account the length of the linked list is not equal, that is, two addend digit is not equal (such as three digit plus five digit)

After reflecting on the error code, we considered to split the problem into two cases. Taking three digits plus five digits as an example, the first three digits and the first three digits were processed according to our existing ideas, while the fourth and fifth digits were another case. Specifically: within the range of the first three digits, the corresponding bits are added to the low carry when adding operations; The fourth digit and the fifth digit can only be carried with the low digit (or understood as another three-digit high digit 0). The specific code is implemented as follows:

 def _addTwoNumbers(self, l1, l2):
        """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """
        # specify to the list head node
        p = dummy = ListNode(-1)
        # carry flag, 1 if there is a carry in the low position, 0 by default
        carry = 0
        # when the same position of two lists is not empty at the same time (i.e., the lower three digits of James's example)
        while l1 and l2:
            # p.ext refers to l1.val refers to the corresponding data
            p.next = ListNode(l1.val + l2.val + carry)
            The division and modulo operations obtain the tens bits of P. ext
            carry = p.next.val / 10
            p.next.val %= 10
            p = p.next
            l1 = l1.next
            l2 = l2.next
        res = l1 or l2 # or operation corresponds to the high order example (fourth and fifth place)
        while res:
            p.next = ListNode(res.val + carry)
            carry = p.next.val / 10
            p.next.val %= 10
            p = p.next
            res = res.next
        if carry:
            p.next = ListNode(1)
        return dummy.next# return the list
Copy the code

Do you feel finished? After typing the code, I felt comfortable, but… Running found a little error, here xiaozhan first not revealed, next period xiaozhan will tell you where the above procedure needs to be adjusted to the next can oh, find a partner to leave your opinion in the message area, the first one to answer the right red envelope oh! And the error elimination effect is quite impressive:

If you think the article is good, welcome to forward all kinds of posture oh, let more people participate in our punching team oh! At the request of friends, attach a group qr code, declined all kinds of promotion [xiaozhan himself will not send in addition to the leetcode punched-out public article], pure punched-out discussion group, thank you for your cooperation! Has more than 100 people, can be added from the public number xiaobian wechat invited into the group oh!

【 xiaozhan learn Python】 Oh!

​