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

最近公共祖先__牛客网

 

求父节点：父节点 = 孩子节点/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接口

（2）AbstractSet实现Set接口

（3）HashSet继承自AbstractSet

（4）WeakHashMap继承自HashMap

6.ArrayList list = new ArrayList(20)

new的时候带参数，有object数组传了大小为20的数组，并没有扩充；如果new的时候不带参数，容量大小默认为10，当add到第11个元素时，会以数组1.5倍扩充

7.

8. switch

没有break，就会一直往下滑动执行语句

9.

（1）java.sql：提供java存取数据库的包

（2）java.swing：包含swing组件

（3）java.awt：抽象窗口工具包

（4）java.lang：包含基本包装类和String类