光棍指数

[编程题]光棍指数

热度指数：119 时间限制：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

算法知识视频讲解

Python

201807221218349

# coding=utf-8
def count_one(x):
    """统计十进制数x的二进制表示的1的个数"""
    x_bi_str = bin(x)
    n = 0
    for c in x_bi_str[2:]:
        if c == "1":
            n += 1
    return n, len(x_bi_str) - 2

def all_ones(x):
    """判断某数的二进制是否全为1"""
    n_one, n_all = count_one(x)
    return n_one == n_all

def ones2int(n_bits):
    """获取具有 n_bits 个 1 的十进制数，eg. 1111 -> 15"""
    bi_str = "1"*n_bits
    return int(bi_str , 2)

def voil_search(a, b):
    """暴力搜索"""
    most_lonely = a
    measure_lonely, _ = count_one(a)
    for x in range(a+1, b+1):
        meas, _ = count_one(x)
        if meas > measure_lonely:
            measure_lonely = meas
            most_lonely = x
    return most_lonely, measure_lonely
            
            
def search(a, b):
    """各种情况汇总"""
    # 第一种情况: 相等
    if a == b:
        return a
    
    # 第二种情况: b 全是1，当然他最多
    if all_ones(b):
        return b
    
    # 第三种情况: 构造比b 低一位的全1二进制数 b1
    n_one_b, n_all_b = count_one(b)
    b1 = ones2int(n_all_b - 1)
    #    如果 a <= b1， 那最多1就只能有这么多个
    if a <= b1:
        return b1
    
    #    最后，暴力搜索吧，这时候 a和b是一个数量级的
    # 但是，暴力搜索复杂度不能满足要求
    
    # 递归搜索：寻找  a = 101000 与 b = 101101 的光棍数
    #        等价于  a =   1000 与 b =   1101 的光棍数
    minus_val = 0
    a_bi_str, b_bi_str = bin(a)[2:], bin(b)[2:]
    n_bits = len(a_bi_str)
    i = 0
    while a_bi_str[i] == b_bi_str[i]:
        if a_bi_str[i] == "1":
            minus_val += int(2**(n_bits - 1 - i))
        i += 1
    most_lonely = search(a - minus_val, b - minus_val)
    return most_lonely + minus_val

#===============================================================
if __name__ == "__main__":
    T = int(input())
    for i in range(T):
        # 每行输入
        num_str = input().strip().split(" ")
        a, b = int(num_str[0]), int(num_str[1])
        most_lonely = search(a, b)
        print("Case {}: {}".format(i+1, most_lonely))

发表于 2018-07-22 22:04:05 回复(0)

Hisun100

#生成器
def decimalToBinary(item):
    while item:
        if item < 1:
            modeValue = int(item)
            break
        else:modeValue = int(item % 2)
        yield modeValue
        item = int(item / 2)
a=0
b=15
valueSum_max = 0
# 遍历区间[a,b]内的所有整数item
for item in range(a,b+1):
    valueSum = 0
    for value in decimalToBinary(item):
        valueSum +=value
    if valueSum >= valueSum_max:
        valueSum_max = valueSum
        guanggun = item
print(guanggun)

发表于 2018-07-21 22:39:11 回复(0)