43. Multiply Strings 字符串相乘
2024-08-29 20:55:16
1. 原始题目
给定两个以字符串形式表示的非负整数 num1
和 num2
,返回 num1
和 num2
的乘积,它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明:
num1
和num2
的长度小于110。num1
和num2
只包含数字0-9
。num1
和num2
均不以零开头,除非是数字 0 本身。- 不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。
2. 思路
对于两个长为num1和num2的整数相乘,结果最长为num1+num2,所以先初始化这样长的一个数组。然后可以看到建立两个循环来存放每个索引的结果,当前的两个数字相乘后会在数组的两个位置产生结果。即商和余数。依次便利即可。存放完成后再对数组进行一边处理,因为有的位置可能>9,需要再进位至前一位。如果开头是0的话要删除。如果全0数组只返回”0“即可。
3. 实现
class Solution:
def multiply(self, num1: str, num2: str) -> str:
res = [0]*(len(num1)+len(num2))
for i in range(len(num1)-1, -1, -1): # 2,1,0
for j in range(len(num2)-1, -1, -1): # 1,0
temp = int(num1[i])*int(num2[j])
res[i+j+1] += temp%10 # 更新第一个索引位置
res[i+j] += temp // 10 # 更新第二个索引位置
for i in range(len(res)-1,-1,-1): # 将数组在遍历一遍更新>9的数,进位
if res[i]>9:
res[i-1]+=res[i]//10
res[i] = res[i]%10
res = ''.join([str(s) for s in res]).lstrip('') # 删掉开头的0
if not res: return '' # 如果全0的话只返回"0"就好
return res
最新文章
- ferret不能创建txt文本
- 将XmlDocument转换成XDocument
- Yii源码阅读笔记(十四)
- nagios监控远程主机端口
- ORACLE EXPDP命令使用详细【转】
- poj3468,poj2528
- cdoj 92 Journey tarjan/lca 树上点对距离
- php判断字符串是不是xml格式并解析
- 动态规划 计数型DP:dobra
- MapReduce新版客户端API源码分析
- js/jquery获取当前页面URL地址并判断URL字符串中是否包含某个具体值
- Celery工具
- Redux thunk中间件
- C#匿名对象(转JSON)
- python2 线程基础
- POJ 2187 - Beauty Contest - [凸包+旋转卡壳法][凸包的直径]
- Debian ifconfig 命令找不到
- POJ 3903 Stock Exchange 【最长上升子序列】模板题
- [C#.net]处理UTF-8文件乱码
- redisHelper
热门文章
- 图解CSS的padding,margin,border属性(详细介绍及举例说明)
- QQ会员2018春节红包抵扣券项目背后的故事
- MsysGit下GUI乱码问题解决
- 深入理解JavaScript系列(31):设计模式之代理模式
- js 获取时间相关
- [转]前端HTML-CSS规范
- SQLServer 2016 Express 安装部署,并配置支持远程连接
- The Dangers of the Large Object Heap(转载,LOH内存碎片情景重现)
- css-css简介
- 【linux学习笔记】began,每次玩这个都特别着迷