leetcode 43 字符串乘法模板

题目

https://leetcode.com/problems/multiply-strings/submissions/

思路

计算任意两个数的乘法,然后结果对应的位置可以直接计算,落下去迭代更新

源码

class Solution {
public:
    //不要只有一个循环,直接两个循环,计算任意两个数的乘法,然后结果对应的位置可以直接计算,落下去迭代更新
    string multiply(string num1, string num2) {
        int m = num1.size(),n = num2.size();
        if(m == 0||n == 0)return "0";
        int pos[m+n]={0};
        for(int i = m-1;i >= 0; i--){
            for(int j = n-1; j >= 0; j--){
                //pos从大存从小存都可以
                int mul = (num1[i]-'0')*(num2[j]-'0');
                int pl = i+j+1;
                int ph = i+j;
                int sum = pos[pl]+mul;//这一步也很妙
                pos[pl]=sum%10;
                pos[ph]+=sum/10;
            }
        }
        string res = "";
        for(int i = 0;i < m+n;++i){
            //排除开头的0
            if(res.length()==0&&pos[i]==0)continue;
            res+=('0'+pos[i]);
        }
        return res.length()==0?"0":res;
    }
};

发表评论

邮箱地址不会被公开。 必填项已用*标注