目录

最近公共祖先

求最大连续bit数

最近公共祖先

链接:最近公共祖先_牛客题霸_牛客网 (nowcoder.com)

来源:牛客网

描述

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。

  测试样例：

2，3

返回：1

理解题意:最近公共祖先表示距离两个节点最近的公共父节点，这道题考察二叉树。

怎么做:

题目所描述的满二叉树如下： 1 / 2 3 / / 4 5 6 7 上述树中子节点与父节点之间的关系为root = child / 2所以如果a ！= b，就让其中的较大数除以2， 如此循环直到a == b 即是原来两个数的最近公共祖先 比如： 2和7的最近公共祖先：7/2 = 3 ---> 3/2 = 1， 2/2 = 1， 得到1为它们的公共祖先

 直接上代码:

class LCA {
public:
    int getLCA(int a, int b) {
        // write code here
        while(a != b){
            if(a > b){
                a = a / 2;
            }else{
                b = b / 2;
            }
        }
        return a;
    }
};

求最大连续bit数

链接:求最大连续bit数_牛客题霸_牛客网 (nowcoder.com)

来源:牛客网

描述

求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1

数据范围：数据组数：1le tle 51≤t≤5 ，1le nle 5000001≤n≤500000 

进阶：时间复杂度：O(logn)O(logn) ，空间复杂度：O(1)O(1) 

输入描述：

输入一个int类型数字

输出描述：

输出转成二进制之后连续1的个数

示例1

输入：

200

复制输出：

2

复制说明：

200的二进制表示是11001000，最多有2个连续的1。  

理解题意:将数据转化为2进制求出最大的连续1的次数 

怎么做:根据位运算，获取每一位的二进制值。获取第i位的值： (n >> i) & 1。如果1连续，则计数累加，如果不连续，则从0开始计数。

直接上代码

#include 
#include 
using namespace std;
int main(){
    int n;
    while(cin >> n){
        int count = 0;//计数
        int maxcount = 0;//保存最大的数
        while(n){
            if(n & 1){//让数字和1相&  如果为1
                count++;//这里的count++
                maxcount = max(count, maxcount);//将count中的值比较并且将最大的赋值给maxcount
            }else{
                count = 0;//如果为0,就让这里的count置为0
            }
            n = n >> 1;//让输入的数字向右移动
        }
        cout << maxcount << endl;
    }
}

但是上述代码还是有问题,如果输入的为负数时,负数移动补位为1,那么就会陷入死循环

所以这里有了新的解题

#include 
#include 
using namespace std;
int main(){
    int n;
    while(cin >> n){
        int count = 0;//计数
        int maxcount = 0;//保存最大的数
        for(int i = 0; i < 32; i++){//给一个32位的循环,8位也可以,题目要求一个字节
            if(n & (1 << i)){//这里让1往左移动i位,与下面不同的是1在移动
                count++;
                maxcount = max(count, maxcount);
            }else{
                count = 0;
            }
        }
        
        cout << maxcount << endl;
    }
}