CodingTour —

ARTS #82

Algorithm

本周选择的算法题是：Multiply Strings

规则

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Constraints:

• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Solution

解法一：完全手算

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == '0' or num2 == '0': return '0'

        ans = [0] * (len(num1) + len(num2))
        for i in range(len(num1) - 1, -1, -1):
            carry = 0
            for j in range(len(num2) - 1, -1, -1):
                temp = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0')) + carry
                carry = (temp + ans[i+j+1]) // 10
                ans[i+j+1] = (temp + ans[i+j+1]) % 10
            ans[i] += carry
        return "".join(map(str, ans)).lstrip('0')

解法二：将两数换算成整型

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        first, second = 0, 0
        for num in num1:
            first = first * 10 + ord(num) - ord('0')
        for num in num2:
            second = second * 10 + ord(num) - ord('0')
        return str(first * second)

Review

Apple M1 foreshadows Rise of RISC-V

RISC-V 只有 40-50 个指令，相比 Intel 超过 1500 个指令来说，绝对算是 small and simple，而且它还将功耗做到了最低，未来可能是 ARM and RISC-V，又或者是 ARM or RISC-V。

Tip

修复了当网站内容含有图片时，顶部进度条显示不正确的 Bug：

$("img").on("load", event => {
  onResize();
});

Share

试水微信公众号。