当前位置 博文首页 > yumoz:LeetCode43--字符串相乘

    yumoz:LeetCode43--字符串相乘

    作者:[db:作者] 时间:2021-07-14 15:39

    1 题目描述

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

    1.1分析

    1. 判断num1 或 num2 是否为0或1;
    //1.判断单独有“0” 和 "1"的情况
    if(num1=="0" || num2=="0") return "0";
    if(num1=="1") return num2;
    if(num2=="1") return num1;
    
    1. 保证效率,让大数乘小数
    //2. 保证效率,让大数乘小数
    if(num1.length() < num2.length())  
        swap(num1,num2);
    
    1. 测长度 开空间
     // 3. 测长度,开字符串
    int m = num1.length(), n = num2.length();
    //提前开一个足够大的string,m位数和n位数的乘法结果不会超过m+n位数
    string res(m+n,'0');  
    
    1. 计算 字符串相乘(重点分析
      以 num1 = 123 ,num2 = 456 为例子分析:
      公式: new_num = (num1[j]-'0')*(num2[i]-'0') + (res[i+j+1]-'0') + c_in;
      在这里插入图片描述
      在这里插入图片描述
      依次类推,第三层循环留给读者分析。
      得到结果:
      res[1] = 5
      res[2] = 6
      res[3] = 0
      res[4] = 8
      res[5] = 8

    总结:此段代码,有效的结合进位,叠加等方式,依次推出每个位的值,最后通过计算得出最终答案。

    //4. 计算相乘
            for(int i = n-1; i>=0; --i){
                int c_in = 0; //进位
                for(int j = m-1; j>=0; --j){
                    //乘法加法进位一口气算完
                    int new_num = (num1[j]-'0')*(num2[i]-'0') + (res[i+j+1]-'0') + c_in;  
                    c_in = new_num / 10; //进位
                    new_num = new_num % 10;  //求出 
                    res[i+j+1] = char(new_num + '0'); //转成字符类型
                }
                if(c_in > 0) res[i] = char(c_in + '0');//有进位,加进位
            }
    
    1. 去除相乘后,数字前多余零
    int i = 0;
            while(res[i] == '0') i++;
            return res.substr(i,m+n-i);   //去掉前面多余的0
    

    2 代码

    class Solution {
    public:
        string multiply(string num1, string num2) {
            //1.判断单独有“0” 和 "1"的情况
            if(num1=="0" || num2=="0") return "0";
            if(num1=="1") return num2;
            if(num2=="1") return num1;
    
            //2. 保证效率,让大数乘小数
            if(num1.length() < num2.length())  
                swap(num1,num2);
            
            // 3. 测长度,开字符串
            int m = num1.length(), n = num2.length();
            //提前开一个足够大的string,m位数和n位数的乘法结果不会超过m+n位数
            string res(m+n,'0');  
            //4. 计算相乘
            for(int i = n-1; i>=0; --i){
                int c_in = 0; //进位
                for(int j = m-1; j>=0; --j){
                    //乘法加法进位一口气算完
                    int new_num = (num1[j]-'0')*(num2[i]-'0') + (res[i+j+1]-'0') + c_in;  
                    c_in = new_num / 10; //进位
                    new_num = new_num % 10;  //求出 
                    res[i+j+1] = char(new_num + '0'); //转成字符类型
                }
                if(c_in > 0) res[i] = char(c_in + '0');//有进位,加进位
            }
    
            int i = 0;
            while(res[i] == '0') i++;
            return res.substr(i,m+n-i);   //去掉前面多余的0
        }
    };
    

    总结

    此篇博客代码参考于大牛写的一个题解,作为一种新的处理方法。

    cs