868. Binary Gap

2023-12-21 15:58
文章标签 binary gap 868

本文主要是介绍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;}
    };
    1. 设置变量count记录两个1之间的距离,maxDist记录其最大值;
    2. 先对N反复右移,直到N的最低位为1;
    3. 再对N右移。过程中遇到1,就更新maxDist,并重置count为1;遇到0就简单地对count加1;
    4. 返回maxDist。

    注意 != 的优先级比 &(按位与) 大,第一个while判断那里要加括号。

    2019/07/18 11:31

    这篇关于868. Binary Gap的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



    http://www.chinasem.cn/article/520600

    相关文章

    uva 575 Skew Binary(位运算)

    求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

    226 Invert Binary Tree

    //226 Invert Binary Tree//算法思路:主要使用递归算法public class Solution {public TreeNode invertTree(TreeNode root) {//1 出口 空节点if (root==null)return null;//2 递归 调用自己TreeNode left = root.left;TreeNode right = ro

    [LeetCode] 863. All Nodes Distance K in Binary Tree

    题:https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/ 题目大意 求给树中,距给定 结点 指定长度的 所有结点的val 思路 tree -> graph 、 bfs 先遍历树,并用map记录每个结点的父结点 ,将树变为图,然后 bfs。 /*** Definition for a binary tree

    LeetCode 67 Add Binary

    题意: 两个二进制数相加,输出结果 思路: 各种模拟均可,比如先把A和B倒过来,再按位相加,最后把结果再倒回来。 不过为了快,我是这样做的——假设A比B长,那么我对位相加B的长度。这时如果没有进位,那么A长出B的部分就不会变了;如果有进位,那么继续往A的高位加,直到某一次进位为0,那么更高位的A就不变了;如果直到最后还有进位,那就最前面添加一个最高位1。 代码: cla

    Classical Binary Search

    Find any position of a target number in a sorted array. Return -1 if target does not exist. Example Example 1: Input: nums = [1,2,2,4,5,5], target = 2Output: 1 or 2 Example 2: Input: nums = [1,

    Cousins in binary tree

    Input: root = [1,2,3,null,4,null,5], x = 5, y = 4Output: true Input: root = [1,2,3,4], x = 4, y = 3Output: false 思路:就是level order traverse,BFS,记录一下parent, curNode, Depth; /*** Definition for

    Average of Levels in Binary Tree

    Input:3/ \9 20/ \15 7Output: [3, 14.5, 11]Explanation:The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11]. 思路:就是一个level order trav

    Closest Leaf in a Binary Tree

    Input:root = [1,2,3,4,null,null,null,5,null,6], k = 2Diagram of binary tree:1/ \2 3/4/5/6Output: 3Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the no

    Binary Tree - Lowest Common Ancestor 题型总结

    Lowest Common Ancestor of a Binary Search Tree 思路:这题跟 Lowest Common Ancestor of Binary Tree 一模一样。思路:就是找p的节点在不在左支,或者右支,找到各自左右节点,然后进行比较,如果两者不一样,说明当前的root就是lowest 父节点,如果左边为空,那就都在右边,返回右边的即可,如果右边为空,那就都在左

    BLE Profile(GATT与GAP)

    一. 引言 现在低功耗蓝牙(BLE)连接都是建立在 GATT (Generic Attribute Profile) 协议之上,GATT 是一个在蓝牙连接之上的发送和接收很短的数据段的通用规范,这些很短的数据段被称为属性(Attribute)。 二. GAP 详细介绍GATT之前,需要了解GAP(Generic Access Profile),它在用来控制设备连接和广播。GAP使你的设备被其