給定兩個(gè)以字符串形式表示的非負(fù)整數(shù) num1 和 num2 ，返回 num1 和 num2 的乘積，它們的乘積也表示為字符串形式。
示例 1:
輸入: num1 = "2", num2 = "3"
輸出: "6"
示例 2:
輸入: num1 = "123", num2 = "456"
輸出: "56088"
說(shuō)明：
不能使用任何標(biāo)準(zhǔn)庫(kù)的大數(shù)類型（比如 BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來(lái)處理。
從題目要求來(lái)看，應(yīng)該是讓我們實(shí)現(xiàn)一個(gè)比較省內(nèi)存的大數(shù)乘法，先分享幾個(gè)我在discuss中發(fā)現(xiàn)的不太切合題意的解法：
class Solution: def multiply(self, num1, num2): """ :type num1: str :type num2: str :rtype: str """ return str(eval(num1+'*'+num2))
這個(gè)可以說(shuō)是個(gè)毫無(wú)技術(shù)含量的解法，如果面試的時(shí)候掏出這種解法，八成是跪了。
還有很多人使用了以下的解法。
class Solution: def multiply(self, num1, num2): """ :type num1: str :type num2: str :rtype: str """ dict = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9} if (num1=='0' or num2=='0'): return "0" n1 = 0 n2 = 0 for c in num1: val = dict[c] n1 = n1*10 + val for s in num2: val = dict[s] n2 = n2*10 + val result = n1 * n2; return str(result)這種解法我覺得還是沒(méi)有切合題意，將注意力放在的字符串轉(zhuǎn)數(shù)字上，乘法還是使用的*。題目要求不能將輸入直接轉(zhuǎn)成數(shù)字類型，解體人自己實(shí)現(xiàn)了int方法完成了字符串的轉(zhuǎn)換，好像是符合要求，但有投機(jī)取巧的感覺。
我來(lái)分享一下我的解法，思路很簡(jiǎn)單也很好理解，當(dāng)我們徒手計(jì)算222*11時(shí)我們?cè)趺从?jì)算呢，肯定是分解成222+2220來(lái)計(jì)算的，那么我們就可以使用一個(gè)一維列表來(lái)記錄計(jì)算結(jié)果11分解成10+1，第一輪計(jì)算列表的結(jié)果為[0, 2, 2, 2]，第二輪計(jì)算后變?yōu)閇2, 2+2, 2+2, 2]計(jì)算結(jié)束。如果需要進(jìn)位的話，進(jìn)位的計(jì)算放到最后一步。
class Solution(object): def multiply(self, num1, num2): """ :type num1: str :type num2: str :rtype: str """ if num1 == "0" or num2 == "0": return "0" num1 = num1[::-1] num2 = num2[::-1] str_list = [0 for _ in range(len(num1)+len(num2))] for i in range(len(num1)): for j in range(len(num2)): str_list[i+j] += (int(num1[i])*int(num2[j])) result = "" up = 0 for i in str_list: now = i + up cur = now % 10 up = now / 10 result += str(cur) begin = 0 result = result[::-1] for i in result: if i == "0": begin += 1 else: break return result[begin:]
新聞熱點(diǎn)
疑難解答
圖片精選
