LeetCode HOT 100 (01)

Not good enough, hair amount is still much, dental laboratories, can become Buddha.

The importance of algorithm is self-evident. No matter you are a researcher or a popular IT worker recently, you should have certain algorithm ability, which is also a necessary part of the interview. The demonstration of algorithm foundation can often make the interviewer’s eyes shine, which is also an important factor to stand out from most competitors.

However, most people pay more attention to their practical operation ability, focusing on the realization of functions, but ignore the improvement of algorithm ability. Sometimes different algorithms are used to solve the same problem, but the difference in operation efficiency is quite large. After all, we still need to think from the perspective of the customer, and it would be best to bring the user more extreme experience.

All methods are empty, cause and effect is not empty. Taoye was also reluctant to spend too much time on algorithms before, and the algorithm foundation is quite weak. It was not until I entered a new stage of learning that I began to realize the fact of my “food” in the face of various “torture” from my tutor and comparison with others around me.

Talking about this, shed no technical tears!!

This topic is the second question of LeeTCode HOT 100. The difficulty is medium, involving the knowledge of linked lists.

For as long as I’ve been in Python, I haven’t used linked lists, nor have I been able to manipulate linked lists with Pointers. I used to brush some linked list related algorithms when I was preparing for exam 408 and learning C. At the beginning, I didn’t know how to start Python and operate linked lists.

After searching for information, we found that when we operate the linked list, we actually encapsulate it into an instance object, and the instance object stores the related information of the node (in fact, similar to C). But unlike C or C++, Python has no Pointers and therefore no pointing operations, so the overall structure of a linked list is somewhat different from that of C or C++. It means something like this:

You can think of it as a kind of Russian nesting doll.

Note: the meaning is still the same, but the understanding is different.

Now, let’s look at this problem.

Title: Add two numbers

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

If we add these two numbers together, a new linked list is returned to represent their sum.

You can assume that neither of these numbers will start with 0, except for the number 0.

The sample

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

Train of thought

As mentioned earlier, in Python, linked lists can be understood as a kind of nesting doll. You can input two linked lists and output a new one, and the generation process of each node in the new list is basically the same. Therefore, we preliminarily decide to solve this problem by recursion.

Of course, recursion can solve any problem that non-recursion can solve, just by replacing a recursive function call with a loop. So here are two ways to do it.

  • Method one: recursion

In the example given, the two lists are of the same length, but what the question means is that the two lists are of any length. Therefore, in order to improve the “generalization performance” of the algorithm, on the premise of inputting two linked lists with different lengths, we need to unify them, that is, we need to do a complement 0 processing for the short linked list. Adding 0 does not affect the summation operation, but it is convenient for us to judge the cut-off recursion.

This way of handling in math is quite common, for instance in time to get the most value, we often use the mean inequality, but the numerical dimension in the title may not be clearly meet the average can’t type, so often used an d the operation of the expanding, cleverly will subject to be near average inequality, which simplifies the solution on the theme, Like the clever answer to the following question:


Topic: a a , b , c ∈ R + Verification: a b c 3 Or less 27 ( a + b + c 5 ) 5 A ^3≤27(\frac{a+b+c}{5})^5

Solution: a + b + c 5 = a + b + c 3 + c 3 + c 3 5 p a f. b f. c 3 f. c 3 f. c 3 5 = a b c 3 27 5 Solution: \ frac {a + b + c} {5} = \ frac {+ a + b \ frac {c} {3} + \ frac {c} {3} + \ frac {c} {3}} {5} \ or SQRT [5] {\ bullet b \ bullet \ frac {c} {3} \ bullet \frac{c}{3}\bullet \frac{c}{3}}=\sqrt[5]{\frac{abc^3}{27}}

And then finally, you take the left and right to the fifth power, and you multiply it by 27.

Let’s go back to the algorithm.

Since we are asked to find the sum of units corresponding to the linked list, then there must be a carry involved, we might as well express carry. At this point, it is not difficult to imagine that each recursion requires three parameters, namely the value in the first list, the value in the second list, and the value of the last carry (non-0 or 1).

As mentioned earlier, in Python, a list is an object that has two attributes, val and next, and next itself represents a list object. So the first and second arguments passed in by our recursive method can be retrieved using the current list node.

** Before, we have already processed the linked list, which means that whether the two lists you input are of the same length or not, we have processed them with the same length. So we jump out of recursion when all three arguments we pass are False. For example: 1. Enter two empty lists and a parameter with a carry of 1 to indicate that a carry has been generated and we need to process it instead of jumping out of recursion. 2. The input value of a linked list node is 5, while the other node is None and carry is 0. At this point, we still need to sum up. As for other possibilities, you can think for yourself.

