本文主要是介绍868. Binary Gap,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
868. 二进制间距
给定一个正整数
N
,找到并返回N
的二进制表示中两个连续的 1 之间的最长距离。如果没有两个连续的 1,返回
0
。
示例 1:
输入:22 输出:2 解释: 22 的二进制是 0b10110 。 在 22 的二进制表示中,有三个 1,组成两对连续的 1 。 第一对连续的 1 中,两个 1 之间的距离为 2 。 第二对连续的 1 中,两个 1 之间的距离为 1 。 答案取两个距离之中最大的,也就是 2 。
示例 2:
输入:5 输出:2 解释: 5 的二进制是 0b101 。
示例 3:
输入:6 输出:1 解释: 6 的二进制是 0b110 。
示例 4:
输入:8 输出:0 解释: 8 的二进制是 0b1000 。 在 8 的二进制表示中没有连续的 1,所以返回 0 。
提示:
1 <= N <= 10^9
解法一
//时产复杂度O(logN), 空间复杂度O(1)
class Solution {
public:int binaryGap(int N) {int count = 0, maxDist = 0;while((N & 1) != 1) N >>= 1;while(N > 0) {if(N & 1) {maxDist = max(maxDist, count);count = 1;}else count++;N >>= 1;}return maxDist;}
};
- 设置变量count记录两个1之间的距离,maxDist记录其最大值;
- 先对N反复右移,直到N的最低位为1;
- 再对N右移。过程中遇到1,就更新maxDist,并重置count为1;遇到0就简单地对count加1;
- 返回maxDist。
注意 != 的优先级比 &(按位与) 大,第一个while判断那里要加括号。
2019/07/18 11:31
这篇关于868. Binary Gap的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!