- 2020-08-12 11:02
*views 3*- Algorithm questions

<> Title Description

My first thought was this ： Traverse the two linked lists , Take these two numbers back , And then do the operation , The results of the calculation are taken out in reverse order according to the requirements , Make a list . In fact, it should be feasible ,

<> First attempt

however ：

I used one of the numbers I returned int Type , But Dangdi 1559 Use cases , The number of reverts has exceeded int Type …… Forced by helplessness , I changed the type to long type , I thought it would be enough , result ：

The first 1560 Use cases , It's been a long time , There seems to be 30 position ,long The type range seems to be in the 20 Right and left , worry , Do you want to continue to change double Type ? What if he gets a few hundred ? Change the way of thinking , And it's time to change double It doesn't seem to work .

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { double l1Num =

getNum(l1); double l2Num = getNum(l2); double sum = l1Num + l2Num; ListNode temp

= new ListNode((int) (sum%10)); ListNode re = temp; sum = Math.floor(sum/10);

while (sum > 0) { int each = (int) (sum % 10); System.out.println(each);

ListNode listNode= new ListNode(each); temp.next = listNode; temp = listNode;

sum= Math.floor(sum/10); } return re; } public static double getNum(ListNode l1)

{ double sum = 0; int count = 0; while (l1 != null) { int val = l1.val; sum +=

val*Math.pow(10,count); l1 = l1.next; count++; } System.out.println(sum); return

sum; }

<> Changing ideas

After the previous ideas were rejected , Just think ： Why do you want to recover these two numbers ? After recovery, we have to traverse again . Then there's no recovery , Traverse these two linked lists directly , In the process of traversal , Add up the numbers of the corresponding positions .

This idea is feasible , But consider the boundary and carry cases , I follow this line of thinking , He wrote the first edition , Then various submit debugging , Finally, it passed

boolean carry = false; // Carry flag , Pay attention to reset ArrayList<Integer> l1ArrayList = new

ArrayList<>(); while (l1 != null) { l1ArrayList.add(l1.val); l1 = l1.next; } int

size1= l1ArrayList.size(); ArrayList<Integer> l2ArrayList = new ArrayList<>();

while (l2 != null) { l2ArrayList.add(l2.val); l2 = l2.next; } int size2 =

l2ArrayList.size(); int firstSum = l1ArrayList.get(0)+l2ArrayList.get(0);

ListNode temp= new ListNode(firstSum%10); ListNode re = temp; if (firstSum >=10)

{ carry = true; if (size1 ==1 && size2 == 1) { temp.next = new ListNode(firstSum

/10); } } for (int i = 1,j = 1; i<size1 || j<size2; i++,j++) { int num1 ; if (i

>= size1) { num1 = 0; } else { num1= l1ArrayList.get(i); } int num2 ; if (j >=

size2) { num2 = 0; } else { num2 = l2ArrayList.get(j); } int sum = num1 + num2;

ListNode eachTemp= new ListNode(sum%10); if (carry) { if (sum%10 +1 < 10) {

eachTemp= new ListNode(sum%10+1); carry = false; } else { eachTemp = new

ListNode(0); carry = true; } } temp.next = eachTemp; temp = eachTemp; if (sum >=

10) { carry = true; } } if (carry) { temp.next = new ListNode(1); } return re;

The effect is not very good

<> optimization

I know , I'm a fool , Why should I traverse two linked lists and put them into the collection first , From the set ? It's OK to go directly when traversing ?? Don't you take off your pants and fart

boolean carry = false; // Carry flag , Pay attention to reset int firstNum = l1.val + l2.val; ListNode

temp= new ListNode(firstNum%10); ListNode re = temp; l1 = l1.next; l2 = l2.next;

if (firstNum >= 10) { carry = true; if (l1 == null && l2 == null) { temp.next =

new ListNode(firstNum/10); } } while (l1 != null || l2 != null) { int num1; if (

l1== null) { num1 = 0; } else { num1 = l1.val; } int num2; if (l2 == null) {

num2= 0; } else { num2 = l2.val; } int sum = num1 + num2; ListNode eachTemp =

new ListNode(sum%10); if (carry) { if (sum % 10 < 9) { eachTemp = new ListNode(

sum%10+1); carry = false; } else { eachTemp = new ListNode(0); carry = true; } }

temp.next = eachTemp; temp = eachTemp; if (sum >= 10) { carry = true; } if (l1

!= null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } if (carry) { temp

.next = new ListNode(1); } return re;

It's not necessary to traverse the linked list twice , Submit results

Sure enough , The effect is obviously improved , I guess I was out of my head . What I thought at first was , Because the title reverses the number , So it can't be traversed directly , Traverse from the tail , And because the single linked list cannot be traversed in reverse order , That's why we first traverse in positive order , Stored in the collection . Think more, think more

<> Big guy idea

The idea given by the government is the same as the one above , But he's very good at details , The amount of code is a quarter of mine , The function is the same . The main details are ：

* He used a dummy node , Used to handle head and tail nodes , And my separation is special

*

He used one 0 and 1 To handle the carry problem , And I used a Boolean tag . Use numeric type , You can add this number directly , The boolean type is used instead , Need to judge , Then decide whether to add it or not , It increases the workload invisibly .

code

ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, curr =

dummyHead; int carry = 0; while (p != null || q != null) { int x = (p != null) ?

p.val : 0; int y = (q != null) ? q.val : 0; int sum = carry + x + y; carry =

sum/ 10; curr.next = new ListNode(sum % 10); curr = curr.next; if (p != null) p

= p.next; if (q != null) q = q.next; } if (carry > 0) { curr.next = new ListNode

(carry); } return dummyHead.next;

excellent !!!

Technology

Daily Recommendation

views 26

views 2

©2019-2020 Toolsou All rights reserved,

One is called “ Asking for the train ” A small village Finally got the train Spring Boot Lesson 16 ：SpringBoot Implementation of multithreading with injection class Chrome OS, For programmers and Windows What does it mean ? Internet Marketing JAVA Convert a string to a numeric type I've been drinking soft water for three years ? What is the use of soft water and water softener You don't know ——HarmonyOS Talking about uni-app Page value transfer problem JavaScript Medium Call and ApplySparkSQL Achieve partition overlay write Character recognition technology of vehicle license plate based on Neural Network