每日练习-2022-1-31-牛客NC1-大数加法

描述

来源：牛客-名企高频面试题高频TOP200

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

数据范围：len(s),len(t) <= 100000，字符串仅由’0’~’9’构成

要求：时间复杂度 O(n)

答案及解析

倒序相加，判断进位

string solve(string s, string t)
{
	vector<int> vec;
	auto len1 = s.size();
	auto len2 = t.size();
	string str;
	bool last = false;
	int i = len1 - 1;
	int j = len2 - 1;
	for ( ;; )
	{
		int num = 0;
		if ( i >= 0 )
			num += s[i] - '0';
		if ( j >= 0 )
			num += t[j] - '0';
		if ( i < 0 && j < 0 )
			break;
		if ( last )
			++num;
		if ( num >= 10 )
		{
			num -= 10;
			last = true;
		}
		else
		{
			last = false;
		}
		vec.push_back(num);
		--i;
		--j;
	}
	if ( last )
		vec.push_back(1);
	std::reverse(vec.begin(), vec.end());
	for ( auto i : vec )
		str.push_back(i + '0');
	return str;
}