415. Add Strings
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
给定两个用字符串表示的非负整数num1和num2，返回用字符串表示的num1和num2的和。
Note:
The length of both num1 and num2 is < 5100.(长度都是<5100)
Both num1 and num2 contains only digits 0-9.(只包含数字0-9)
Both num1 and num2 does not contain any leading zero.(不包含任何前导零)
You must not use any built-in BigInteger library or convert the inputs to integer directly.(不得使用任何内置的BigInteger库或直接将输入转换为整数)
先写出自己的理解，最下面是最好的解法
错误思路1：
刚开始把第一个Node看成了num1和num2小于5100，紧接着整体的想法就歪了。。。。
先将num1和num2转化为整数，相加后将结果转化为字符串输出
代码只能将在int范围的整数正确求和，超出int返回就发生错误，输出-1
错误代码1：
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string addStrings(string num1, string num2) {//错误 只能运行在int范围内 题目要求num1和num2长度小于5100
int NUM1 = stringToInt(num1);
int NUM2 = stringToInt(num2);
return intToString(NUM1+NUM2);
}
string intToString(int i){//整数转化为字符串
string s = "";
if(i < 0)
return "-1";
if(i == 0)
s = "0";
while(i > 0){
int temp = i%10;
s = intToChar(temp) + s;
i /= 10;
}
return s;
}
int stringToInt(string s){//字符串转化为整数
int Length = s.size();
int t = 1;
int num = 0;
for(int i=Length-1; i>=0; i--){
int temp = charToInt(s[i]);
num += temp*t;
t *= 10;
}
return num;
}
int charToInt(char c){//字符转化为整数
char charArray[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
for(int i=0; i<=9; i++){
if((charArray[i]^c) == 0){// ^ 优先级小于 ==， 必须在charArray[i]^c外加括号
return i;
}
}
return -1;
}
char intToChar(int i){//整数转化为字符
char charArray[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
for(int m=0; m<=9; m++){
if((m^i) == 0){// ^ 优先级小于 ==， 必须在charArray[i]^c外加括号
return charArray[m];
}
}
return '-1';
}
};
int main()
{
Solution S;
string num1 = "13423452345345";
string num2 = "93423423423423423";
cout << S.addStrings3(num1, num2) << endl;
return 0;
}
正确思路1：
在错误思路1的基础上，我曾尝试将int改成long等各种类型，发现题目规定的范围太大了，数字类型都无法满足，只能换一个想法
思路是分情况讨论，字符串相等或不相等
字符串不相等时，将两个字符串相加，长字符串分成两部分，一部分是长字符串的右半部分（即低位），和短字符串长度相同，另一部分是剩下的字符串，左半部分（即高位）
将右半部分和短字符串相加得到一个数，加上左半部分
为此我还专门写了两个函数，一个用于相等字符串相加，一个用于不相等字符串相加（其实就是将不等的两个字符串分割开，利用相等字符串相加的函数求解）
最后历经坎坷，终于通过了，但是效率不是太高
代码如下：
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string addStrings1(string num1, string num2) {//正确 但是效率太低 12ms
int length1 = num1.size();
int length2 = num2.size();
if(length1>length2)
return addStrings2(num1, num2, length1, length2);
else if(length1<length2)
return addStrings2(num2, num1, length2, length1);
else{//两个字符串长度相等
int a =0;
string res = addStr(num1, num2, a);
if(a == 1){
return '1'+res;
}
return res;
}
}
//两个长度不相等的字符串相加
string addStrings2(string Max, string Min, int MaxLength, int MinLength){
string res = "";
string LString = "";
string RString = "";
int t = MaxLength-MinLength;
for(int i=0; i<MaxLength; i++){//将长字符串分为左右两部分
if(i<t)
LString += Max[i];
else
RString += Max[i];
}
int a = 0;
res = addStr(Min, RString, a) + res;//将右半部分和短字符串相加赋值给res
if(a == 1){//右半部分和短字符串相加有进位
string tempA = "1";
for(int j=0; j<LString.size()-1; j++)
tempA = '0' + tempA;
a = 0;
LString = addStr(LString, tempA, a);//左半部分和进位相加
if(a == 1)//左半部分和进位相加仍然有进位
LString = '1' + LString;
}
res = LString + res;
return res;
}
//字符串长度相同的相加,a代表是否有进位
string addStr(string num1, string num2, int &a){
string res = "";
for(int i=num1.size()-1; i>=0; i--){
int temp = charToInt(num1[i]) + charToInt(num2[i]) + a;
if(temp < 10){
a =0;
res = intToChar(temp) + res;
}
else{
a = 1;
res = intToChar(temp%10) + res;
}
}
return res;
}
int charToInt(char c){//字符转化为整数
char charArray[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
for(int i=0; i<=9; i++){
if((charArray[i]^c) == 0){// ^ 优先级小于 ==， 必须在charArray[i]^c外加括号
return i;
}
}
return -1;
}
char intToChar(int i){//整数转化为字符
char charArray[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
for(int m=0; m<=9; m++){
if((m^i) == 0){// ^ 优先级小于 ==， 必须在charArray[i]^c外加括号
return charArray[m];
}
}
return '-1';
}
};
int main()
{
Solution S;
string num1 = "13423452345345";
string num2 = "93423423423423423";
cout << S.addStrings1(num1, num2) << endl;
return 0;
}
思路3：
我的代码AC后我看了一下时间，发现一个3ms的代码，代码理解起来不难，我还在他的代码上加上了一些括号便于理解，增加了一些注释
再看一下我的代码，实在是不忍直视。以后仍需努力
下面贴出代码
#include <algorithm>
string addStrings(string num1, string num2) {//速度最快3ms
string res = "";
int add=0,i=num1.size()-1,j=num2.size()-1;
while(i>=0 || j>=0 || add>0)
{
int cur=add;
cur+=(i>=0?num1[i--]-'0':0);
cur+=(j>=0?num2[j--]-'0':0);
add=cur/10;//用来判断是否有进位
cur%=10;
res+=('0'+cur);
}
reverse(res.begin(), res.end());//翻转字符串
return res;
}
