[容易]408.二进制求和

我是小小强,这是我的第6篇原创文章,阅读需要大约10分钟。


题目

LintCode:二进制求和

描述

给定两个二进制字符串,返回他们的和(用二进制表示)。

样例

a = 11
b = 1
返回 100

思路

二进制相加,主要考虑进位的情况,每位在进行相加之后,要判断之前有无进位的情况,如果有,本位要进行加1处理,同时还要考虑是否要再次向高位进位。相加结果的二进制串长度是有可能超过原数的。
最直接的方法将二进制串转换为整数,进行相加,然后将结果再转换为二进制串。

实现

非递归实现

  1. java实现

    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
    public class Solution {
    /**
    * @param a a number
    * @param b a number
    * @return the result
    */
    public String addBinary(String a, String b) {
    // Write your code here
    if (a == null || b == null) {
    return null;
    }
    return parseInt2String(parseString2(a) + parseString2(b));
    }
    public static int parseString2(String str1){
    char c = 0;
    int sum = 0;
    for (int i = 0; i < str1.length(); i++) {
    if (str1.charAt(i) == '1'){
    sum += 1<<(str1.length()-1-i);
    }
    }
    return sum;
    }
    public static String parseInt2String(int a){
    String str = "";
    if (a == 0)
    return "0";
    while (a != 0){
    str += a % 2;
    a = a/2;
    }
    String str2 = "";
    int i = str.length();
    while (i > 0 ){
    str2+=str.charAt(i-1);
    i--;
    }
    return str2;
    }
    }
  2. 结果分析
    结果:结果通过了LintCode的要求。
    分析:这种实现比较好理解,但是实现起来却没什么巧妙之处。

其它优化参考

lintcode 二进制求和 给定两个二进制字符串,返回他们的和
LIntCode-二进制求和
Short AC solution in Java with explanation

坚持原创技术分享,您的支持将鼓励我继续创作!