目录

 一、最近公共祖先

（1）原题再现

（2）问题分析

（3）完整代码

 二、求最大连续bit数

（1）原题再现

（2）问题分析

（3）完整代码

 一、最近公共祖先

（1）原题再现

最近公共祖先_牛客题霸_牛客网

描述

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

测试样例：

2，3

返回：1

（2）问题分析

        本题只是一道入门题，看似与树有关，其实只是简单的数学运算。对于二叉树父节点和子节点有一个关系：

若i>0，双亲序号：；i=0，i为根结点编号，无双亲结点
若，否则无左孩子
若，否则无右孩子

        根据这样的关系，只需要将两个孩子结点不断除以2，直到两数相等时，就是两个数的最近公共祖先。

（3）完整代码

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

 二、求最大连续bit数

（1）原题再现

求最大连续bit数_牛客题霸_牛客网

描述

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

输入描述：

输入一个int类型数字

输出描述：

输出转成二进制之后连续1的个数

示例1

输入：

200

输出：

2

（2）问题分析

        这道题很明显是一道动态规划的题。跟求解最长子序列类似。

        首先需要将十进制转化成二进制，并将二进制结果保存下来，我这里使用的是栈存储，可以保证得到的二进制顺序与实际的一致，其实也可以用StringBuffer类存储，无所谓顺序。得到二进制数的方法是，将该数不断除以2，得到余数，知道除数为0。

        其次求求解连续1的最长序列 ，使用动态规划的思想。

状态：
子状态：F(i): 从0到i的连续一的个数
状态递推：

        如果当前下标位置为i的值为1时，连续1的个数就加一
              F(i) = F(i-1)+1

        如果当前下标位置为i的值为0时，连续1的个数就变为0

              F(i) = 0
初始化： 
              F(0) = 0(最开始是连续1的个数为0)
返回结果：右下角
              F(length)(数组长度)

每进行一次状态递推，就判断一次最大值和当前状态连续1的个数谁更大。

（3）完整代码

import java.util.*;
public class Main {public static void main(String[] args) {Deque stack = new LinkedList<>();//定义的栈存储二进制数Scanner sc = new Scanner(System.in);int num = sc.nextInt();stack = translate(stack, num);System.out.println(continueMax(stack));}public static Deque translate(Deque stack, int num) {//十进制转二进制int ans = 0;while (num != 0) {int tmp = num % 2;stack.push(tmp);//将余数压入栈中num /= 2;}return stack;}public static int continueMax(Deque stack) {int length = stack.size();int []oneSize = new int[length + 1];//长度是二进制数的个数+1，第0号位置用来初始化oneSize[0] = 0;int ans = oneSize[0];//定义初始连续1的最大数为0for (int i = 1; i <= length; i++) {//从第1号位置开始将二进制比特数出栈int tmp = stack.pop();//出栈，删除栈顶元素，并将栈顶元素的值赋给tmpif (tmp == 1) {//判断连续1的个数oneSize[i] = oneSize[i - 1] + 1;} else {oneSize[i] = 0;}ans = Math.max(ans, oneSize[i]);//每进行一次二进制数的出栈，就将现阶段连续1的个数与最大值比较}return ans;}
}

​