首页 > 试题广场 >

光棍指数

[编程题]光棍指数
  • 热度指数:280 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
对于一个正整数,我们认为它的光棍指数是它二进制表示下1的个数。
通常认为光棍指数越高,这个数就越孤单。那么问题来了,对于给定的[a,b]区间中。最孤单的数字是谁呢?
如果光棍指数相同,最孤单的就是最小的那个数。

输入描述:
第一行一个整数 T (1≤T≤10^4),表示问题数。
接下来 T 行,每行两个整数 a,b (0≤a≤b≤2^31−1)。数据之间用一个空格分隔。


输出描述:
对于每个问题,输出一行 Case x: y,其中 x 是问题编号,从 1 开始,y 是答案
示例1

输入

2
0 14
100 1000

输出

Case 1: 7
Case 2: 511
package 位运算;

/*
 * 
链接:https://www.nowcoder.com/questionTerminal/0e28cf34d05d422ea4a8fee8b4772c4a?orderByHotValue=1&page=1&onlyReference=false
来源:牛客网

对于一个正整数,我们认为它的光棍指数是它二进制表示下1的个数。
通常认为光棍指数越高,这个数就越孤单。那么问题来了,对于给定的[a,b]区间中。最孤单的数字是谁呢?
如果光棍指数相同,最孤单的就是最小的那个数。

解题思路:
看一下数字规模,穷举每个数求其二进制表示中1的个数,显然会超时。
可以这样想,既然要求"1"最多的数,那么我就对一个数从低位开始,将其低位上的0不断换成1,比较换之后的结果是否在区间内就行了。
关键:result |= result + 1;
 */
import java.util.Scanner;

public class 光棍指数 {    public static void main(String[] args) {    Scanner sc = new Scanner(System.in);    int T = sc.nextInt();    for (int i = 1; i <= T; i++) {    long a = sc.nextLong();    long b = sc.nextLong();    long result = a;    while ((result | (result + 1)) <= b) {    result |= result + 1;    }    System.out.println("Case " + i + ": " + result);    }    }
}

编辑于 2018-07-11 22:48:36 回复(1)
T=int(input())
a=[]
def sum(l):#统计 '1' 的 个数
    num=0
    for i in list(l):
        if i=='1':
            num=num+1
    return num
for i in range(T):
    # a[i]=list(map(int, input().strip().split(' ')))
    a.append(list(map(int, input().strip().split(' '))))

for  i in range(T):
    number = []#存储每个数字1的 个数
    # a.append(list(map(int, input().strip().split(' '))))
    for j in range(a[i][0],a[i][1]+1):
        tmp="{0:b}".format(j)#转为二进制
        # number[k]=sum(tmp)#空list 不能直接用index访问赋值,会out of range,用append 添加
        number.append(sum(tmp))#存储每个数字1的 个数
    res=number.index(max(number)) #list  中  1最多的下标
    # print('Case',i+1,':',a[i][0]+res)
    print("Case %d: %d" % (i+1, a[i][0]+res))

发表于 2019-09-24 19:04:20 回复(0)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
/**
您的代码已保存 运行超时:您的程序未能在规定时间内运行结束,
请检查是否循环有错或算法复杂度过大,case通过率为50.00% 
蛋疼。。。。*/
public class Main {
public static int maxNum = 0;
public static void main(String[] args) {

List<String> issueList = new ArrayList<String>();
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextLine()) {
issueList.add(scanner.nextLine());
}

for(int i=1; i<issueList.size(); i++) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
String parts[] = issueList.get(i).split(" ");
int min = Integer.parseInt(parts[0]);
int max = Integer.parseInt(parts[1]);
if(min > max) {
System.out.println("input error");
} else {

for(int j=min; j<=max; j++) {
int countx = fun(j);
if(countx > maxNum) {
maxNum = countx;
map.clear();
map.put(maxNum, j);
}
}

}
System.out.println("Case " + i + ": " + map.get(maxNum));
maxNum = 0;
}
}

private static int fun(int x) {

int countx = 0;
while(x > 0) {
countx ++;
x = x&(x-1);
}
return countx;
}
}
编辑于 2018-07-10 22:52:09 回复(0)