问题描述
问题分析
分析题意，此题实际是求解两个二进制数的和，但是有两点要注意：
1.字符串的长度不限，所以相应十进制数值很可能会超过int的上限。
2.二进制的加法规则是自右向左进位，需要注意，以题目示例为例：
11
＋ 1
－－－－－－
100
所以直接将二进制字符串转成十进制值相加求和，再将十进制和转为二进制字符串的做法是不被接受的，虽然其复杂度只有O（1），错误做法如下；
public class Solution {
public string AddBinary(string a, string b) {
var result = string.Empty;
var sum = StringToInt(a) + StringToInt(b);
result = IntToString(sum);
return result;
}
public long StringToInt(string s)
{
if (s != null || s.Length > )
{
var a = Convert.ToInt32(s, );
return a;
}
return long.Parse("");
}
public string IntToString(long i)
{
var b = string.Empty;
b= Convert.ToString(i, );
return b;
}
}
正确的做法应该是将二进制字符串转为字符集合，根据进算结果相应进位或者求和，这样可以忽略int上限，复杂度也仅为O（n），代码实现如下：
public class Solution {
public string AddBinary(string a, string b) {
var result = string.Empty;
var dataA = a.Reverse<char>().ToList();
var dataB = b.Reverse<char>().ToList();
var maxAry = dataA.Count > dataB.Count ? dataA : dataB;
var degree = ;
for (int i = ; i < maxAry.Count; i++)
{
var j = ;
var k = ;
if (i < dataA.Count)
{
j = dataA[i] - '';
}
if (i < dataB.Count)
{
k = dataB[i] - '';
}
var sum = j + k + degree;
switch (sum)
{
case :
maxAry[i] = '';
degree = ;
break;
case :
maxAry[i] = '';
degree = ;
break;
case :
maxAry[i] = '';
degree = ;
break;
case :
maxAry[i] = '';
degree = ;
break;
}
}
if (degree == )
{
maxAry.Add('');
}
maxAry.Reverse();
for (int k = ; k < maxAry.Count; k++)
{
result += maxAry[k];
}
return result;
}
}
其中值得一提的是，我将容器由Array换成List之后，速度提升了近30ms，跑出了此题C#解答的最好纪录。