> 文章列表 > 强训之【求最大连续的bit数和最近公共祖先】

强训之【求最大连续的bit数和最近公共祖先】

强训之【求最大连续的bit数和最近公共祖先】

目录

  • 1.求最大连续的bit数
    • 1.1题目
    • 1.2思路
      • 1.2.1暴力求解
      • 1.2.2 字符串分割求解
      • 1.2.3 位运算“与”求解
    • 1.3代码
      • 1.3.1暴力求解代码
      • 1.3.2字符串分割求解代码
      • 1.3.3位运算“与”求解
  • 2.最近公共祖先
    • 2.1题目
    • 2.2思路
    • 2.3代码
  • 3.选择题

1.求最大连续的bit数

1.1题目

链接: link
描述
求一个int类型数字对应的二进制数字中1的最大连续数,例如3的二进制为00000011,最大连续2个1

数据范围:数据组数:1\\le t\\le 5\\1≤t≤5 ,1\\le n\\le 500000\\1≤n≤500000
进阶:时间复杂度:O(logn)\\O(logn) ,空间复杂度:O(1)\\O(1)
输入描述:
输入一个int类型数字

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

示例1
输入:
200

输出:
2

说明:
200的二进制表示是11001000,最多有2个连续的1。

1.2思路

1.2.1暴力求解

暴力求解是最容易理解的方法。

 将整数求余后,利用字符串拼接,因为此时的二进制数是反的,所以要反转一下。
注意要将StringBuilder的sb字符串变为String类型的。

 然后判断每一位是否等于1,等于1就count++,遇到0的时候判断count和ret的大小,将大值给ret,并且将count置为0,再循环。

为了防止最后几位都是1,所以最后判断一下,count和ret的大小,将大的一方,赋值给ret。

1.2.2 字符串分割求解

利用Integer.toBinaryString()直接将整数变为二进制数的字符串形式。
然后利用库函数spilt,用“0”作为分割线,字符数组的每一个都是字符1,最后判断字符数组中的最长字符串的长度。

1.2.3 位运算“与”求解

大家都知道**任何一个数&1,如果这个数的二进制末尾是1,那么结果就是1,如果末尾是0,那么结果就是0.**
根据这个判断,结果等于1,count++,遇到0的时候判断count和ret的大小,将大值给ret,并且将count置为0,再循环。

为了防止最后几位都是1,所以最后判断一下,count和ret的大小,将大的一方,赋值给ret。

1.3代码

1.3.1暴力求解代码

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n=in.nextInt();StringBuilder sb=new StringBuilder();while(n>0){int a=n%2;sb.append(a+"");n=n/2;}sb.reverse();String str=sb.toString();char[] ch=str.toCharArray();int count=0;int ret=0;for(int i=0;i<ch.length;i++)//1110101{if(ch[i]=='1'){count++;//2//1}if(ch[i]=='0'){if(count>ret){ret=count;//2}count=0;}}if(count>=ret){ret=count;}System.out.println(ret);}
}

1.3.2字符串分割求解代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n=in.nextInt();String str1=Integer.toBinaryString(n);String[] str=str1.split("0");int count=0;for(int i=0;i<str.length;i++){if(str[i].length()>count){count=str[i].length();}}System.out.println(count);}
}

1.3.3位运算“与”求解

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

2.最近公共祖先

2.1题目

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

测试样例:
2,3
返回:1

2.2思路

首先判断A是否等于B,如果等于的话,任何一个都是最近公共祖先。

当A!= B的时候,我们知道父节点=孩子节点/2,所以我们让,较大的数/2,再和另外一个判断,如果不相等就在取最大的数,然后除以2,知道A和B相等。这个时候,A的值,就是父亲节点。
强训之【求最大连续的bit数和最近公共祖先】

2.3代码

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

3.选择题

  1. 下面哪个标识符是合法的?(D
    A 9HelloWorld
    B _Hello World
    C Hello*World
    D Hello$World

标识符开头不能是数字,中间也不能有空格,也不能有 * 等特殊的字符

2.以下java程序代码,执行后的结果是(C
java.util.HashMap map=new java.util.HashMap();
map.put(“name”,null);
map.put(“name”,“Jack”);
System.out.println(map.size());
A 0
B null
C 1
D 2

map是有键值对的,键(只有一个)和值(可以有多个)
当开始键为 name 值为null
后来键不变,值覆盖为jack
所以大小还是1个

  1. Java中的集合类包括ArrayList、LinkedList、HashMap等类,下列关于集合类描述错误的是C

A ArrayList和LinkedList均实现了List接口
B ArrayList的访问速度比LinkedList快
C 添加和删除元素时,ArrayList的表现更佳
D HashMap实现Map接口,它允许任何类型的键和值对象,并允许将null用作键或值

ArrayList的访问速度比LinkedList快,因为ArrayList的底层是数组,LinkedList是链表
添加和删除元素时,ArrayList更慢,LinkedList更快,因为ArrayList的底层是数组,添加的时候需要一个一个访问,链表直接添加一个节点就可以

  1. 以下描述正确的是(B
    A CallableStatement是PreparedStatement的父接口
    B PreparedStatement是CallableStatement的父接口
    C CallableStatement是Statement的父接口
    D PreparedStatement是Statement的父接口

PreparedStatement是CallableStatement的父接口
Statement是CallableStatement的父接口

  1. 下面有关重载函数的说法中正确的是(C
    A 重载函数必须具有不同的返回值类型
    B 重载函数形参个数必须不同
    C 重载函数必须有不同的形参列表
    D 重载函数名可以不同

重载可以是,参数类型不同,个数不同,返回值可以不同,函数名必须相同

  1. 下列关于容器集合类的说法正确的是?(C
    A LinkedList继承自List
    B AbstractSet继承自Set
    C HashSet继承自AbstractSet
    D WeakMap继承自HashMap

LIst和Set是接口,只能实现不能继承

  1. ArrayList list = new ArrayList(20);中的list扩充几次(A
    A 0
    B 1
    C 2
    D 3

当我们new的时候给定大小20,此时不会扩容
但是当我们不给与大小的时候,默认为10,当我们添加到第11个时候,就会扩容1.5倍

强训之【求最大连续的bit数和最近公共祖先】
8. 以下程序的输出结果是?(B
public class Example {
String str = new String(“good”);
char[] ch = { ‘a’, ‘b’, ‘c’ };
public static void main(String args[]) {
Example ex = new Example();
ex.change(ex.str, ex.ch);
System.out.print(ex.str + " and ");
System.out.print(ex.ch);
}
public static void change(String str, char ch[])
{
str = “test ok”;
ch[0] = ‘g’;
}
}
A good and abc
B good and gbc
C test ok and abc
D test ok and gbc

  1. 下面的方法,当输入为2的时候返回值是多少?(D
    public static int getValue(int i) {
    int result = 0;
    switch (i) {
    case 1:
    result = result + i;
    case 2:
    result = result + i * 2;
    case 3:
    result = result + i * 3;
    }
    return result;
    }
    A 0
    B 2
    C 4
    D 10

当i=2的时候,我们先执行case 2语句,此时result=4,不过因为没有break,所以还会往下执行case 3.此时结束result=4+2*3=10。
需要注意,此时** i 依然等于2**

  1. 提供Java存取数据库能力的包是(A
    A java.sql
    B java.awt
    C java.lang
    D java.swing