Leetcode 415. string addition and 43. string multiplication

These two topics are about string Class related exercises . meanwhile , This is also a topic about the operation of large numbers , Let's analyze it ！

String addition

difficulty Simple OJ link

Let's take an example 2 To explain this idea ：

First , We use two subscripts to point to the last position of two strings . Then add these two numbers 6+7=13, So here we are going to enter 1.

And then 3 Insert the header into a new string . Then move the subscript forward one bit .

5+7=12,12 Plus the number on the carry 12+1=13,13 Then you have to carry , Carry or 1. We put 3 Insert the header into the new string , Then the subscript moves forward one bit .

here , A string ends . But it's not over yet , We regard the remaining positions as 0. That is to say 4+0+1( carry )=5.5 Less than 10 There is no need to carry , Let's change the carry to 0. And then we put 5 Insert the header into the new string .

At this point, the number of both strings ends , Is the real end .

that , Let's look at the writing of this problem ：

First , We need to set the carry to 0, Because there is no carry when two numbers are added at the beginning . here , Why use the trinocular operator ？ as a result of ： There may be a string that ends first , If it's over , If we still go to get the position there, we will cross the border . So if one ends first , We'll give it directly 0. And here we subtract one character 0, If we don't subtract characters 0, So we take characters and numbers . image ’1’ Of ASCII The value is 49, And the number we need is 1, So subtract one character 0.

If the sum is greater than 9, Then let's set the carry to 1, If not, change to 0.

Then we insert each character header . At this time, we also need to put characters 0 Add it .

But there is still a problem ： Is that if ’9’+'1’ This string , According to the above formula 9+1=10, It is greater than 9 Of , Then subtract 10,ret=0,carry=1. Alphabet character 0 Insert into the string , then end1–,end2–, The cycle is over . At this time, there is only one in the string 0, No, 1. So we have to judge again .

But the time complexity of each head insertion is O(N^2), So the time will be very slow . We can write like this ：

Let's directly insert , When all the numbers are inserted . Let's turn it all over again . This time complexity is O(N).

String multiplication

difficulty Simple OJ link

Thinking process ：
Let's take the following data as an example ：

According to multiplication we learned in primary school .47=28, We are going to put 8 leave , Then enter 2. But here , Let's not carry . But the 28 Keep it . Back 37=21 Don't carry and keep it . All calculations are not carried .

then , We add up all the numbers in each column .

here , Let's go back and forth , Carry one by one .

Let's start step by step ：
First step ： If one of these two strings is an empty string , An empty string is returned directly .

The second step ： Open up an array , Accumulate the data each time into the array .

Here we first calculate the length of two strings m,n. And how big should this array be ？ for instance ：100100=10000, Multiply two three digits , The smallest is 5 digit .999999=998001, Multiply two three digits , The biggest thing is 6 digit . therefore , We will open up m+n Space is enough to put . Because the smallest is m+n-1, The biggest is m+n, Then we initialize the space inside 0.

The third step ： The numbers of two strings are multiplied by each bit from the back to the front , Then add it to the array .

Some students here may not know why i+j+1？

This is the subscript position of the two strings .

This is the display of the subscript position of the data in the array . We see 4 * 7=28,28 In the array, the subscript is 6 The place of , At this time i by 3,j by 2, therefore 2+3+1=6. image 3*7=21, In the array, the subscript is 5 The place of , here i by 2,j by 2, therefore 2+2+1=5. The same is true for others .

Step four ： Start each carry of the data in the array .

Step five ： Insert the data in the array into the new string from the beginning to the end .

Some students may not know what this means ？ This is to judge whether there is data at the beginning of the array . If it starts with 0, Description no carry to the beginning . We just need to subscript from the array 1 Where the tail begins . If not 0, It means that there is carry to the beginning , We need to subscript from the array to 0 Where the tail begins .

Okay , Let's finish these two questions . If you think it helps , You can like it and collect it . Thank you. ！！！