43. Multiply Strings
Description
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
描述
給定兩個(gè)表示為字符串形式的非負(fù)整數(shù)num1和num2，返回num1和num2的乘積呛牲，也表示為字符串形式。
例:輸入 num1 = "2", num2 = "3",輸出 "6" 輸入 num1 = "123",num2 = "456", 輸出"56088"
注意：
- 字符串num1和num2的長度都小于110
- 字符串num1和num2都只包含數(shù)字0-9
- 字符串num1和num2起始都不會(huì)為0,除了num1和num2只有一個(gè)字符0本身的情況
- 不能使用任何函數(shù)自帶得乘法運(yùn)算也不能使用字符串轉(zhuǎn)換為整數(shù)的函數(shù)
思路
回顧乘法的運(yùn)算法則,如下圖
43 Multiply Strings-1.png
- 如上圖所示草姻，我們把兩個(gè)數(shù)右對(duì)齊魄宏，依次排好，從右至左依次進(jìn)行運(yùn)算，每次運(yùn)算結(jié)果按位置對(duì)其逸贾，最后進(jìn)行加和，這就完成了乘法運(yùn)算
- 再給出一個(gè)示例津滞，如下圖
class Solution:
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
if num1 == '0' or num2 == '0':
return '0'
lennum1, lennum2 = len(num1), len(num2)
result = [0]*(lennum1+lennum2)
# 共有兩層
for i in range(lennum1-1, -1, -1):
for j in range(lennum2-1, -1, -1):
# 首先計(jì)算乘積铝侵，注意用ASCII碼的方式轉(zhuǎn)換為數(shù)值
temp = (ord(num1[i])-ord('0'))*(ord(num2[j])-ord('0'))
# 計(jì)算所得應(yīng)和i+j位置求和
_sum = temp+result[i+j+1]
# 第i+j個(gè)位置
result[i+j+1] = _sum % 10
# 第i+j-1個(gè)位置,此代碼為python3，注意使用'//'等號(hào)進(jìn)行運(yùn)算触徐，例5/2=2.5,5//2=2
result[i+j] += _sum//10
# 將數(shù)字轉(zhuǎn)換為字符串
result = [str(i) for i in result]
return ''.join(result[1:]) if result[0] == "0" else ''.join(result)
源文件地址在這里
?本文首發(fā)于何睿的博客咪鲜，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來源撞鹉，作者信息和本聲明.
