首页 > 试题广场 >

光棍指数

[编程题]光棍指数
  • 热度指数:364 时间限制: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
function lonelyIndex(min, max) {
    let arr = [];
    for (; min <= max; min++) {
        arr.push(min.toString(2));
    }
    arr.sort(function (a, b) {
        if (a.replace(/0/g, '') < b.replace(/0/g, '')) {
            return 1;
        }
        return -1;
    });
    let temp = arr[0],
        i = 0;
    while (arr[i].replace(/0/g, '') === arr[i + 1].replace(/0/g, '')) {
        if (Number(arr[i]) > Number(arr[i + 1])) {
            temp = arr[i + 1];
        }
        i++;
    }
    return Number.parseInt(temp, 2);
}

发表于 2019-03-25 06:48:50 回复(0)
var count = parseInt(readline())
for(var i = 1; i <= count; i++) {
    var arr = readline().split(' ')
    arr[0] = + arr[0]
    arr[1] = + arr[1]
    var max = 0
    var res = 0
    var temp = 0
    for(var j = arr[0]; j <= arr[1]; j++) {
        var str = j.toString(2)
        temp = str.replace(/[^1]*/g, '').length
        if(temp > max) {
            res = j
            max = temp
        }
    }
    print("Case " + i + ": " + res)
}
算法复杂度过高o(╥﹏╥)o

发表于 2018-08-30 12:44:46 回复(0)
var n = parseInt(readline());
for(var i = 0;i < n; i++){
    var line = readline().split(' ');
    var a = parseInt(line[0]);
    var b = parseInt(line[1]);
    var result = a;
    while((result | (result + 1)) <= b){
        result |= result + 1;
    }
    print("Case " + (i+1) + ": " + result);
}

发表于 2018-08-03 19:23:33 回复(2)