python leetcode 字符串相乘實(shí)例詳解
給定兩個(gè)以字符串形式表示的非負(fù)整數(shù) num1 和 num2 ,返回 num1 和 num2 的乘積,它們的乘積也表示為字符串形式。
示例 1:
輸入: num1 = "2", num2 = "3"
輸出: "6"
示例 2:
輸入: num1 = "123", num2 = "456"
輸出: "56088"
說明:
- num1 和 num2 的長度小于110。
- num1 和 num2 只包含數(shù)字 0-9 。
- num1 和 num2 均不以零開頭,除非是數(shù)字 0 本身。
不能使用任何標(biāo)準(zhǔn)庫的大數(shù)類型(比如 BigInteger)或直接將輸入轉(zhuǎn)換為整數(shù)來處理。
從題目要求來看,應(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è)可以說是個(gè)毫無技術(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)
這種解法我覺得還是沒有切合題意,將注意力放在的字符串轉(zhuǎn)數(shù)字上,乘法還是使用的*。題目要求不能將輸入直接轉(zhuǎn)成數(shù)字類型,解體人自己實(shí)現(xiàn)了int方法完成了字符串的轉(zhuǎn)換,好像是符合要求,但有投機(jī)取巧的感覺。
我來分享一下我的解法,思路很簡單也很好理解,當(dāng)我們徒手計(jì)算222*11時(shí)我們?cè)趺从?jì)算呢,肯定是分解成222+2220來計(jì)算的,那么我們就可以使用一個(gè)一維列表來記錄計(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:]
相關(guān)文章
Django+uni-app實(shí)現(xiàn)數(shù)據(jù)通信中的請(qǐng)求跨域的示例代碼
這篇文章主要介紹了Django+uni-app實(shí)現(xiàn)數(shù)據(jù)通信中的請(qǐng)求跨域的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10python?import?引用上上上級(jí)包的三種方法
這篇文章主要介紹了python?import?引用上上上級(jí)包的三種方法包的三種方法,需要的朋友可以參考下2023-02-02運(yùn)行django項(xiàng)目指定IP和端口的方法
今天小編就為大家分享一篇運(yùn)行django項(xiàng)目指定IP和端口的方法。具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-05-05Keras實(shí)現(xiàn)DenseNet結(jié)構(gòu)操作
這篇文章主要介紹了Keras實(shí)現(xiàn)DenseNet結(jié)構(gòu)操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-07-07