刷题_11：最近公共祖先 and 求最大连续bit数

心已赠人 2023-09-29 23:24 80阅读 0赞

### 一.最近公共祖先 ###

**题目链接：**

> [最近公共祖先][Link 1]

**题目描述：**

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

**示例1：**

> **输入：  
> 2，3  
> 输出：  
> 1**

**个人总结：**

> **这棵二叉树是一颗无穷大的满二叉树，且节点值按层数从左到右编号，根节点为1，根据根节点与其左右孩子的关系，即 左孩子 = 2 \* 根节点，右孩子 = 2 \* 根节点 + 1，反过来即 根节点 = 左孩子 (或者右孩子) / 2，通过该关系我们可以很快找到最近公共祖先。**

**代码实现：**

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

--------------------

### 二.求最大连续bit数 ###

**题目链接：**

> [求最大连续bit数][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。**

**个人总结：**

> **使用位运算来写，较简单。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
        
                int num = sc.nextInt();
                int len = 0;
                int max = 0;
                while (num != 0) {
        
                    if ((num & 1) != 0) {
        
                        len++;
                        max = Math.max(max, len);
                    } else {
        
                        len = 0;
                    }
                    num = num >> 1;
                }
                System.out.println(max);
            }
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/70e00e490b454006976c1fdf47f155d9?
[bit]: https://www.nowcoder.com/questionTerminal/4b1658fd8ffb4217bc3b7e85a38cfaf2