首页 > 代码库 > LeetCode: Multiply Strings [042]

LeetCode: Multiply Strings [042]

2024-07-05 11:26:02   230人阅读

【题目】


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.



【题意】

给定用字符串表示的整数，返回两个数的乘积结果字符串。两个数字都非负，且能任意大。


【思路】

       

1. 考虑其中一个数是0的情况
2. 模拟乘法运算过程

    维护一个vector，用来存储成绩结果结各个数位上的累加值，从0~高位依次是个，十，百，千，万......

    然后对各个位置上的累加值mod 10就能得到对应的值【注意进位的处理】 


【代码】

class Solution {
public:
    string multiply(string num1, string num2) {
        string result="";
        //默认num1是被乘数，num2是乘数，我们先保证乘数的位数小于被乘数
        if(num1.length()<num2.length()){
            string temp=num1;
            num1=num2;
            num2=temp;
        }
        //判断乘数或被乘数是否为0
        if(num1=="0"||num2=="0")return "0";
        //处理一般情况
        vector<int> posVal;
        int posSize=0;  //用来确定posSize中已有的位数
        int lenNum1=num1.length();
        int lenNum2=num2.length();
        //乘数的每一位与被乘数的每一位相乘
        for(int i=lenNum2-1; i>=0; i--){
            int pos2Add=lenNum2-1-i;
            for(int j=lenNum1-1; j>=0; j--){
                int multiplyVal=((int)(num2[i]-'0'))*((int)(num1[j]-'0'));
                //将乘积累加到对应的结果位，进位问题先不管
                if(pos2Add<posSize){
                    posVal[pos2Add]+=multiplyVal;
                }
                else{
                    posVal.push_back(multiplyVal);
                    posSize++;                
                }
                pos2Add++;
            }
        }
        //生成结果
        int toNext=0;   //存储进位值
        for(int i=0; i<posSize; i++){
            int curPosVal=(toNext+posVal[i])%10;
            char curPosValChar=curPosVal+'0';
            toNext=(toNext+posVal[i])/10;
            result=curPosValChar+result;
        }
        //别忘了还有进位值需要处理
        while(toNext>0){
            int curPosVal=toNext%10;
            char curPosValChar=curPosVal+'0';
            toNext=toNext/10;
            result=curPosValChar+result;
        }
        return result;
    }
};


联系
我们