Summation processing:

  1. Find the sum of the current value and carry of two linked lists, and perform one on 10divmodOperation.Description:PythondivmodReturns a tuple with the first value to carry and the second value to mod, for exampledivmod(13, 10) = (1, 3). ** Note: ** During the summation process, it is possible that the current node is None, in which case the node will need to be changed tovalueThe values are summed as 0.
  2. Instantiate a linked list, that is, our target return list, whose value is the mod above. Note: the value in the linked list is the reverse of the actual value.
  3. The value corresponding to the next attribute of result is itself a linked list, and to assign it, we need to call a recursive method. ** After the above process, the current value in the list has been processed, this time needs to process the next value of the list, that is, the next node as a parameter for a recursion. But the thing to consider here is that if our current node is empty, that is, the current list has been traversed, we need to pass None to the recursive function.

Related codes:

class Solution: def recursion(self, list_node1, list_node2, carry): If (list_node1 == None) and (list_node2 == None) and (carry == 0); Return None # Sum of two node values and carry values. If None is passed, value is set to 0. Sum_number = (list_node1. Val if list_node1 else 0) + (list_node2. Val if list_node2 else 0) + carry # As a judgment for the next recursion. Carry, value = divmod(sum_number, 10); Next = self. Recursion (list_node1. Next if list_node1 else None, List_node2. Next if list_node2 else None, carry) return result # def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: return self. Recursion (l1, l2, 0) #Copy the code
  • Method two: non-recursive

The idea of non-recursion is similar to recursion, except that in addition to returning the result list, you need to create a new list for the loop.

class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: # initial node where result is the result list and temp_node is used for loop traversal, Result = temp_node = ListNode(0) carry = 0 If None is passed in, then value is set to 0. If None is passed in, then value is set to 0. Sum_number = (l1.val if L1 else 0) + (l2.val if l2 else 0) + carry # l1.val if l2 else 0 L1 = l1. Next if L1 else None; Next if l2 else None # generate a new carry value for the next recursive judgment. Carry, value = divmod(sum_number, 10) # assign temp_node to result list. Next = ListNode(value); temp_node = temp_node.next return result.nextCopy the code

In general, the idea of non-recursive expression is similar to that of recursive expression.

The result node is only used for initial and final returns, but not for the core while loop. Why return a normal result list?

This is mainly because our initialized result and temp_node are already assigned to the new list, where val is 0, the next attribute is None, and the memory location is fixed. The initial result and temp_node values are equal and refer to the same memory address, so we simply extend the temp_node. The address of result remains the same, and the address of the next node referred to by result changes with the change of the temp_node.

Note that the memory address of result remains the same from start to finish. The initial memory address of result is the same as that of temp_node, except that the memory address of result remains the same as that of temp_node. We can do this by simply testing the following operations:

I don’t know if I made it clear.

Also did not know everybody see an officer to understand?

If you don’t get it, I strongly suggest you revisit it. It’s a very important place to think about.

  • The last

While browsing the discussion board, I saw another solution, I feel this algorithm is written quite elegant, here to share the next.

""" class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: head = curr = ListNode() carry = val = 0 while carry or l1 or l2: val = carry if l1: l1, val = l1.next, l1.val + val if l2: l2, val = l2.next, l2.val + val carry, val = divmod(val, 10) curr.next = curr = ListNode(val) return head.nextCopy the code

So this is the same idea as the non-recursive one, except when you’re trying to figure out the sum, it’s a summation, not a one-time sum. Curr. Next = curr = ListNode(val) curr. Next = curr = ListNode(val)

curr.next =ListNode(val)
curr = curr.next
Copy the code

Taoye does not know why this is the order of assignment, but it should be curr = ListNode(val) followed by curr.next = curr? But after testing, the above two lines of code are correct. I don’t know why, but I’ll come back to them later.

I am Taoye, a postgraduate student. I love studying and sharing, and I’m keen on all kinds of technologies. In my spare time, I like playing chess, listening to music and chatting about animation. I hope to record my growth process and life bit by bit with this opportunity, and also hope to make more like-minded friends in the circle.

Recommended reading:

Taoye infiltrated into a black platform headquarters, the truth behind it is very afraid of “Tai Hua Database” -SQL statement execution, what did the bottom of the small action? Over the years, we’ve played Git, Hexo+Github is a deep learning environment based on Ubuntu+Python+Tensorflow+Jupyter Notebook The correct way to open ElasticSearch, Kibana, logStash