当前位置：首页 > news >正文

【编程强训11】最近公共祖先+求最大连续bit数

news 来源：原创 2024/4/29 23:21:18

1.最近公共祖先 ->链接

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

【测试样例】：

2，3

返回：1

【题目解析】：

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

【解题思路】：

题目所描述的满二叉树举例如下：

我们以2和7为例，寻找2、7的最近公共祖先。

我们知道上述树中子节点与父节点之间的关系为root = child / 2，将a=2,b=7

所以如果a ！= b，就让其中的较大数除以2，如此循环直到a == b 即是原来两个数的最近公共祖先.

比如： 2和7的最近公共祖先：7/2 = 3 —> 3/2 = 1，

代码实现：

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

2.求最大连续bit数 ->链接

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

$数据范围：数据组数：1\le t\le 5\1≤t≤5 ，1\le n\le 500000\1≤n≤500000 进阶：时间复杂度：O(logn)\O(logn) ，空间复杂度：O(1)\O(1)$

【输入描述】
输入一个int类型数字

【输出描述】
输出转成二进制之后连续1的个数

示例1

输入： 200

输出： 2

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

【题目解析】：

这道题考察位运算

【解题思路】：

我们以200为例：

首先定义count来计数连续1的个数，定义max_count来更新当前最多的连续1(两者均初始化为0)

我们通过200的二进制和1的二进制进行按位与操作，来判断当前最低位是否为1，

如果为1

count++;
max(max_count,count);

如果不为1，停止连续1的累加，将count置为0，即count=0;

进行一次判断之后，通过右移一位当前数来获取次低位的判断，直到右移32位之后该数变为0，停止。

代码实现：

#include <iostream>
//#include<algorithm>
using namespace std;

int main()
{
    int n=0;
    while(cin>>n)//多次输入
    {
        int count=0;
        int max_count=0;
        
        while(n)//右移32为之后n变为0
        {
            if(n&1)
        {
            count++;
            max_count=max(max_count,count);
        }
            else{
            count=0;
            }
            n=n>>1;
        }
      cout<<max_count<<endl;  
    }
    return 0;
}