美文网首页
43. 字符串相乘

43. 字符串相乘

作者: __LXF__ | 来源:发表于2020-03-10 14:06 被阅读0次

1、思路

  两数相乘时,乘数某位与被乘数某位相乘,所产生结果的位置是有规律的。具体规律如下:
  乘数 num1 位数为 MM,被乘数 num2 位数为 NN, num1 x num2 结果 res 最大总位数为 M+N。num1[i] x num2[j] 的结果为 tmp(位数为位,"0x","xy"的形式),其第一位位于 res[i+j],第二位位于 res[i+j+1]。

2、代码实现(C++)

class Solution {
public:
    // 字符串相乘
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        int len1 = num1.length();
        int len2 = num2.length();
        string res(len1+len2, '0'); // 结果位数一定小于等于len1+len2位
        for (int i = len2-1; i >= 0; i--) {
            for (int j = len1-1; j >= 0; j--) {
                int temp = (num1[j]-'0') * (num2[i]-'0') + (res[i+j+1]-'0'); // res[i+j+1]是上次进位
                res[i+j+1] = temp%10 + '0';   //当前位
                res[i+j] += temp/10;  // 产生的进位,res[i+j]已经初始化为'0',加上int类型自动转化为char,所以此处不加'0'
            }
        }
        // 去除首位'0'
        for(int i = 0; i < len1+len2; i++){
            if(res[i]!='0')
                return res.substr(i);
        }
        return "0";
    }
};

相关文章

  • LeetCode 43. 字符串相乘 | Python

    43. 字符串相乘 题目来源:力扣(LeetCode)https://leetcode-cn.com/proble...

  • 字符串乘法

    读完本文,你可以去力扣拿下如下题目: 43.字符串相乘[https://leetcode-cn.com/probl...

  • 43.字符串相乘

    题目给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也...

  • 43. 字符串相乘

  • 43. 字符串相乘

    1、思路   两数相乘时,乘数某位与被乘数某位相乘,所产生结果的位置是有规律的。具体规律如下:  乘数 num1 ...

  • 43. 字符串相乘

    自己解法 墨迹了两晚上,才写出来的字符串相乘,虽然写得很丑,还是记下来吧,至少思路是好理解的。基本就是从个位开始乘...

  • 43.字符串相乘

    题目描述: 给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们...

  • 43. 字符串相乘

    给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示...

  • 43. 字符串相乘

    #### [https://leetcode-cn.com/problems/multiply-strings]4...

  • LeetCode 43.字符串相乘

    题目 给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积...

网友评论

      本文标题:43. 字符串相乘

      本文链接:https://www.haomeiwen.com/subject/vtuwdhtx.html