解题思路
-
题目要求:
- 输入两个字符串表示的整数
- 计算它们的和
- 字符串长度不超过10000
- 字符串只包含数字'0'-'9'
-
实现思路:
- 从右往左逐位相加
- 处理进位
- 最后反转结果
-
具体步骤:
- 将两个字符串对齐(右对齐)
- 从右往左遍历,按位相加并处理进位
- 注意最后可能还有进位需要处理
代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string addStrings(string num1, string num2) {
string result;
int carry = 0;
int i = num1.length() - 1;
int j = num2.length() - 1;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += num1[i--] - '0';
if (j >= 0) sum += num2[j--] - '0';
carry = sum / 10;
result += (sum % 10 + '0');
}
reverse(result.begin(), result.end());
return result;
}
int main() {
string num1, num2;
while (cin >> num1 >> num2) {
cout << addStrings(num1, num2) << endl;
}
return 0;
}
import java.util.*;
public class Main {
public static String addStrings(String num1, String num2) {
StringBuilder result = new StringBuilder();
int carry = 0;
int i = num1.length() - 1;
int j = num2.length() - 1;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += num1.charAt(i--) - '0';
if (j >= 0) sum += num2.charAt(j--) - '0';
carry = sum / 10;
result.append(sum % 10);
}
return result.reverse().toString();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String num1 = sc.next();
String num2 = sc.next();
System.out.println(addStrings(num1, num2));
}
}
}
def add_strings(num1: str, num2: str) -> str:
result = []
carry = 0
i, j = len(num1) - 1, len(num2) - 1
while i >= 0 or j >= 0 or carry:
sum_val = carry
if i >= 0:
sum_val += int(num1[i])
i -= 1
if j >= 0:
sum_val += int(num2[j])
j -= 1
carry = sum_val // 10
result.append(str(sum_val % 10))
return ''.join(result[::-1])
while True:
try:
num1 = input()
num2 = input()
print(add_strings(num1, num2))
except EOFError:
break
算法及复杂度
- 算法:模拟竖式加法
- 时间复杂度:
- 其中
和
是两个字符串的长度
- 空间复杂度:
- 需要存储结果字符串