Leetcode 989. 数组形式的整数加法(简单)

题目链接

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

思路讲解

官方示例: 输入：A = [1,2,0,0], K = 34 输出：[1,2,3,4] 解释：1200 + 34 = 1234

我一开始就根据题目示例中的思路去想, 然后写出了解法一

解法一:

1.将 数字型数组 -> 字符串型数组

2.将数组中的字符串拼接, 用eval函数取出字符串中的数字 和 k 取和，然后转为字符串

3.将字符串 -> 数字型的数组

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]

复制

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)

python的相关知识

1. 关键字eval用来提取字符串中的表达式, 然后返回表达式的值. 示例:

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

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

其中pow(2, 3)的意思是计算2的3次方,结果为 8

复制

1. 列表推导式

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

这样写法相当于:

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

复制

1. 数组 -> 字符串(join的用法)

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

复制

上面的解法一其实是一种取巧的做法, 正规的做法应该是用 进制的思路 去做，如解法二.此解法是从题解中看到的, 按照大佬的思路理了一下

解法二

题目思路

本题思路可类比2数相加的竖式计算(满10进1), 使用的算法思想是双指针法 !

1.定义2个指针, 分别指向 num 和 k 的末尾

2.从后往前遍历,只要最长的字符串有值就一直遍历.遍历过程中,如果较短的 字符串 or 列表 无对应索引, 则用数值0代替

3.最后判断一下carry变量，如果carry > 0，代表需要手动添加一次1(因为可能上面的最后一次判断中,carry>0,然后循环就终止了)

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   # 是否需要进一位的标识符

        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]

复制

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(1)

python的相关知识

• 列表翻转

a = [1, 2, 3, 4]

方式1:
print(a[::-1])  # 本题使用的翻转方法

方式2:
a.reverse()  # 注意使用reverse,更改的是原数组中元素的顺序!
print(a)

方式3:
print(list(reversed(a)))  # ['4', '3', '2', '1']  
# 注意reversed的结果是一个 迭代器 对象, 需要使用list()函数转为列表
print(a) # ['1', '2', '3', '4']  # 使用reversed不会影响到原来的列表

复制

• 取余 + 获取除数

# 取余数
a = 12
print(a % 10) # 2


知识点: 
//表示整数除法
/表示 浮点数除法，返回浮点结果


# 获取除数(整数): //
b = 25
print(25//4) # 6

# 获取除数(浮点数): /
c = 25
print(c/4) # 6.25

复制

以上就是整理的 每日leetcode 系列的开篇.

其中每种解法后面的时间复杂度, 空间复杂度分析可能不太准确，仅供参考.

另外对本题有 不同的见解 or 不理解的地方可以一起交流~