欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java 蓝桥杯 算法训练 二进制数数

程序员文章站 2024-02-21 18:58:22
...

试题 算法训练 二进制数数

资源限制
时间限制:1.0s 内存限制:256.0MB

问题描述
  给定L,R。统计[L,R]区间内的所有数在二进制下包含的“1”的个数之和。
  如5的二进制为101,包含2个“1”。
输入格式
  第一行包含2个数L,R
输出格式
  一个数S,表示[L,R]区间内的所有数在二进制下包含的“1”的个数之和。
样例输入
2 3
样例输出
3
数据规模和约定
  L<=R<=100000;

本来是使用穷举法做的,后来列了一遍二进制数 1 10 11 100 101……发现了数数字1有规律,用递推做出来了,穷举:140ms,递推:93ms
穷举:
Java 蓝桥杯 算法训练 二进制数数
递推:
Java 蓝桥杯 算法训练 二进制数数
二进制数数1规律:
  二进制数—1的个数
  长度为1:1—1
  长度为2:10—1 11—2
  长度为3:100—1 101—2 110—2 111—3
  可以发现从长度为2开始
  前半部分二进制数1的个数会是上一个长度的二进制数1的个数
  后半部分为前半部分1的个数+1
  比如:100 101的1的个数 1、2 是长度为2的1的个数1、2 ,
     110 111 的1的个数 2、3 是前半部分1的个数 1+1=2、2+1=3。后面以此类推

import java.util.Scanner;

public class Main {
	//用来存储每个二进制数中1的个数 0-1 1-2...
	static int bNum[];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int L=sc.nextInt();
		int R=sc.nextInt();
		//获取最大数的长度
		int length=Integer.toBinaryString(R).length();
		//获取从1到最大长度的二进制数个数
		int i=(int)Math.pow(2,length)-1;
		
		bNum=new int[i];//bNum初始化
		bNum[0]=1;
		//获取每个长度的二进制数中1的个数 从长度2开始
		for(int x=2;x<=length;x++)
			add(x);
		//计算从L到R的二进制中1的个数	
		int sum=0;
		for(int x=L-1;x<=R-1;x++)
			sum+=bNum[x];
		System.out.println(sum);
	}
	
	public static void add(int le) {
		//每个长度开始的下标 比如:长度2 开始下标为1
		int s=(int)Math.pow(2,le-1)-1;
		//每个长度结束的下标 比如:长度2 结束下标为3
		int e=(int)Math.pow(2,le)-1;
		//上一个长度开始的下标 比如:长度2时 bs获取长度1的开始下标为0
		int bs=(int)Math.pow(2,le-2)-1;
		//每个长度前半部分的赋值
		for(int x=s;x<s+(e-s)/2;x++)
			bNum[x]=bNum[bs++];
		//每个长度后半部分的赋值
		for(int x=s+(e-s)/2;x<e;x++)
			bNum[x]=bNum[s++]+1;


	}
}