程序员人生 网站导航

LeetCode Multiply Strings

栏目:php教程时间:2015-04-01 08:35:56

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.

题意:字符串的乘法。

思路:摹拟竖乘的思路,跟大数计算1样,先将字符串颠倒

class Solution { public: string multiply(string num1, string num2) { reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); int len1 = num1.size(), len2 = num2.size(); string ans(len1+len2+1, '0'); int tmp = 0; for (int i = 0; i < len1; i++) { int cur = num1[i] - '0'; tmp = 0; for (int j = 0; j < len2; j++) { int a = tmp + cur * (num2[j]-'0') + (ans[i+j]-'0'); tmp = a / 10; ans[i+j] = a % 10 + '0'; } int idx = len2; while (tmp != 0) { int a = tmp + (ans[i+idx]-'0'); tmp = a / 10; ans[i+idx] = a % 10 + '0'; idx++; } } while (!ans.empty() && ans.back() == '0') ans.pop_back(); if (ans.empty()) return "0"; reverse(ans.begin(), ans.end()); return ans; } };



------分隔线----------------------------
------分隔线----------------------------

最新技术推荐