面接アルゴリズム問題(2)--2つの大きな数を加算

2つの大きな数を加算
これは频繁に出てくるアルゴリズムの问题だそうで、○○サイトでは上位にランクインしています.
仕事を探す前に、同僚が一度言ったことがありますが、私は気にしていません.ちょうど私の最初の面接で出会ったのです.
2つの大きな数を加算します.
1、整数です.
2、二つの数は無限大で、longは入れられない.
3、BigIntegerは使えない;
4、いかなる包装類が提供した演算方法ではいけない.
5、両方の数は文字列で提供されます.
2つの文字列の数字は、どのように加算しますか?
実は簡単で、核心点はASCIIコードと加算進位の問題です.
比喩文字タイプの'9'はどのようにintの9に変換しますか?
'9' - '0' = 9.このアルゴリズムは理解できますか?
charタイプが算数演算を行うと自動的にintタイプに変換されますか?
文字9のASCII値は文字0より9個多いのではないでしょうか.これが最初のキーです.
2つ目のポイントは、加算時のキャリーに注意することです.
2つの文字列の数字は、文字配列で処理してもよいし、StringBufferで処理してもよい.
StringBufferはappendのたびに後に追加されますが、デジタルキャリーを処理する場合は前に処理する必要があります.
実はStringBufferにはreverse()という方法があり、文字列を反転します.
例を挙げて、処理プロセス全体を例えます.
String str1 = "123459";
string str2 = "123";
2つの文字列を反転する必要があります.なぜですか.
加算処理は右端のビットから始まるので、キャリー処理もあります.
reverse()メソッドの処理を呼び出した後:
String str1 = "954321";
string str2 = "321";
今はやりやすいので、席を揃えました.加算を開始できますので、キャリーに注意してください.
int carry = 0;
計算ビット:
int value = str1.charAt(0) + str2.charAt(0) - 2*'0' + carry;
上の行のコードは理解できますか?
"9'+'3'-2*'0'+carry;
なぜ-2*'0?
文字が算術演算されると、ASCII値に変換されて演算されます.
57+51-2*48+0;
9+3+0に等しいのではないでしょうか.
はい、くだらないことは言わないでください.加算値は12です.
直接12をビットに格納しますか?もちろんそうではありません.キャリーの10部分をcarry変数に格納し、10桁の数値加算を行う場合に便利です.
carry = 12/10;
value = 12 % 10;
次にvalueの値を最終ビットに保存します.
上記の手順を1回行います.
最後に、入力された2つの文字列の数字の長さは必ずしも等しくないことに注意してください.
最初のループでは、短い文字列の未終了点で、2つの数値とcarryの加算とキャリーを計算します.
その後,長い文字列に基づいて長い部分サイクルでcarryに加算し,キャリーを処理する.
上はすべて核心点を言って、直接コードを引っ張って、注釈があります:

public static void main(String[] args) {
	String str1 = "123459";
	String str2 = "123";
	System.out.println(add(str1, str2));//123582
}

private static String add(String str1, String str2) {
	//        null     ，       
	if (str1 == null || "".equals(str1)) {
		return str2;
	}
	if (str2 == null || "".equals(str2)) {
		return str1;
	}
	int maxLength = Math.max(str1.length(), str2.length());
	//            ，               ，           
	StringBuffer result = new StringBuffer(maxLength + 1);

	//       
	str1 = new StringBuffer(str1).reverse().toString();
	str2 = new StringBuffer(str2).reverse().toString();

	//         ：
	//954321
	//321
	int minLength = Math.min(str1.length(), str2.length());
	//  
	int carry = 0;
	//       
	int currentNum = 0;
	//    
	int i = 0;
	for (; i < minLength; i++) {
		//               ，    ，     
		currentNum = str1.charAt(i) + str2.charAt(i) - 2 * '0' + carry;
		//    
		carry = currentNum / 10;
		//         
		currentNum %= 10;
		//                 
		result.append(String.valueOf(currentNum));
	}
	if (str1.length() < str2.length()) {
		//  
		str1 = str2;
	}
	for (; i < str1.length(); i++) {
		//               ，    ，     
		currentNum = str1.charAt(i) - '0' + carry;
		//    
		carry = currentNum / 10;
		//         
		currentNum %= 10;
		//                 
		result.append(String.valueOf(currentNum));
	}
	//         (      ，            )
	if (carry > 0) {
		result.append(String.valueOf(carry));
	}
	//         ，   
	return result.reverse().toString();
}

もしあなたがもっと良い考えがあれば、伝言を歓迎します.