【Java版oj】day11最近公共祖先、求最大连续bit数

忘是亡心i 2024-03-25 18:35 7阅读 0赞

**目录**

一、最近公共祖先

（1）原题再现

（2）问题分析

（3）完整代码

二、求最大连续bit数

（1）原题再现

（2）问题分析

（3）完整代码

--------------------

> ## 一、最近公共祖先 ##
> 
> ### （1）原题再现 ###
> 
> [最近公共祖先\_牛客题霸\_牛客网][Link 1]
> 
> 描述
> 
> 将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。
> 
> 测试样例：
> 
> 2，3
> 
> 返回：1
> 
> ### （2）问题分析 ###
> 
> 本题只是一道入门题，看似与树有关，其实只是简单的数学运算。对于二叉树父节点和子节点有一个关系：
> 
> **若i>0，双亲序号：![gif.latex?%5Cfrac%7Bi-1%7D%7B2%7D][gif.latex_5Cfrac_7Bi-1_7D_7B2_7D]；i=0，i为根结点编号，无双亲结点  
> 若![gif.latex?2i&plus;1][gif.latex_2i_plus_1]<n，左孩子序号：![gif.latex?2i&plus;1][gif.latex_2i_plus_1]，否则无左孩子  
> 若![gif.latex?2i&plus;2][gif.latex_2i_plus_2]<n，右孩子序号：![gif.latex?2i&plus;2][gif.latex_2i_plus_2]，否则无右孩子**
> 
>  **根据这样的关系，只需要将两个孩子结点不断除以2，直到两数相等时，就是两个数的最近公共祖先。**
> 
> ![2235faa69b064b77b33094d1b7631bcc.png][]
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     
>     public class LCA {
>         public int getLCA(int a, int b) {
>             // write code here
>             while (a != b) {
>                 if (a < b) {
>                     b = b / 2;
>                 } else {
>                     a = a / 2;
>                 }
>             }
>             return a;
>         }
>     }
> 
> ![2bb3fbbea94749e0b12309cf5d515ac2.png][]

> ## 二、求最大连续bit数 ##
> 
> ### （1）原题再现 ###
> 
> [求最大连续bit数\_牛客题霸\_牛客网][bit]
> 
> **描述**
> 
> 求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1
> 
> **输入描述：**
> 
> 输入一个int类型数字
> 
> **输出描述：**
> 
> 输出转成二进制之后连续1的个数
> 
> 示例1
> 
> 输入：
> 
> 200
> 
> 输出：
> 
> 2
> 
> ### （2）问题分析 ###
> 
> 这道题很明显是一道动态规划的题。跟求解最长子序列类似。
> 
> 首先需要将十进制转化成二进制，并将二进制结果保存下来，我这里使用的是栈存储，可以保证得到的二进制顺序与实际的一致，其实也可以用StringBuffer类存储，无所谓顺序。得到二进制数的方法是，将该数不断除以2，得到余数，知道除数为0。
> 
> ![a1b4ca54e8c54e41a8b1fda975e14c22.png][]
> 
> 其次求求解连续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<Integer> 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<Integer> translate(Deque<Integer> 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<Integer> stack) {
>             int length = stack.size();
>             int []oneSize = new int[length + 1];//长度是二进制数的个数+1，第0号位置用来初始化
>             oneSize[0] = 0;
>             int ans = oneSize[0];//定义初始连续1的最大数为0
>             for (int i = 1; i <= length; i++) {//从第1号位置开始将二进制比特数出栈
>                 int tmp = stack.pop();//出栈，删除栈顶元素，并将栈顶元素的值赋给tmp
>                 if (tmp == 1) {//判断连续1的个数
>                     oneSize[i] = oneSize[i - 1] + 1;
>                 } else {
>                     oneSize[i] = 0;
>                 }
>                 ans = Math.max(ans, oneSize[i]);//每进行一次二进制数的出栈，就将现阶段连续1的个数与最大值比较
>             }
>             return ans;
>         }
>     }
> 
> ![96d70111310a44ae8902d013409c2760.png][]

--------------------

![3ea9e174341b4b8daa7de7031662a6f8.png][]

--------------------

[Link 1]: https://www.nowcoder.com/practice/70e00e490b454006976c1fdf47f155d9?tpId=8&&tqId=11017&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[gif.latex_5Cfrac_7Bi-1_7D_7B2_7D]: https://latex.csdn.net/eq?%5Cfrac%7Bi-1%7D%7B2%7D
[gif.latex_2i_plus_1]: https://latex.csdn.net/eq?2i&plus;1
[gif.latex_2i_plus_2]: https://latex.csdn.net/eq?2i&plus;2
[2235faa69b064b77b33094d1b7631bcc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/95bbebb0a2c8432b82726b3e836086f8.png
[2bb3fbbea94749e0b12309cf5d515ac2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3c92cbf21b134f1d9ed0e5c9621adbfe.png
[bit]: https://www.nowcoder.com/practice/4b1658fd8ffb4217bc3b7e85a38cfaf2?tpId=37&tqId=21309&ru=/exam/oj
[a1b4ca54e8c54e41a8b1fda975e14c22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/73cfd8ba39434e8ebf88b1dffe7865fc.png
[96d70111310a44ae8902d013409c2760.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/85b666071de0424f91ceee0775978931.png
[3ea9e174341b4b8daa7de7031662a6f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f521f94f83b94f9282a5a117c633a990.png