【每天一题】LeetCode 0067. 二进制求和

开源地址：https://github.com/jiauzhang/algorithms

题目描述

* https://leetcode-cn.com/problems/add-binary
* 给定两个二进制字符串，返回他们的和(用二进制表示)。
* 输入为非空字符串且只包含数字 1 和 0。
* 
* 示例 1:
*     输入: a = "11", b = "1"
*     输出: "100"
* 
* 示例 2:
*     输入: a = "1010", b = "1011"
*     输出: "10101"

题目描述

* 1. 二进制运算相当简单了，不同之处在于这里是操作的字符串
*    所以需要程序实现字符相加的二进制运算
* 2. 两个二进制字符相加，再加上进位位，总共有种可能的结果
*    0, 1, 2, 3，所以最直白的做法就是写四个 if 语句即可
* 3. 但是为了进一步优化，我们可以定义一个数组，如程序中所示
*    最后直接根据数组获取进位位的值和当前和的结果即可
*    本来需要四条 if 语句的操作直接一步就可以解决了！

题目描述

class Solution {
public:
    string addBinary(string a, string b) {
        if (a.size() < b.size()) {
            do_add(b, a);
            return b;
        }            
        else {
            do_add(a, b);
            return a;
        }            
    }

    void do_add(string &a, string &b) {
        char cs[4] = {0, 0, 1, 1};
        char ss[4] = {'0', '1', '0', '1'};
        char carry = 0;
        char base = '0';
        int i = a.size() - 1;
        int j = b.size() - 1;
        while (j >= 0 || (carry && i >= 0)) {
            char sum = 0;
            if (j >= 0) {
                sum += b[j] - base;
            }

            sum += a[i] - base;
            sum += carry;
            a[i] = ss[sum];
            carry = cs[sum];

            i--;
            j--;
        }

        if (carry)
            a = '1' + a;
    }
};

版权声明：本文来源博客园，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://www.cnblogs.com/jiau/p/11668128.html
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2019-11-16 23:48:51
阅读 ( 1413 )
分类：算法

【每天一题】LeetCode 0067. 二进制求和

开源地址：https://github.com/jiauzhang/algorithms

题目描述

题目描述

题目描述

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看