[leetcode] 16. Add Binary

这个题目相对有点奇怪，题目如下：

Given two binary strings, return their sum (also a binary string).
For example,

a = "11"

b = "1"

Return "100".

可能是我思路的问题吧，我之前是在考虑先将string转成int或者double，然后将二进制转为十进制进行计算，最后再将这个十进制转为二进制再转为string返回。这个思路本来是没问题的。但是。。。。。在最后一个测试用例中，他给了一个超长的二进制串，其实也是，一个长度为100的string是很正常的，但是如果这个长度为100的string是一个二进制数，这个数字就已经挺可怕的了。我又不想强行引入big num，所以我写了一套string的二进制加法器。

题解如下：

class Solution {

public:

	string addBinary(string a, string b)

	{

		reverse(a.begin(), a.end());

		reverse(b.begin(), b.end());

		int i = 0;

		int flag = 0;

		int lenA = a.length();

		int lenB = b.length();

		string c = "";

		while (i < lenA && i < lenB)

		{

			if (a[i] - '0' + b[i] - '0' + flag >= 2)

			{

				c += (a[i] - '0' + b[i] - '0' + flag) % 2 + '0';

				flag = 1;

			}

			else

			{

				c += a[i] - '0' + b[i] - '0' + flag + '0';

				flag = 0;

			}

			i++;

		}

		while (i < lenA)

		{

			if (a[i] - '0' + flag == 2)

			{

				flag = 1;

				c += "0";

			}

			else

			{

				c += a[i] - '0' + flag + '0';

				flag = 0;

			}

			i++;

		}

		while (i < lenB)

		{

			if (b[i] - '0' + flag == 2)

			{

				flag = 1;

				c += "0";

			}

			else

			{

				c += b[i] - '0' + flag + '0';

				flag = 0;

			}

			i++;

		}

		if (flag == 1)

		{

			c += "1";

		}

		reverse(c.begin(), c.end());

		return c;

	}

};

在这里用flag来表示前一位是否进位，这里要注意的就是有可能本身的两位加上进位的flag会出现3的情况，所以要考虑取余。其余的都很简单。

巴特西

[leetcode] 16. Add Binary

最新文章

热门文章