算法之兩個大數相加

兩個大數相加

思路：

* 1. 對相加的字符串進行反轉。

* 2. 比較位數，位數少的進行補0；

* 3. 逐個相加

* 4. 處理溢出

代碼如下：

@Test
public void t2() {
 String n1 = "12345600";
 String n2 = "12545";
 System.out.println(TwoBignumSum(n1, n2));
}
/**
 *
 * @param n1
 * @param n2
 * @return
 */
private String TwoBignumSum(String n1, String n2) {
 //反轉字符串
 StringBuffer sb1 = new StringBuffer(n1);
 StringBuffer sb2 = new StringBuffer(n2);
 String n11 = sb1.reverse().toString();
 String n22 = sb2.reverse().toString();
 boolean overFlow = false;
 
 //比較位數，位數少的進行補0；
 int len_n11 = n11.length();
 int len_n22 = n22.length();
 int max = len_n11 > len_n22 ? len_n11 : len_n22;
 int[] result = new int[max + 1];
 if(len_n11 > len_n22) {
 for(int i = len_n22; i < len_n11; i++) {
 n22 += "0";
 }
 } else {
 for(int j = len_n11; j < len_n22; j++) {
 n11 += "0";
 }
 }
 //逐個相加
 for(int m = 0; m < max; m++) {
 int temp = Integer.parseInt(n11.charAt(m) + "") + Integer.parseInt(n22.charAt(m) + "");
 if(overFlow) {
 result[m] = temp + 1;
 } else {
 result[m] = temp;
 }
 //處理溢出
 overFlow = overFlow(result, m);
 }

 //處理最高位
 if(overFlow) {
 result[max] = 1;
 } else {
 result[max] = 0;
 }

 //轉換為字符串
 String sr = "";
 for(int n = 0; n < max; n++) {
 sr += String.valueOf(result[n]);
 }
 return new StringBuffer(sr).reverse().toString();
}

//處理溢出
private boolean overFlow(int[] sums, int k) {
 boolean b = false;
 if(sums[k] > 10) {
 sums[k] = sums[k] - 10;
 b = true;
 }
 return b;
}