day11—编程题

1.第一题

1.1题目

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

1.2涉及的相关知识

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树

满二叉树中：parent = child/2

1.3思路

1. 找到a，b两个节点中较大的结点数，让它的值除以2，直到两个数相等
2. 返回循环后a，b两数的任意一个值

1.4解题

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

2.第二题

2.1题目

描述：
求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1
输入描述：
输入一个int类型数字
输出描述：
输出转成二进制之后连续1的个数

2.2思路

1. 定义两个变量分别存储当前1连续出现的次数和1连续出现的最多的次数
2. 让输入的数与1相与，如果结果为1，次数就加1，否则就把当前1连续出现的次数置为0，然后让输入的数左移一位
3. 输出1连续出现的最多的次数

2.3解题

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