撬动offer：两个长字符串数字相加
共 2412字，需浏览 5分钟
·
2020-10-30 03:08
点击上方「蓝字」关注我们
算法题千奇百怪，今天分享的这样一道算法题。
0x01：题目
题目一：有两个字符串分别如下：
String a = "10101001101010100110";
String b = "1011011101100";
字符串里的数字或者是0，或者是1。编写一个函数实现这两个数的二进制字符串相加。考虑都是无符号数字相加。
题目变种
有两个字符串分别如下：
String a = "1879987637894818799876378948";
String b = "176898";
字符串里的数字是0到9的任意一个数字字符。编写一个函数实现这两个十进制字符串的相加。考虑都是无符号数字相加。
0x02：分析
如果a和b这两个字符串的数字位数不是很多大，确实直接用Integer或者Long类型转换就可以求出a+b了，但是如果a和b的位数都是几百位呢？那么就不可以使用简单的数字相加的方法了，因为a或者b早就溢出了，Integer或者Long已经无法表示a或b这两个数值了。这时候要怎么计算呢？这种情况下，可以想到如下一些解决方案
用字符串来存储a和b的值；
用数组来存储a和b的值；
用链表来存储a和b的值。
可能有其他解决方案，请大家想想。以上这三种方案都有一个共同点，就是无论哪一种方案，都可以不需要担心因为数字太大而造成数值溢出出错。除了内存溢出的情况。
回想一下老师教的数字是怎么相加，其实就是从数字的最右边的最后一位开始（就是个位开始计算），将两个对应的位进行相加，对于十进制，如果相加的数字大于等于10，就往前进一位。就这样教计算机进行计算即可。（如果是二进制就是逢2进1即可，原理一样）
0x03：代码实现
Java实现如下，可能不是最优解，其他时间复杂度和空间复杂度的大家开动脑筋，发散思维想想。
public class TestAdd {
public String add(String a, String b){
a = getStr(a);
b = getStr(b);
if(a.equals("") && b.equals("")){
return "";
}
String res = "";
int addOne = 0;//用于判断是否需要进位
char[] aCharArray = a.toCharArray();
char[] bCharArray = b.toCharArray();
int aIndex = a.length();
int bIndex = b.length();
while(aIndex>0 || bIndex>0){
int aTemp = getNumber(aCharArray, aIndex);
int bTemp = getNumber(bCharArray, bIndex);
System.out.println("aTemp = " + aTemp + ", bTemp = " + bTemp);
int sum = aTemp + bTemp + addOne;
if(sum > 9){
addOne = 1;
sum = sum % 10;
}else{
addOne = 0;
}
res = sum + res;
System.out.println("res = " + res);
aIndex--;
bIndex--;
}
// 当a和b都全部加完了之后，再最后一次判断是否需要进位
if(addOne==1){
res = "1" + res;
}
return res;
}
public int getNumber(char[] cs, int index){
try{
return Integer.parseInt(String.valueOf(cs[index-1]));
}catch (Exception e) {
//如果出现异常说明数组越界返回0， 加0等于没加
}
return 0;
}
public String getStr(String a){
if(a==null){
return "";
}
return a.trim();
}
public static void main(String[] args) {
TestAdd ta = new TestAdd();
System.out.println(ta.add("19", "9111"));
}
}
扫码二维码
获取更多精彩
Java乐园
