leetcode/src/Add_Binary.cpp at master · zyx4843/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
// Source : https://oj.leetcode.com/problems/add-binary/
// Author : zheng yi xiong
// Date   : 2015-02-05

/**********************************************************************************
*
* Given two binary strings, return their sum (also a binary string).

* For example,
* a = "11"
* b = "1"
* Return "100".
*
**********************************************************************************/
#include "stdafx.h"
#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
	string addBinary(string a, string b) {
		string s = a;
		int i = a.length() - 1, j = b.length() - 1;
		bool bCarry = false;
		for (; 0 <= i && 0 <= j; --i, --j)
		{
			if ('1' == a[i] && '1' == b[j])
			{
				if (bCarry)
				{
					s[i] = '1';
				}
				else
				{
					s[i] = '0';
					bCarry = true;
				}
			}
			else if ('0' == a[i] && '0' == b[j])
			{
				if (bCarry)
				{
					s[i] = '1';
					bCarry = false;
				}
				else
				{
					s[i] = '0';
				}
			}
			else
			{
				if (bCarry)
				{
					s[i] = '0';
				}
				else
				{
					s[i] = '1';
				}
			}
		}

		if (0 > i)
		{
			for (; 0 <= j; --j)
			{
				if (bCarry)
				{
					if ('0' == b[j])
					{
						s.insert(s.begin(), '1');
						bCarry = false;
					}
					else
					{
						s.insert(s.begin(), '0');
					}
				}
				else
				{
					s.insert(s.begin(), b[j]);
				}
			}
		}
		else if (0 > j)
		{
			for (; 0 <= i; --i)
			{
				if (bCarry)
				{
					if ('0' == a[i])
					{
						s[i] = '1';
						bCarry = false;
					}
					else
					{
						s[i] = '0';
					}
				}
			}
		}

		if (bCarry)
		{
			s.insert(s.begin(), '1');
		}

		return s;
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	string a = "11";
	string b = "1";
	Solution so;
	string s = so.addBinary(a, b);
	return 0;
}