⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【最近公共祖先】和【求最大连续bit数】，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆首发时间：🌴2022年7月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《数据结构与算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️最近公共祖先⭐️

🔐题目详情

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

测试样例：

2，3
返回：1

题目链接：最近公共祖先

💡解题思路

基本思路： 二叉树子结点与符结点的编号关系

解题思路：
我们知道，编号从1开始编号的完全二叉树，子结点编号的一半就是父结点的编号 ，根据此性质，我们可以通过比较a与b是否相等来得到公共祖先的结点编号，如果a>b，将a处以2继续比较大小，反之a<b，就将b处以2继续比较大小，a与b第一次相等时，这个a或b的值就是公共祖先结点编号。

🔑源代码

import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {
        //二叉树中，根节点编号为1，则子树的父节点下标p与子节点l, r下标有如下关系：p = l / 2 = r / 2
        //所以告诉你两个节点的编号求最近公共祖先的编号可以直接判断两结点编号的大小
        //如果 a==b 则最近公共结点编号为a或b,如果a>b，a 除以 2继续与b比较，反之b 除以 2继续与a比较
        while (a != b) {
            if (a > b) {
                a /= 2;
            } else {
                b /= 2;
            }
        }
        return a;
    }
}

🌱总结

此题考查完全二叉树的特点之一，即子结点与父节点的编号关系。
升级题：
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
剑指 Offer 68 - II. 二叉树的最近公共祖先

⭐️求最大连续bit数⭐️

🔐题目详情

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

数据范围：数据组数： $1≤t≤5$， $1≤n≤500000$

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

输入描述：

输入一个int类型数字

输出描述：

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

示例1

输入：

200

输出：

2

说明：

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

题目链接：求最大连续bit数

💡解题思路

基本思路： 右移+按位与1求连续位1的个数

解决思路：
使用一个变量来记录最大连续1的数量，在求这个连续1的数量时，采取按位与1与右移的方式来实现，按位与1的作用就是判断n的最右边一位是1还是0，右移就是更新n的最右边的一位，使得n的所有位都进行判断。

🔑源代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        //右移+按位与1,记录最大的连续位数都是1的位数
        int ans = 0;
        while (n > 0) {
            //记录当前连续bit数
            int ret = 0;
            while (n > 0 && (n & 1) == 1) {
                ret++;
                n >>= 1;
            }
            n >>= 1;
            //最终结果取ans与ret较大的值
            ans = ret > ans ? ret : ans;
        }
        System.out.println(ans);
    }
}

🌱总结

本题本质上属于位运算的基础题，只需要知道按位与能够判断某位或某些位为1，就可以解决二进制1的个数所有相同类型的题目。
类似题：
剑指 Offer 15. 二进制中1的个数