程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Multiply Strings

LeetCode Multiply Strings

編輯:C++入門知識

LeetCode Multiply Strings


LeetCode解題之Multiply Strings


原題

將兩個用字符串表示的數進行乘法操作並返回字符串結果。

注意點:

給的數是非負整數數字可以無窮大

例子:

輸入: num1 = “123”, num2 = “20”
輸出: “2460”

解題思路

根據筆算乘法的公式來看,乘法操作分解開來其實就是先進行每個位的乘法操作,然後將所有結果進行加法操作。首先明確一個m位的數乘以一個n位的數做多為m+n位(都是9的時候試一下)。其次後面的0相等的數在相加時是末尾對齊的。如123×456,我們可以看到1×6、2×5和3×4在進行加法的時候是末尾對齊的,我們可以在進行第一輪乘法的時候將這些數先加起來,而後面的零通過在列表中的位置來表示。再用一個循環進行進位加法,最後把開頭多余的0去掉。具體步驟看下面的例子:

123*456

100        400
 20         50
  3          6

[3*6, 2*6+3*5, 1*6+2*5+3*4, 2*4+1*5, 1*4, 0]

[18, 27, 28, 13, 4, 0]

[8, 27+1, 28, 13, 4, 0]

[8, 8, 28+2, 13, 4, 0]

[8, 8, 0, 13+3, 4, 0]

[8, 8, 0, 6, 5, 0]

"880650"-->"056088"

"56088"

AC源碼

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        num1 = num1[::-1]
        num2 = num2[::-1]
        length1 = len(num1)
        length2 = len(num2)
        temp = [0 for __ in range(length1 + length2)]
        # Do multiply
        for i in range(length1):
            for j in range(length2):
                temp[i + j] += int(num1[i]) * int(num2[j])
        carry = 0
        digits = []
        # Do plus
        for num in temp:
            s = carry + num
            carry = s // 10
            digits.append(str(s % 10))
        result = "".join(digits)[::-1]
        # Remove the surplus zero
        sub_index = 0
        for i in range(length1 + length2 - 1):
            if result[i] == "0":
                sub_index += 1
            else:
                break
        result = result[sub_index:]
        return result


if __name__ == "__main__":
    assert Solution().multiply("120", "20000") == 2400000
    assert Solution().multiply("0", "3421") == 0

歡迎查看我的Github來獲得相關源碼。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved