leetcode-67- Add Binary

题目描述:

Given two binary strings, return their sum (also a binary string).

For example, a = "11" b = "1" Return "100".

要完成的函数:

string addBinary(string a, string b) 

说明:

1、本题实现二进制的加法,无论有多少位二进制均可以处理。不采用常规的二进制转十进制,十进制相加,结果再转回二进制的做法,是因为这样子很麻烦,而且对于超过int表示范围的数,这种常规做法无法解决问题。可能有的朋友会说设置long类型的变量来存储和运算,但是c++只支持小于等于INT_MAX的数的计算,大于INT_MAX的数没有办法相加和相乘的。因此我们才需要设计大数相加的算法和大数相乘的算法。笔者之后应该会涉及到这个问题,之后再来记录,分享给大家。

所以这道题实现二进制相加是最好的做法。

2、两个二进制相加,笔者采用的是这样的方法,比如“1111”+“110”:

两个数先翻转,变成“1111”和“011”;

接着把两个数中短的那个,补0在最后,补足长度到两个数一样长,变成“1111”和“0110”;

接着从第一位开始,逐位相加,情况处理,像传统的人工加法一样处理,得到“10101”;

最后翻转回去,得到最终的结果“10101”。

3、这道题目不翻转字符串,也可以处理,只不过补零补在前面,然后从最后面一位开始计算,开始处理,到最前面结束。应该会比笔者下述代码更快。

代码:

#include<string>
string reverse(string a)//实现对于字符串的翻转
{
    int i=0;
    int j=a.size()-1;
    char temp;
    while(i<j)
    {
        temp=a[j];
        a[j]=a[i];
        a[i]=temp;
        j--;
        i++;
    }
    return a;
}
string addBinary(string a, string b)//主体函数
{
    string result="";//存放结果
    a=reverse(a);
    b=reverse(b);//翻转两个字符串便于处理
    int lena=a.size();
    int lenb=b.size();
    if(lena>lenb)//补零
    {
        for(int i=lenb;i<lena;i++)
        {
            b=b+"0";
        }
    }
    else
    {
        for(int i=lena;i<lenb;i++)
        {
            a=a+"0";
        }
    }
    int len=lena>lenb?lena:lenb;
    bool addflag=0;//进位标志
    for(int i=0;i<len;i++)
    {
        if(a[i]-48+b[i]-48+addflag==0)//各种情况的处理
        {
            result+="0";
            addflag=0;            
        }    
        else if(a[i]-48+b[i]-48+addflag==1)
        {
            result+="1";
            addflag=0;
        }
        else if(a[i]-48+b[i]-48+addflag==2)
        {
            result+="0";
            addflag=1;
        }
        else if(a[i]-48+b[i]-48+addflag==3)
        {
            result+="1";
            addflag=1;
        }
    }
    if(addflag==1)//最后的进位
    result+="1";
    return reverse(result);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-551-Student Attendance Record I(判断是否出现连续几个相同字符)

14760
来自专栏蓝天

常见指针定义解读

最近做的C/C++技术面试比较多,发现了一些共同的问题,对于如下所示的指针认识,多数面试者都答错了,作为过来人,这种情况还可以理解的,放在一起确实有些复杂。 ...

5310
来自专栏牛客网

校招面试手撕算法汇总

所有题目都是从面经中提取而来,持续更新。 本人也是菜鸟一枚,帖子也会相应的发布自己对于题目的解法和看法,但是可能想得不够,也希望大家能够一起讨论,一起进步。 1...

422110
来自专栏数据魔术师

基础算法| 常用排序算法小结

日常吹水 说到这个算法, 可能瞬间大家就觉得那些灰机昏膏素什么的比这个生动活泼多了。 那么,正走在算法之路上的你, 是否还在苦苦寻求修仙之路? 是否被各种排序...

34250
来自专栏醒者呆

面向程序员编程——精研排序算法

这篇文章很长,我花了好久的时间(中间公司出了bug,加班了好几天( ¯ ¨̯ ¯̥̥ ))进行整理,如有任何疑问,欢迎随时留言。 关键字:排序算法,时间...

39050
来自专栏云霄雨霁

排序----希尔排序

16500
来自专栏小筱月

各种排序算法

冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序

16730
来自专栏诸葛青云的专栏

C语言for语句用法详解

在C语言中,for语句使用最为灵活,它完全可以取代 while 语句。它的一般形式为:

9000
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第六章 归并排序

分而治之 从算法设计的分类上来说,插入排序属于增量方法。在排序好子数组A[1 ‥ j-1]后,再将单个元素A[j]插入子数组的适当位置,产生排序好的子数组A[1...

38160
来自专栏苦逼的码农

一些常用的算法技巧总结

数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些...

15230

扫码关注云+社区

领取腾讯云代金券