Leetcode 989. 数组形式的整数加法(简单)
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的相关知识
- 关键字eval用来提取字符串中的表达式, 然后返回表达式的值. 示例:
print(eval("[1, 2, 3]")) # [1, 2, 3]
print(eval("pow(2, 3)")) # 8
其中pow(2, 3)的意思是计算2的3次方,结果为 8
- 列表推导式
print([i for i in range(5)]) # [0, 1, 2, 3, 4]
这样写法相当于:
arr = []
for i in range(5):
arr.append(i)
print(arr)
- 数组 -> 字符串(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 不理解的地方 可以一起交流~
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-09-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录