力扣算法题—043字符串相乘

末蓝、 2022-10-02 15:55 181阅读 0赞

解题思路：

/*
                      4   5     6
                    * 1   2     3
                ——————————
                     12   15   18
                 8   10      12
             4   5    6
        ————————————
        v _  _   _    _    _    _
        v 0  4   13   28   27   18
        进位处理即得答案
    */

1 class Solution {
     2 public:
     3     string multiply(string num1, string num2) {
     4         int len1 = num1.length();
     5         int len2 = num2.length();
     6         vector<int>v(len1 + len2, 0); //用来存放乘积，最后的结果的位数不可能超过len1+len2
     7         
     8         for (int i = len1 - 1; i >= 0; i--) {
     9             for (int j = len2 - 1; j >= 0; j--) {
    10                 v[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');  //此处很巧妙，对应位乘完后相加，并始终不进位
    11             }
    12         }
    13 
    14         // 处理进位
    15         int carry = 0;
    16         for (int i = len1 + len2 - 1; i >= 0; i--) {
    17             v[i] += carry;
    18             carry = v[i] / 10;
    19             v[i] %= 10;
    20         }
    21 
    22         string re = "";
    23         int flag = 1;
    24         for (int i = 0; i < len1 + len2; ++i) {
    25             if (v[i] == 0 && flag)continue;//去除前位是0的数
    26             re += v[i] + '0';
    27             flag = 0;
    28         }
    29         if (flag)
    30             re += '0';//若全为0即得0
    31         return re;
    32     }
    33 };
    34 
    35 
    36 void T043() {
    37     Solution s;
    38     string num1;
    39     string num2;
    40     num1 = "2";
    41     num2 = "3";
    42     cout << s.multiply(num1, num2) << endl;
    43     num1 = "123";
    44     num2 = "456";
    45     cout << s.multiply(num1, num2) << endl;
    46     num1 = "0";
    47     num2 = "456";
    48     cout << s.multiply(num1, num2) << endl;
    49 }

转载于:https://www.cnblogs.com/zzw1024/p/10579198.html