【leetcode】43. Multiply Strings 大数乘法
发布时间:2021-01-21 09:09:33 所属栏目:大数据 来源:网络整理
导读:1. 题目 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. Converting the input string to integer is NOT allowed. You should NOT use
1. 题目Given two numbers represented as strings,return multiplication of the numbers as a string. Note: 2. 思路模拟手算的过程,按位相乘并累加。 3. 代码耗时:26ms class Solution { public: // 模拟乘法手算过程实现 string multiply(string num1,string num2) { string sum; sum.reserve(num1.length() * num2.length() + 2); string prefix; // 从低到高位逐个字符相乘,然后加入到总和中去。 for (int i = num2.length() - 1; i >= 0; i--) { char c2 = num2[i]; string c_sum = multiply(num1,c2) + prefix; sum = plus(sum,c_sum); prefix += '0'; } // 去掉前导0多余的0,至少保留一位 int i = 0; while (sum[i] == '0' && i < sum.length() - 1) {i++;} return sum.substr(i); } string multiply(string& n,char c) { string r; r.reserve(n.length() + 2); int jingwei = 0; for (int i = n.length() - 1; i>= 0; i--) { int m = multiply(n[i],c); m += jingwei; r += m % 10 + '0'; jingwei = m / 10; } if (jingwei != 0) { char ch = '0' + jingwei; r += ch; } reverse(r.begin(),r.end()); return r; } int multiply(char c1,char c2) { return (c1 - '0') * (c2 - '0'); } string plus(string& n1,string& n2) { string n3; int l1 = n1.length(); int l2 = n2.length(); int min_v = min(l1,l2); int max_v = max(l1,l2); n3.reserve(max_v + 2); char jingwei = '0'; for (int i = 1; i <= min_v; i++) { char c1 = n1[l1 - i]; char c2 = n2[l2 - i]; int c_sum = plus(c1,c2,jingwei); n3 += c_sum % 10 + '0'; jingwei = c_sum / 10 + '0'; } string& big = n1; if (l2 > l1) { big = n2; } for (int i = min_v + 1; i <= max_v; i++) { int c_sum = plus(big[max_v - i],jingwei); jingwei = c_sum / 10 + '0'; n3 += c_sum % 10 + '0'; } if (jingwei != '0') { n3 += jingwei; } reverse(n3.begin(),n3.end()); return n3; } int plus(char c1,char c2) { return c1 + c2 - 2 * '0'; } int plus(char c1,char c2,char c3) { return c1 + c2 + c3 - 3 * '0'; } }; (编辑:佛山站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |