如何统计L和H之间包含的幸运数字的个数？

Question

我已经完成了一项编码游戏评估，但我无法通过关于幸运数字的一项挑战的所有测试。我需要协助。定义：幸运数字是一个数字中包含6s 或8s 但不能同时包含两者的数字。例如16, 38,666是幸运数字。234，687不是。任务L：打印和之间的幸运数字数H。约束：L < H记忆：512MB时间：6 seconds这是我所做的（我选择 Python 作为编程语言）def is_lucky(nbr):    nbr = [*str(nbr)]    if '6' in nbr and '8' in nbr:        return False    if '6' in nbr or '8' in nbr:        return True    return Falsen_lucky_number = 0for number in range(L, H + 1):    n_lucky_number += is_lucky(number)print(n_lucky_number)L由于超时，我在和H很大（或两者之间的差距）的测试中失败了。L, H = 1, 1000000000000000000L, H = 92871036442, 3363728910382456有人可以帮我优化我的代码吗？

Answer 1

这是一个有趣的问题，@sulav shrestha 已经提供了一个有效的算法。不幸的是，他的回答缺乏一些解释，代码本身可以更清晰。

正如其他人指出的那样，您必须想出一个公式才能执行大数字。

@user3386109 正确地指出lucky(L,H) = lucky(0,H) - lucky(0,L-1). 从那里让我们看看在 0 和任何给定数字之间有多少幸运数字。
在十进制中，任何数字都可以写成十的幂之和：

12345 = 1e4 + 2e3 + 3e2 + 4e1 + 5e0

那么让我们计算 0 到 之间的幸运数字的数量10^n。它归结为计算 n 位数字的可能组合：

• 没有8，至少有一个6

• 没有6，至少有一个8

没有的组合数8是9^n（您可以为 n 位数字中的每一个选择 9 种可能性）。然后删除所有不包含任何6:的组合8^n。

所以 0 到 之间的幸运数字的个数10^n是2*(9^n-8^n)。

从那里你可以从左到右遍历你的数字并计数：

import time

def magic_numbers_until(num):

    num_str=str(num)

    str_len=len(num_str)

    c=[]

    count=0

    for i,digit in enumerate(num_str):          # we're going from left to right in num

        power_ten=str_len-i-1

        for k in range(int(digit)):             # summing all magic numbers for this power of ten

            if (k==6 or k==8                    # if 6 (resp. 8) was already seen,

                or "6" in c or "8" in c):       # you just calculate the combinations without 8 (resp. 6)

                count=count+9**power_ten 

            else:                               # the case described in my answer

                count=count+2*(9**power_ten-8**power_ten)

        

        c.append(digit)        

        if "6" in c and "8" in c:               # if 6 and 8 are in num, all remaining combinations will be non-magic

            break

    return(int(count))

    

L=1

H=1000000000000000000

t0 = time.time()  

print(magic_numbers_until(H+1)-magic_numbers_until(L))

print(time.time()-t0)

Answer 2

def coo(a):

    b=str(a)

    l=len(b)

    c=[]

    count=0

    for i,j in enumerate(b):

        d=l-i-1

        for k in range(int(j)):

            if k==6 or k==8:

                if k==6 and "8" not in c:

                    count=count+9**d

                elif k==8 and "6" not in c:

                    count=count+9**d    

            elif "6" not in c and "8" not in c:

                count=count+2*((9**d)-(8**d))

            elif "6" in c or "8" in c:

                count=count+9**d 

        

        c.append(j)        

        if "6" in c and "8" in c:

            break

    return(int(count))

L=21345323634

H=8392440035734    

print(coo(H+1)-coo(L))

Answer 3

6秒？这在 Python 中似乎真的很难，与 C、Java 等相比通常很慢。尽管我还没有找到通过测试的方法，但有几个地方可以改进：

1. is_lucky

nbr可以直接转换成str，不需要解压成list. str支持in。使用在数学计算中的事实，True==1，False==0。

例如 A is '6' in nbr, B is '8' in nbr:

两者都为真，A+B=2

一个为真，A+B=1

两者都为假，A+B=0

所以我们可以检查是否A+B == 1。

前：

def is_lucky(nbr):

    nbr = [*str(nbr)]

    if '6' in nbr and '8' in nbr:

        return False

    if '6' in nbr or '8' in nbr:

        return True

    return False

后：

def is_lucky(nbr):

    nbr = str(nbr)

    return ('6' in nbr) + ('8' in nbr) == 1

2.循环

如果现在已经检查了数字False，我们可以改进它。

如果最后一位小于 5，递增 6-n%10。

例如，311不是幸运数字。所以当然 312~315 也不是，所以只需通过6-1=5直接添加到316。 为什么不<6？5 加 1 无论如何，所以我们不需要它:]

前：

n_lucky_number = 0

for number in range(L, H + 1):

    n_lucky_number += is_lucky(number)

print(n_lucky_number)

后：

number, s = L, 0

while n <= H:

    x = is_lucky(number)

    n_lucky_number += x

    m = number % 10

    if not x and m < 5:

        number += 6-m

    else:

        number += 1

print(n_lucky_number)