转载

LeetCode手记-Add Binary

问题描述

问题分析

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

1.字符串的长度不限，所以相应十进制数值很可能会超过int的上限。

2.二进制的加法规则是自右向左进位，需要注意，以题目示例为例：

＋ 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<char>().ToList();    var dataB = b.Reverse<char>().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;  } }