二进制的的加法

二进制加法

分析：

这道题目当中的二进制数字是以字符串的形式来保存的，如果将字符串转化为位int类型或者long long 类型，string 的长度特别长的时候，那么就会超出时间限制

参考解法

加法操作只能针对两个字符串进行。可以参照十进制的加法来完成。回忆一下小学学习的十进制加法，首先将字符的右端对齐，然后从他们个位开始从右向左相加同一位置的两个数字，如果有进位要进一位。

二进制加法

1. 获取字符串的长度-从字符串的右边开始相加
2. 逢二进1
3. 当两个数位加起来等于2时就要产生进位

超级小白思路代码

class Solution {
public:string addBinary(string a, string b) {int lena=a.length()-1;int lenb=b.length()-1;string s;//记录当前是否有进位int current=0;while(lena>=0||lenb>=0){//由于是以字符的形式，所以要减去字符0来获取数字再进行相加，同时还要记录进位int recordA= lena>=0? a[lena--]-'0':0;int recordB= lenb>=0? b[lenb--]-'0':0;int sum=recordA+recordB+current;current=sum>=2?1:0;sum=sum>=2?sum-2:sum;//上面减去的是0字符串，所以要在下面加'0' 变成字符串形式s.push_back(sum+'0');}//如果最后产生了进位的话，然后再把进位加进去if(current==1){s.push_back('1');}//因为我们是从最右边开始计算的，所以要对其进行反转reverse(s.begin(),s.end());return s;}
};

前n个数字中二进制中的个数

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

分析

高效方法

i&（i-1）将整数最右边的1变成0
整数减去1，即其最右边的1变成0
如果右边还有0，则右边所有的0都变成1
其左边的值不发生变化
比如 1000
1000-1=0111
1000&0111=0000
那么其1的个数就等于 其 i&(i-1)+1
可以再举一个例子
101
101-1=100
101&100=100
101中的个数就等于 100当中1的个数加上1

所以在这里我们就得到了一个方程其
i当中1个个数=i&(i-1)+1
那这样以来我们就可以利用这个方程来进行求解

思路清晰上代码

class Solution {
public:vector<int> countBits(int n) {//同时在定义arr的时候要给长度vector<int>arr(n+1);//在这里要注意i==0得时候是0,所以在for 循环得时候要从1开始arr[0]=0;for(int i=1;i<=n;i++){arr[i]=arr[i&(i-1)]+1;}return arr;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！