问题描述

 

 

 

 

 

 

 

 

 

 

 

 

问题分析

 

分析题意，此题实际是求解两个二进制数的和，但是有两点要注意：

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 > 0)            {                var a = Convert.ToInt32(s, 2);                return a;            }            return long.Parse("0");        }        public string IntToString(long i)        {            var b = string.Empty;            b= Convert.ToString(i, 2);            return b;        }}

 

正确的做法应该是将二进制字符串转为字符集合，根据进算结果相应进位或者求和，这样可以忽略int上限，复杂度也仅为O（n），代码实现如下：

 

public class Solution {    public string AddBinary(string a, string b) {         var result = string.Empty;            var dataA = a.Reverse
     
      ().ToList();            var dataB = b.Reverse
      
       ().ToList();            var maxAry = dataA.Count > dataB.Count ? dataA : dataB;            var degree = 0;            for (int i = 0; i < maxAry.Count; i++)            {                var j = 0;                var k = 0;                if (i < dataA.Count)                {                    j = dataA[i] - '0';                }                if (i < dataB.Count)                {                    k = dataB[i] - '0';                }                var sum = j + k + degree;                switch (sum)                {                    case 0:                        maxAry[i] = '0';                        degree = 0;                        break;                    case 1:                        maxAry[i] = '1';                        degree = 0;                        break;                    case 2:                        maxAry[i] = '0';                        degree = 1;                        break;                    case 3:                        maxAry[i] = '1';                        degree = 1;                        break;                }            }            if (degree == 1)            {                maxAry.Add('1');            }            maxAry.Reverse();                        for (int k = 0; k < maxAry.Count; k++)            {                result += maxAry[k];            }            return result;            }    }
      
     

 

其中值得一提的是，我将容器由Array换成List之后，速度提升了近30ms，跑出了此题C#解答的最好纪录。