解题思路
这是一道字符串加法问题,主要思路如下:
-
问题分析:
- 输入两个字符串表示的数字
- 需要判断输入是否合法(是否都是数字)
- 计算两个数字的和
- 非法输入输出"error"
-
解决方案:
- 先判断字符串是否只包含数字
- 将字符串转换为数字数组,从低位到高位存储
- 按位相加,处理进位
- 最后反向输出结果
-
关键点:
- 处理进位
- 去除前导零
- 处理不等长字符串
代码
#include <iostream>
#include <string>
using namespace std;
// 判断字符串是否合法(只包含数字)
bool isLegal(const string& s) {
for (char c : s) {
if (c < '0' || c > '9') return false;
}
return true;
}
int main() {
string a, b;
while (cin >> a >> b) {
// 判断输入是否合法
if (!isLegal(a) || !isLegal(b)) {
cout << "error" << endl;
continue;
}
// 将字符串转为数字数组,反向存储
int len = max(a.length(), b.length()) + 1;
vector<int> result(len, 0);
// 从低位开始相加
for (int i = 0; i < a.length(); i++) {
result[i] += a[a.length()-1-i] - '0';
}
for (int i = 0; i < b.length(); i++) {
result[i] += b[b.length()-1-i] - '0';
}
// 处理进位
for (int i = 0; i < len-1; i++) {
result[i+1] += result[i] / 10;
result[i] %= 10;
}
// 去除前导零并输出
int start = len-1;
while (start > 0 && result[start] == 0) start--;
for (int i = start; i >= 0; i--) {
cout << result[i];
}
cout << endl;
}
return 0;
}
import java.util.Scanner;
public class Main {
// 判断字符串是否合法(只包含数字)
public static boolean isLegal(String s) {
for (char c : s.toCharArray()) {
if (c < '0' || c > '9') return false;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String a = sc.next();
String b = sc.next();
// 判断输入是否合法
if (!isLegal(a) || !isLegal(b)) {
System.out.println("error");
continue;
}
// 将字符串转为数字数组,反向存储
int len = Math.max(a.length(), b.length()) + 1;
int[] result = new int[len];
// 从低位开始相加
for (int i = 0; i < a.length(); i++) {
result[i] += a.charAt(a.length()-1-i) - '0';
}
for (int i = 0; i < b.length(); i++) {
result[i] += b.charAt(b.length()-1-i) - '0';
}
// 处理进位
for (int i = 0; i < len-1; i++) {
result[i+1] += result[i] / 10;
result[i] %= 10;
}
// 去除前导零并输出
StringBuilder sb = new StringBuilder();
int start = len-1;
while (start > 0 && result[start] == 0) start--;
for (int i = start; i >= 0; i--) {
sb.append(result[i]);
}
System.out.println(sb.toString());
}
}
}
def is_legal(s: str) -> bool:
return s.isdigit()
while True:
try:
# 读取输入
a, b = input().split()
# 判断输入是否合法
if not is_legal(a) or not is_legal(b):
print("error")
continue
# 将字符串转为数字列表,反向存储
len_max = max(len(a), len(b)) + 1
result = [0] * len_max
# 从低位开始相加
for i in range(len(a)):
result[i] += int(a[-(i+1)])
for i in range(len(b)):
result[i] += int(b[-(i+1)])
# 处理进位
for i in range(len_max - 1):
result[i+1] += result[i] // 10
result[i] %= 10
# 去除前导零并输出
while len(result) > 1 and result[-1] == 0:
result.pop()
print(''.join(map(str, result[::-1])))
except EOFError:
break
算法及复杂度
- 算法:模拟加法运算
- 时间复杂度:
-
为较长字符串的长度
- 空间复杂度:
- 需要存储结果数组