抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

Leetcode 43. 字符串相乘

43. 字符串相乘

解法:利用竖式乘法原理(小学数学)

思路:这边找的是一个老哥的优化版,而且也比较好理解,写起来也不复杂。

https://leetcode-cn.com/problems/multiply-strings/solution/you-hua-ban-shu-shi-da-bai-994-by-breezean/

可能有两个点需要理解下:

  1. res[i+j+1]res[i+j]溢出问题,首先 i,j 是递减的,所以 res 数组填充是从后到前的,res[i+j+1]是取余不会存在溢出,res[i+j]是会的,但res[i+j]在下一步会变成res[i+j+1],所以这里就被处理了。
  2. 为什么最后需要过滤第一个0,这里引用评论区的一句话:m位乘以n位是m+n-1位到m+n位。

时间复杂度:O(M N)。M,N 分别为 num1 和 num2 的长度。

空间复杂度:O(M+N)。用于存储计算结果。

class Solution {
    fun multiply(num1: String, num2: String): String {
        if (num1 == "0" || num2 == "0") {
            return "0"
        }

        val c1 = num1.toCharArray()
        val c2 = num2.toCharArray()

        val res = IntArray(c1.size + c2.size) { 0 }
        for (i in c1.size - 1 downTo 0) {
            val n1 = c1[i] - '0'
            for (j in c2.size - 1 downTo 0) {
                val n2 = c2[j] - '0'
                val sum = (res[i + j + 1] + n1 * n2)
                //低位 取余
                res[i + j + 1] = sum % 10
                //高位
                res[i + j] += sum / 10
            }
        }

        val builder = StringBuilder()
        for (i in res.indices) {
            if (i == 0 && res[i] == 0) continue
            builder.append(res[i])
        }
        return builder.toString()
    }
}

0条评论

发表评论