Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Multiply Strings

Leetcode algorithms 第 43 题:Multiply Strings 。

题目

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

解答

非负数高精度乘法。直接模拟进行,注意字符与数字的转换以及进位、前导0的问题。

具体代码如下:

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        
        int l1 = num1.size(), l2 = num2.size();
        string ans(l1+l2, '0');
        
        for (int i = l1-1; i >= 0; i--)
        {
            int carry = 0; //进位
            for (int j = l2-1; j >= 0; j--)
            {
                int tem = (num1[i]-'0') * (num2[j]-'0') + ans[i+j+1]-'0' + carry;
                if (tem > 9)
                    ans[i+j+1] = tem%10 + '0', carry = tem / 10;
                else
                    ans[i+j+1] = tem + '0', carry = 0;
            }
            if (carry) ans[i] += carry;
        }
        
        return ans.substr(ans.find_first_not_of('0')); //移除前导0
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论