This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
- 🤟 copyright: this article by [IT learning diary] original, need to reprint please contact the blogger
- 💬 If the article is helpful to you, welcome to follow, like, bookmark (click three links) and subscribe
One, foreword
The first two papers introduced you to the logic of deriving time complexity and space complexity, and we have also formally entered the world of algorithms by solving the “sum of two numbers” problem. As the saying goes, a mountain is more difficult than a mountain. The Boss we met this time is not simple. If you want to pass the game, you need to turn your mind and pay attention to the Boss’s “trap”.
Second, topic introduction
Boss feature: You are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and only one digit can be stored per node.
Customs requirements: please add the two numbers and return a linked list representing the sum in the same form.
Tip: You can assume that neither of these numbers will start with 0, except for the number 0.
Examples of customs clearance:
The sample1: Input: l1 = [2.4.3], l2 = [5.6.4] output: [7.0.8] :342 + 465 = 807The sample2: Input: l1 = [0], l2 = [0] output: [0] example3: Input: l1 = [9.9.9.9.9.9.9], l2 = [9.9.9.9] output: [8.9.9.9.0.0.0.1]
Copy the code
Clearance reminder:
- The number of nodes in each linked list is in the range [1, 100]
- 0 <= Node.val <= 9
- The question data ensures that the numbers represented in the list do not contain leading zeros
Three, the topic interpretation
To solve the Boss, we need to find its weakness first. Through the Boss description, we can find the following characteristics:
-
All the elements in the linked list are in reverse order. For example, if the value 123 is stored in the linked list, it is: 3-1
-
Each element in the linked list can store only one digit, and if the element values add up to more than 10, the Boss will evolve, rounding the values to the preceding number, and so on. In the figure above, the value of the second element of the two lists is 4 and 6 respectively. When they are added together, they will get 10. At this point, the Boss evolves, keeps 0 and carries forward by 1, so the sum of the third element is: 3+4+1 = 8.
Four, customs clearance method 1: crowd tactics
Knowing the characteristics of the Boss, the first thing we can think of is the crowd tactic. No matter how powerful the technical Boss is, we can wear down his health through a large number of people, and finally defeat him. Here are the specific solutions:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// List header element
ListNode head = null;
// The last element in the list
ListNode tail = null;
int carry = 0;
// If the list still has a value, add the two numbers (as long as the Boss is alive, continue after resurrection)
while(l1 ! =null|| l2 ! =null) {
int l1Val = l1 == null ? 0 : l1.val;
int l2Val = l2 == null ? 0 : l2.val;
// Get the sum of the corresponding elements of the list, if more than 10 carry
int sum = l1Val + l2Val + carry;
// Determine whether carry is required
carry = sum / 10;
// Set the header element
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
// Always point tail to the last element of the list for the next operation
tail = tail.next;
}
// If the list still has a value, point the element to the next one for the rest of the calculation
if(l1 ! =null) {
l1 = l1.next;
}
if(l2 ! =null) { l2 = l2.next; }}// If the last element needs to be carried, tail points to the carried value
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
Copy the code
Execution Result:
Sure enough, even though the Boss is strong, he can’t stand the rogue of the crowd tactics, and finally the Boss still falls at the foot of the powerful player. However, some people complained that it would take so many players to complete the Boss, if the number of players is not enough, is there any other solution that only requires a few players to complete the Boss?
At this time, the resourceful little honesty thought of a plan, we can learn from the idea of wheel warfare, the designated number is divided into different key teams, constantly to grind with the Boss, so that the Boss can finally customs clearance, we all agree with the idea of small honesty, the following specific look at how to achieve it.
5. Customs Clearance mode 2: Wheel battle (recursive idea)
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Get the values in the linked list
int l1Val = l1 == null ? 0 : l1.val;
int l2Val = l2 == null ? 0 : l2.val;
// Get the sum of the corresponding elements of the list, if more than 10 carry
int sum = l1Val + l2Val;
ListNode node = new ListNode(sum % 10);
int carry = sum / 10;
if(l1.next ! =null|| l2.next ! =null || carry > 0) { l1 = l1.next ! =null ? l1.next : new ListNode(0);
// New ListCode(0) is used because l1 has been used up, and L2 has not been used up, and l1 has been added to l1, so l1 points to a node with a value of 0.l2 = l2.next ! =null ? l2.next : new ListNode(0);
l1.val = l1.val + carry;
// Use recursion
node.next = addTwoNumbers(l1, l2);
}
return node;
}
Copy the code
Execution Result:
6. Sum up experience
We can both solve the Boss, what is the difference in time complexity between them? Let’s derive their time complexity together.
6.1 Derivation of time complexity
Through two scheme of the code above, we will find that with the increase of list elements (the size of the problem), we need to loop or the number of recursive will also increase, problem size and circular or recurrence relation is f (n) = n, way is derived through the big O meter method, we can draw time complexity of these two schemes are as follows: O (Max (m, n)).
Max (m,n) indicates that the longest value of the two lists is the input size.
6.2. Application of algorithm in actual business
In the above case, the first scheme uses the most common while loop, which is most commonly used in ordinary business in arrays or linked list key elements comparison, sorting (e.g., bubble, selection sort, etc.).
In the second case, we use recursion to solve the problem. In ordinary business, the most common use of this idea is to query the menu function of the system. The menu is nested layer by layer, which just conforms to the recursion idea.
Write at the end
Problems may be infinite, but there are endless ways to solve them. The purpose of brushing LeetCode is not only to cope with the interview, but also to cultivate the way of thinking when we encounter problems and solve them.
One person can go fast, but a group of people can go farther! In study, staying together is the best way. We can make faster progress by learning from each other. Looking forward to learning, communicating and growing together with you!