Leetcode 989. Integer addition in array form (simple)

Leetcode 989. The addition of integers in the form of arrays ( Simple )

Topic link

https://leetcode-cn.com/problems/add-to-array-form-of-integer/

Train of thought explanation

The official sample : Input ：A = [1,2,0,0], K = 34 Output ：[1,2,3,4] explain ：1200 + 34 = 1234

From the beginning, I began to think according to the ideas in the topic examples , Then write the understanding method 1

Solution 1 :

1. take Numeric array -> String array

2. Concatenate the strings in the array , use eval Function to fetch a number from a string and k Sum up , Then it is converted to a string

3. The string -> Numeric array

code for python

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        list_str = [str(i) for i in num]
        final_str = str(eval("".join(list_str)) + k)
        return [int(j) for j in final_str]

Copy

Complexity analysis

• Time complexity : O(N)
• Spatial complexity : O(N)

python Knowledge about

1. keyword eval Used to extract expressions from strings , Then return the value of the expression . Example :

print(eval("[1, 2, 3]"))  # [1, 2, 3]

print(eval("pow(2, 3)"))  # 8  

 among pow(2, 3) It means to calculate 2 Of 3 Power , The result is  8

Copy

1. List derivation

print([i for i in range(5)])  # [0, 1, 2, 3, 4] 

 This is equivalent to :

arr = []
for i in range(5):
  arr.append(i)
print(arr)

Copy

1. Array -> character string (join Usage of )

a = ['1', '2', '3', '4']
print("".join(a))  # 1234

Copy

The above solution 1 is actually a trick , The normal practice should be to use The idea of binary To do , For example, solution 2 . This solution is seen from the problem solution , According to the thought of the boss

Solution 2

Topic ideas

The idea of this question can be compared with 2 A vertical calculation of the addition of numbers ( full 10 Into the 1), The algorithmic idea used is two finger needling !

1. Definition 2 A pointer to the , Point to respectively num and k At the end of

2. Go back and forth , As long as the longest string has a value, it will be traversed . During traversal , If shorter character string or list No corresponding index , Then use numerical value 0 Instead of

3. Finally, judge carry Variable , If carry > 0, Delegates need to be manually added once 1( Because maybe in the last judgment above ,carry>0, Then the loop ends )

code for python

from typing import List


class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        len_num = len(num) - 1
        len_k = len(str(k)) - 1
        arr = []
        carry = 0   #  Whether to need a carry in identifier 

        while len_num >= 0 or len_k >= 0:
            x = num[len_num] if len_num >= 0 else 0
            y = int(str(k)[len_k]) if len_k >= 0 else 0
            total = x + y + carry
            carry = total // 10
            arr.append(total % 10)

            len_num -= 1
            len_k -= 1
        if carry:
            arr.append(1)
        return arr[::-1]

Copy

Complexity analysis

• Time complexity : O(N)
• Spatial complexity : O(1)

python Knowledge about

• Flip the list

a = [1, 2, 3, 4]

 The way 1:
print(a[::-1])  #  The flipping method used in this question 

 The way 2:
a.reverse()  #  Pay attention to reverse, What is changed is the order of the elements in the original array !
print(a)

 The way 3:
print(list(reversed(a)))  # ['4', '3', '2', '1']  
#  Be careful reversed The result is a   iterator   object ,  Need to use list() Function to list 
print(a) # ['1', '2', '3', '4']  #  Use reversed Will not affect the original list 

Copy

• Remainder + Get divisor

#  Take the remainder 
a = 12
print(a % 10) # 2


 Knowledge point : 
// Represents integer division 
/ Express   Floating point division , Return floating point result 


#  Get divisor ( Integers ): //
b = 25
print(25//4) # 6

#  Get divisor ( Floating point numbers ): /
c = 25
print(c/4) # 6.25

Copy

That's what it's all about everyday leetcode The beginning of the series .

After each of these solutions Time complexity , Spatial complexity The analysis may not be accurate , For reference only .

In addition, I have Different opinions or What I don't understand You can talk to each other ~