剑指offer

剑指offer002-二进制加法

二进制加法

Posted by 高明 on 2020-01-01

剑指offer002-二进制加法

题目

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

 

示例 1:

输入: a = "11", b = "10"
输出: "101"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

 

提示：

  • 每个字符串仅由字符 '0' 或 '1' 组成。
  • 1 <= a.length, b.length <= 10^4
  • 字符串如果不是 "0" ，就都不含前导零。

 

注意：本题与主站 67 题相同：https://leetcode-cn.com/problems/add-binary/

Related Topics
  • 位运算
  • 数学
  • 字符串
  • 模拟

  • 👍 9
  • 👎 0

    • 思路

    思路一

    一开始就考虑到数组的方法，比较直观比如输入1011和110

    数组 0 1 2 3 4
    a 1 1 0 1
    b 0 1 1
    c 1 0 0 0 1
    1. 考虑到有进位，因此数组大小应该是a，b数组大小的最大值+1
    2. 数组a和数组b按照反方向入库，先低位再高位
    3. 计算c[i]时，如果可以除了c[i] = a[i] + b[i]，可以考虑用c[i]来存储来自i-1的进位，所以c[i] = a[i] + b[i] + c[i]

    先初始化所需要的信息

    1
    2
    3
    4
    5
    6
    int aSize = a.length();
    int bSize = b.length();
    int cSize = Math.max(aSize, bSize) + 1;
    int[] aArr = new int[cSize];
    int[] bArr = new int[cSize];
    int[] cArr = new int[cSize];

    为A，B赋值

    1
    2
    3
    4
    5
    6
    7
    8
    // 赋值
    for (int i = aSize - 1; i >= 0; i--) {
        aArr[aSize - i - 1] = Integer.parseInt(String.valueOf(a.charAt(i)));
    }

    for (int i = bSize - 1; i >= 0; i--) {
        bArr[bSize - i - 1] = Integer.parseInt(String.valueOf(b.charAt(i)));
    }

    计算c，这里要考虑如果有进位，在c[i+1]中赋值这个进位

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 计算
    for (int i = 0; i < cArr.length - 1; i++) {
        int t = aArr[i] + bArr[i] + cArr[i];
        if (t < 2) {
            cArr[i] = t;
        } else {
            cArr[i] = t - 2;
            cArr[i + 1] = 1;
        }
    }

    反向输出字符串，忽略前面的0

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    String res = "";
    int flag = 0;
    for (int i = cSize - 1; i >= 0; i--) {
        if(cArr[i] == 0 && flag == 0){
            flag = 1;
            continue;
        }
        flag = 1;
        res += cArr[i];
    }
    return res;
    1
    2
    3
    解答成功:
    执行耗时:7 ms,击败了7.63% 的Java用户
    内存消耗:38.4 MB,击败了36.93% 的Java用户

    思路二

    思路一是很正常的解题思路，完全模拟我们日常计算十进制加法，先对齐位数，按位加

    思路一的运行速度很慢，内存消耗也很多，考虑到可能是数组比较大的时候，开辟三个空间比较耗时，因此优化的思路就是减少算法的空间复杂度

    考虑直接从2个字符串的尾部开始加法，不额外开辟空间

    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
    class Solution {
        public String addBinary(String a, String b) {
            int size = Math.max(a.length(), b.length());
            int step = 0;
            String res = "";
            for (int i = 0; i < size; i++) {
                int a_j = 0;
                int b_j = 0;
                if (a.length() - i - 1 < a.length() && a.length() - i - 1 >= 0) {
                    a_j = Integer.parseInt(String.valueOf(a.charAt(a.length() - i - 1)));
                }

                if (b.length() - i - 1 < b.length() && b.length() - i - 1 >= 0) {
                    b_j = Integer.parseInt(String.valueOf(b.charAt(b.length() - i - 1)));
                }


                int s = a_j + b_j + step;
                if (s < 2) {
                    res += s;
                    step = 0;
                } else {
                    s = s - 2;
                    res += s;
                    step = 1;
                }
            }
            // 最后一个进位
            if (step == 1) {
                res += "1";
            }

            String res_new = "";
            for (int i = res.length() - 1; i >= 0; i--) {
                res_new += res.charAt(i);
            }
            return res_new;
        }
    }
    1
    2
    3
    4
    info
    解答成功:
    执行耗时:13 ms,击败了7.63% 的Java用户
    内存消耗:38.5 MB,击败了14.50% 的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
    class Solution {
        public String addBinary(String a, String b) {
            int size = Math.max(a.length(), b.length());
            int step = 0;
            String res = "";
            for (int i = 0; i < size; i++) {
                int a_j = 0;
                int b_j = 0;
                if (a.length() - i - 1 < a.length() && a.length() - i - 1 >= 0) {
                    a_j = Integer.parseInt(String.valueOf(a.charAt(a.length() - i - 1)));
                }

                if (b.length() - i - 1 < b.length() && b.length() - i - 1 >= 0) {
                    b_j = Integer.parseInt(String.valueOf(b.charAt(b.length() - i - 1)));
                }


                int s = a_j + b_j + step;
                if (s < 2) {
                    res = s + res;
                    step = 0;
                } else {
                    s = s - 2;
                    res = s + res;
                    step = 1;
                }
            }
            if (step == 1) {
                res = "1" + res;
            }
            return res;
        }
    }
    1
    2
    3
    解答成功:
    执行耗时:10 ms,击败了7.63% 的Java用户
    内存消耗:38.5 MB,击败了31.68% 的Java用户

    还是没有提升，取消string的追加，以及字符的转化

    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
    class Solution {
        public String addBinary(String a, String b) {
            int size = Math.max(a.length(), b.length());
            int step = 0;
            StringBuilder res=new StringBuilder();
            for (int i = 0; i < size; i++) {
                int a_j = 0;
                int b_j = 0;
                if (a.length() - i - 1 < a.length() && a.length() - i - 1 >= 0) {
                    a_j = a.charAt(a.length() - i - 1) - '0';
                }

                if (b.length() - i - 1 < b.length() && b.length() - i - 1 >= 0) {
                    b_j = b.charAt(b.length() - i - 1) - '0';
                }


                int s = a_j + b_j + step;
                if (s < 2) {
                    res.append(s);
                    step = 0;
                } else {
                    s = s - 2;
                    res.append(s);
                    step = 1;
                }
            }
            if (step == 1) {
                res.append("1");
            }
            return res.reverse().toString();
        }
    }
    1
    2
    3
    解答成功:
    执行耗时:3 ms,击败了17.82% 的Java用户
    内存消耗:38.4 MB,击败了56.32% 的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
    class Solution {
        public String addBinary(String a, String b) {
            int aSize = a.length();
            int bSize = b.length();
            int cSize = Math.max(aSize, bSize) + 1;
            int[] aArr = new int[cSize];
            int[] bArr = new int[cSize];
            int[] cArr = new int[cSize];

            // 赋值
            for (int i = aSize - 1; i >= 0; i--) {
                aArr[aSize - i - 1] = Integer.parseInt(String.valueOf(a.charAt(i)));
            }

            for (int i = bSize - 1; i >= 0; i--) {
                bArr[bSize - i - 1] = Integer.parseInt(String.valueOf(b.charAt(i)));
            }

            // 计算
            for (int i = 0; i < cArr.length - 1; i++) {
                int t = aArr[i] + bArr[i] + cArr[i];
                if (t < 2) {
                    cArr[i] = t;
                } else {
                    cArr[i] = t - 2;
                    cArr[i + 1] = 1;
                }
            }
            String res = "";
            int flag = 0;
            for (int i = cSize - 1; i >= 0; i--) {
                if(cArr[i] == 0 && flag == 0){
                    flag = 1;
                    continue;
                }
                flag = 1;
                res += cArr[i];
            }
            return res;
        }
    }
    FEATURED TAGS
    剑指offer
    FRIENDS