LeetCode Add Binary 2つのバイナリ数を加算
11334 ワード
1 class Solution {
2 public:
3 string addBinary(string a, string b) {
4 if(a==""&&b=="") return "";
5 if(a=="") return b;
6 if(b=="") return a;
7 char *pa=&a[0],*pb=&b[0];
8 int na=0,nb=0;
9 int i=0;
10 int t=0,m=0;
11 while(*pa!='\0'){
12 pa++;
13 na++;
14 }
15 pa--;
16 while(*pb!='\0'){
17 pb++;
18 nb++;
19 }
20 pb--;
21 if(na>=nb){ // a
22 for(i=na-1;i>-1;i--){
23 if(i>na-nb-1){
24 m=(*pa-'0') + (*pb-'0')+t;
25 pa--;
26 pb--;
27 }
28 else if( i<na-nb &&t ==0 )
29 return a;
30 else{
31 m=(*pa-'0')+t;
32 pa--;
33 }
34 t=m/2; //
35 m=m%2; //
36 a[i]=m+'0';
37 }
38 if(t>0)
39 return ("1"+a);
40 else
41 return a;
42 }
43 else{ // b
44 for(i=nb-1;i>-1;i--){
45 if(i>nb-na-1){
46 m=(*pb-'0') + (*pa-'0')+t;
47 pa--;
48 pb--;
49 }
50 else if( i<nb-na &&t ==0 )
51 return b;
52 else{
53 m=(*pb-'0')+t;
54 pb--;
55 }
56 t=m/2; //
57 m=m%2; //
58 b[i]=m+'0';
59 }
60 if(t>0)
61 return ("1"+b);
62 else
63 return b;
64 }
65 }
66 };
題意:2つの文字列を与えて、中にそれぞれ1つのバイナリ数が保存して、バイナリを加算して結果を返して、依然として文字列型です.
考え方:2つのポインタは、後から2つのバイナリ数を加算し、1つが長い場合は、別のポインタが必ず1つの文字列をスキャンし、結果を長い文字列に保存して返します.1つの文字列がスキャンされた場合、もう1つの文字列のスキャンされていない部分を投げて追加する必要があるかどうかを判断します.これは、キャリーが0であるかどうかによって決まります.0であれば、後ろのスキャンされていない部分もスキャンしなくても、スキャンされていない文字列を直接返します.進位が0でない場合は、1つずつ掃き続けなければなりません.1つの条件を満たす限り、掃き続ける必要はありません.この条件は進位が0です.スキャンされていない文字列がスキャンされたら、もう一度キャリーを考慮する必要があります.
ツッコミ:コードは下書きコードですが、ACになったので、比較的わかりやすい角度から書きました.