Java题目训练——最近的公共祖先和求最大连续bit数

分手后的思念是犯贱 2023-09-30 20:41 76阅读 0赞

### 一、最近的公共祖先 ###

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

测试样例：

> 2，3  
> 返回：1

**题目详解：**

满二叉树的子节点与父节点之间的关系为root = child / 2，所以利用这个关系，如果a ！= b，就让其中的较大数除以2， 如此循环直到a == b，即是原来两个数的最近公共祖先。

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数 ###

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

1.  数据范围：数据组数：1<=t<=5 ，1<=n<=500000，

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

1.  输入描述：输入一个int类型数字

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

示例

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

**题目详解：**

利用双指针法，循环遍历整个字符串，遇到1就让右指针后移一位，直到右指针遇到0，记录左右指针差值，即为连续个1的长度，与之前记录的最大长度进行比较更新，然后将左指针更新至此时位下一位，右指针继续向前，直至遍历结束，输出最大值。

import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int num = in.nextInt();
            if(num == 0){
                System.out.println(0);
            } else {
                String s = Integer.toBinaryString(num);
                System.out.println(fun(s));
            }
        }
     
        public static int fun(String s){
            int start = 0;
            int end = 0;
            int max = 0;
            int count = 0;
            while(end < s.length()){
                if(s.charAt(end) == '1'){
                    count++;
                    max = Math.max(max,count);
                }else {
                    start = end;
                    count = 0;
                }
                end++;
            }
            return max;
        }
    }

如有建议或想法，欢迎一起学习讨论~