刷题(十二) 最近公共祖先 求最大连续bit数

刷题(十二) 最近公共祖先 求最大连续bit数

最近公共祖先 求最大连续bit数

• 最近公共祖先
• • 思路
  • • 代码
• 求最大连续bit数
• • 思路
  • • 代码

最近公共祖先

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

思路 代码

根据上面的二叉树父节点和子节点之间的关系root=child/2,如果a!=b,就让其中较大的除以2，如此循环知道ab，即是两个数的最近公共祖先，如a=2,b=3，b=3/2=1,2!=1,a=2/2=1,此时ab，所以最近的公共祖先是1.

import java.util.*;
public 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;
    }
}d 

求最大连续bit数

题目描述：求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1
本题含有多组样例输入。
输入描述：输入一个int类型数字。
输出描述：输出转成二进制之后连续的1的个数。
示例：
输入：
3
5
200
输出：
2
1
2
说明：3的二进制表示11，最多有2个连续的1.
5的二进制表示101，最多只有1个连续的1.
链接：求最大连续bit数

思路

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

代码

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