leetcode:字符串相加

题目链接
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：
输入：num1 = “11”, num2 = “123”
输出：“134”

示例 2：
输入：num1 = “456”, num2 = “77”
输出：“533”

示例 3：
输入：num1 = “0”, num2 = “0”
输出：“0”

法一：暴力法（部分特别大的数字无法通过）

long long myStringLong(string s)//string->int
{
	long long i = 0;
	string::iterator it = s.begin();//反向迭代器
	while (it != s.end())
	{
		i *= 10;
		i += *it-48;//数字0-9对应的ascii码48-57
		it++;
	}
	return i;
}

string myLongString(long long i)//int->string
{
	//123
	string s1;
	while (i != 0)
	{
		int x = i % 10;
		char c = 48 + x;
		s1 += c;
		i /= 10;
	}
	//到这里得到321

	//再反向遍历回去
	string::reverse_iterator rit = s1.rbegin();
	string s2;
	while (rit != s1.rend())
	{
		s2 += *rit;
		rit++;
	}
	return s2;
}

class Solution {
public:
    string addStrings(string num1, string num2) {
        long long Num1 = myStringLong(num1);
        long long Num2 = myStringLong(num2);
        long long x=Num1 + Num2;//先获取int

        if (x == 0)
        {
	        return "0";
        }
        
        //最终需要把int转成string返回
        string y = myLongString(x);
        return y;
    }
};

法二：按位相加

string String1(string num1, string num2, int flag)//不等长情况，子串处理
{//num1长度大于num2
    if (flag == 1)//需要进位
    {
        int k = num1.size() - num2.size();//获取长度之差
        string s = num1.substr(0, k);//取子串
        //substr（i,j）从第i个位置取j个长度的子串

        if (s[k - 1] - '0' < 9)//不需要进位
        {
            s[k - 1]++;
        }
        else//需要进位
        {
            while (s[k - 1] - '0' == 9)
            {
                s[k - 1] = '0';
                k--;
                if (k == 0)
                {
                    string tmp = "1";
                    s = tmp + s;
                    break;
                }
                if (s[k-1]-'0' != 9)//防止是9+1
                {
                    s[k - 1]++;
                    break;
                }
            }
        }
        return s;
    }
    else//不需要进位，直接取剩余子串相加即可
    {
        int k = num1.size() - num2.size();
        string s = num1.substr(0, k);
        return s;
    }
}
class Solution {
public:
    string addStrings(string num1, string num2) {
    //从最后一位开始遍历
    string num;
    int i = num1.size() - 1;
    int j = num2.size() - 1;

    int flag = 0;//用于标记后面是否需要进位

    for (i, j; i >= 0, j >= 0; i--, j--)
    {
        if (i < 0 || j < 0)
        {
            break;
        }
        int c1 = num1[i] - '0';//获得对应位的数字
        int c2 = num2[j] - '0';
        int c3;
        if (flag == 0)//前面遍历的一位相加没有超过10
        {
            c3 = c1 + c2;
        }
        else
        {
            c3 = c1 + c2 + 1;
        }
        string tmp = to_string(c3);
        if (c3 >= 10)
        {
            //个位数最大就是9+9+1
            //相加最大是两位数
            num.insert(num.begin(), tmp[1]);//头插
            flag = 1;
        }
        else
        {
            num.insert(num.begin(), tmp[0]);
            flag = 0;
        }
    }
    if (num1.size() == num2.size())
    {
        if (flag == 0)//等长无进位
        {
            return num;
        }
        else//等长有进位
        {
            //等长进位最多进1位
            //比如91+92
            //1+2=3 个位取3
            //9+9=18 十位取8
            num.insert(0, 1,'1');
            return num;
        }
    }
    //防止两字符串不等长
    if (num1.size() > num2.size())
    {
        string s = String1(num1, num2, flag);
        s += num;
        num = s;
    }
    else
    {
        string s = String1(num2, num1, flag);
        s += num;
        num = s;
    }
    
    return num;
}
};