【day11】最近公共祖先最大连续bit数

news/2024/7/5 3:23:22

最近公共祖先__牛客网

求父节点：父节点 = 孩子节点/2

（1）输入a ，b 如果a==b，表示ab的公共祖先就是ab本身

（2）如果ab不相同，循环while哪个大，哪个除以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数_牛客题霸_牛客网

该题的解题思路

（1）任何不为0的数按位与1，结果都是1，也就是最低为是1

所以，二进制数，看最低位，让n&1，如果n&1等于1，就代表最低位为1，就计数count++

接着让n右移1，更新n的最低位为倒数第二位，接着循环上述代码，如果为0，count清空，同时记录下count清空前的结果

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int count = 0;
            int modCount = 0;
            while(n != 0){
                if((n & 1) == 1){
                    count++;
                    modCount = Math.max(count,modCount);
                }else{
                    count = 0;
                }
                n >>= 1;
            }
            System.out.println(modCount);
        }
    }
}

//一些考点

1.标识符：开头不能是数字，不能有空格，不能有*号，可有$符

2.Map -》键值对 -》key-value

key和value可以为null

如果put两次，在第二次put中，key与第一次put相同，就相当于操作第一个键值对，如果value不同会被覆盖，这时map里只有一个值，不是两个值

3.Statement > PrepareStatement > CallableStatement (>表示父类关系)

4.重载

（1）函数名必须相同

（2）返回值可相同可不相同

（3）必须有不同的形参列表：个数同类型排列不同/个数不同

5.接口是实现，不是继承

（1）LinkedList实现List接口