主页 / 问题 / 1538710
Accepted
Clark Devlin
Asked:2023-09-02 02:22:52 +0000 UTC2023-09-02 02:22:52 +0000 UTC

如何加快搜索算法的速度？

  • 772

有一个任务，我附上条件截图：

在此输入图像描述

我写了两个解决方案，似乎都可以正常工作，但是在数量较多时，程序需要很长时间才能执行，并且时间测试失败。

第一个选项：

def find_a_x(X):
    for i in range(X, 0, -1):
        if bin(i).count('1') == 3:
            return i
    return -1
 
 
T = int(input())
 
 
for _ in range(T):
    X = int(input())
    result = find_a_x(X)
    print(result)

带缓存的选项（不确定缓存是否正确实现）：

def find_a_x(X, cache):
    if X in cache:
        return cache[X]
 
    for i in range(X, 0, -1):
        binary_str = bin(i)[2:]
        if binary_str.count('1') == 3:
            cache[X] = i
            return i
 
    cache[X] = -1
    return -1


T = int(input())


for _ in range(T):
    X = int(input())
    result = find_a_x(X, {})
    print(result)

文本条件：

上课时，一名学生接管了黑板，开始写下一些奇怪的数字，结果发现这些数字根本不是随机的，爱丽丝注意到黑板上写的 2N 个数字是分成两对的，这样对于每个数字 X 都有一个数字 a (X)，使得 a(X) 等于不超过 X 的最大自然数，并且在其二进制表示法中恰好包含三个。如果不存在这样的数字，则 a(X) = -1。

输入数据格式。
第一行包含一个数字 T - 测试用例的数量，接下来的第 i 个 T 行包含由单个自然数给出的第 i 个测试。

输入数据示例：

4
1
8
1023
7

回答：

-1
7
896
7
python

3 个回答

  1. def cb(x):
    if x<7:
        return -1
    s=format(x,'b')
    if s.count('1')==3:
        return x
    if s.count('1')>3:
        b=1+s.find('1',1+s.find('1',1+s.find('1')))
        a=s[:b]
        for i in range(b,len(s)):
            a+='0'
        return int(a,2)
    if s.count('1')<3:
        return cb(x-1)


n=int(input())
res=[]
for _ in range(n):
    z = int(input())
    res.append(cb(z))
for y in res:
    print(y)

    4
1
8
1023
7

-1
7
896
7

    3
1000000000000
2000000000000
3000000000000
962072674304
1924145348608
2886218022912
    • 1

  2. 如果二进制表示的数字至少包含三个，那么我们只留下三个最高的：

    1010111010

    1010100000

    如果二进制表示的数字少于三个单位，则将其减 1：

    100亿

    0111111111

    如果减少结果的数字小于 7（即 110、101、100、11、10、1 或 0），则我们输出 -1，否则我们将结果数字再次传递给算法。

    • 0
  3. Best Answer

    我立即决定，只留下三个领导单位：

    def a(x):
    if x < 7:
        return -1
    bin_num = bin(x)[2:]
    if bin_num.count('1') > 3:
        return int(remove_el(bin_num), 2)
    elif bin_num.count('1') == 3:
        return x
    else:
        while x > 7:
            x -= 1
            bin_num = bin(x)[2:]
            if bin_num.count('1') > 3:
                return int(remove_el(bin_num), 2)
            elif bin_num.count('1') == 3:
                return x
        return 7


def remove_el(byte_string: str):
    one_c = 0
    iter_c = 0
    for s in byte_string:
        if one_c == 3:
            return byte_string[0:iter_c] + '0' * (len(byte_string) - iter_c)
        if s == '1':
            one_c += 1
        iter_c += 1


n = int(input())
for _ in range(n):
    print(a(int(input())))

    有人向我建议了一个更优雅的解决方案，但稍作改动：

    def a(x):
    r = 7 << 100
    while 6 < r > x:
        r >>= 1
    return r if r > 3 else -1


n = int(input())
for _ in range(n):
    print(a(int(input())))
    • 0

相关问题