LeetCode Multiply Strings 大数相乘
发布时间:2020-12-14 03:35:42 所属栏目:大数据 来源:网络整理
导读:题目要求: 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. 代码:? 代码支持 大负数的相乘 class Solution {public: string multiply(str
题目要求: 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. 代码:?代码支持 大负数的相乘 class Solution { public: string multiply(string num1,string num2) { int flag1 = 1,flag2 = 1; if(num1.empty() || num2.empty()) return " "; if(num1[0] == '-') flag1 = -1; if(num2[0] == '-') flag2 = -1; string res; if(num1[0] == '0' || num2[0] == '0') return "0"; int len = num1.size(); if(flag1 == -1) num1 = num1.substr(1); if(flag2 == -1) num2 = num2.substr(1); for(int i = num1.size() - 1; i >= 0; --i) { MultiplyByNum(res,num2,num1[i],len - i - 1); } if(flag1 != flag2) res.insert(res.begin(),'-'); return res; } void MultiplyByNum(string& res,const string& multi,char num,int multiply) { string tmp; if(num == '0') return; MultiplyByNum(tmp,multi,num); for(size_t i = 0; i < multiply; ++i) tmp.push_back('0'); Add(res,tmp); } void MultiplyByNum(string& res,char num) { int carry = 0; for(int i = multi.size() - 1; i >= 0; --i) { int tmp = (multi[i] - '0') * (num - '0') + carry; res.push_back((tmp % 10) + '0'); carry = tmp / 10; } if(carry != 0) res.push_back(carry + '0'); reverse(res.begin(),res.end()); } void Add(string& num1,string& num2) { int carry = 0; string tmp; int len1 = num1.size(),len2 = num2.size(); int i = len1 - 1,j = len2 - 1; while(i >= 0 || j >= 0) { int sum = 0; if(i >= 0) { sum += num1[i] - '0'; --i; } if(j >= 0) { sum += num2[j] - '0'; --j; } sum += carry; tmp.push_back((sum % 10) + '0'); carry = sum / 10; } if(carry != 0) tmp.push_back(carry + '0'); reverse(tmp.begin(),tmp.end()); num1 = tmp; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- golang如何实现mapreduce单进程版本详解
- VB提示 - 文件未找到 “C:/Windows/sytem32/ieframe.dll/1”
- scilab符号运算工具箱Symbolic Toolbox for Scilab安装过程
- [VB.NET]点net写client程序传递参数给mssql存储过程insert,
- Delphi XE – 我应该使用String还是AnsiString?
- 201. Bitwise AND of Numbers Range
- Delphi 2010 TListView一些使用
- Delphi 制作自定义数据感知控件并装入包(dpk文件)中(与D
- Lua 错误处理 pcall & xpcall
- Golang:make,slice和append的一个小细节