每天一道LeetCode-----字符串乘法

原题链接Multiply Strings

意思是给两个字符串，代表两个整数，求这两个整数的积，以字符串的形式返回
主要注意的地方在这两个字符串可能很长，远远超过了long long int所表示的范围，所以当初耍小聪明直接用std::stringstream获取两个整数再相乘就果断的溢出了

所以这种问题还是实打实的用字符串计算比较好，当然需要点技巧，算法题很少用蛮力法硬算的…
首先还是找规律，对于字符串1的某一位乘字符串2的某一位，乘积的结果在整个结果的哪一位呢，能不能找到某种规律直接定位，这样就简单多了。
先看一下乘法运算

/* 以下a * b表示num1[a] * num2[b] */
                    num1[0]        num1[1]        num1[2]
            *       num2[0]        num2[1]        num2[2]
--------------------------------------------------0 * 2          1 * 2          2 * 20 * 1       1 * 1          2 * 1
0 * 0     1 * 0       2 * 0
----------------------------------------------------------

上式中直接用下标代表对应位的值，乘号左边代表num1的值，右边代表num2的值，比如0 * 1代表num1[0] * num2[1]
注意这里，0*0中0+0=0，正好是结果的第0位，0*1中0+1=1，1*0中1+0=1刚好是结果的第1位
所以根据下标很容易定位到结果的位置
又因为0*0可能会进位，所以在结果中每一位都后移一位，即0*0是第1位….，第0位用来存最后的进位
这样代码就容易写出了

class Solution {
public:string multiply(string num1, string num2) {if(num1 == "0" || num2 == "0")return "0";int n1 = num1.size();int n2 = num2.size();string res(n1 + n2, '0');for(int i = n1 - 1; i >= 0; --i){for(int j = n2 - 1; j >= 0; --j){int lhs = num1[i] - '0';int rhs = num2[j] - '0';/* 这里要注意的问题时，当把进位加给res[i+j]时，res[i+1]仍然可能继续向高位进位 *//* 但是不需要直接处理这种情况，在下次处理到res[i+j]时，一定会将进位进到高位 *//* 因为res[i+j]一定在res[i+j+1]后面处理 */int num = lhs * rhs + (res[i + j + 1] - '0');res[i + j + 1] = (num % 10) + '0';res[i + j] = res[i + j] + num / 10;}}/* 比如两个3位数相乘结果位数可能是5位或6位，6位时是次高位向高位有进位，此时res中没有前导0 *//* 而5位时说明没有进位，那么res[0]将是0，结果应该把这个前导0去掉，因为初始时res设成6位 */return res.substr(res.find_first_not_of('0'));}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！