猿问

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

我已经完成了一项编码游戏评估，但我无法通过关于幸运数字的一项挑战的所有测试。我需要协助。

定义：幸运数字是一个数字中包含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 False


n_lucky_number = 0

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

    n_lucky_number += is_lucky(number)

print(n_lucky_number)

L由于超时，我在和H很大（或两者之间的差距）的测试中失败了。

L, H = 1, 1000000000000000000

L, H = 92871036442, 3363728910382456

有人可以帮我优化我的代码吗？


拉莫斯之舞
浏览 125回答 3
3回答

PIPIONE

这是一个有趣的问题，@sulav shrestha 已经提供了一个有效的算法。不幸的是，他的回答缺乏一些解释，代码本身可以更清晰。正如其他人指出的那样，您必须想出一个公式才能执行大数字。@user3386109 正确地指出lucky(L,H) = lucky(0,H) - lucky(0,L-1).&nbsp;从那里让我们看看在 0 和任何给定数字之间有多少幸运数字。在十进制中，任何数字都可以写成十的幂之和：12345&nbsp;=&nbsp;1e4&nbsp;+&nbsp;2e3&nbsp;+&nbsp;3e2&nbsp;+&nbsp;4e1&nbsp;+&nbsp;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 timedef magic_numbers_until(num):&nbsp; &nbsp; num_str=str(num)&nbsp; &nbsp; str_len=len(num_str)&nbsp; &nbsp; c=[]&nbsp; &nbsp; count=0&nbsp; &nbsp; for i,digit in enumerate(num_str):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # we're going from left to right in num&nbsp; &nbsp; &nbsp; &nbsp; power_ten=str_len-i-1&nbsp; &nbsp; &nbsp; &nbsp; for k in range(int(digit)):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# summing all magic numbers for this power of ten&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (k==6 or k==8&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # if 6 (resp. 8) was already seen,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; or "6" in c or "8" in c):&nbsp; &nbsp; &nbsp; &nbsp;# you just calculate the combinations without 8 (resp. 6)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count=count+9**power_ten&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# the case described in my answer&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count=count+2*(9**power_ten-8**power_ten)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; c.append(digit)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if "6" in c and "8" in c:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# if 6 and 8 are in num, all remaining combinations will be non-magic&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; return(int(count))&nbsp; &nbsp;&nbsp;L=1H=1000000000000000000t0 = time.time()&nbsp;&nbsp;print(magic_numbers_until(H+1)-magic_numbers_until(L))print(time.time()-t0)
0

沧海一幻觉

def coo(a):&nbsp; &nbsp; b=str(a)&nbsp; &nbsp; l=len(b)&nbsp; &nbsp; c=[]&nbsp; &nbsp; count=0&nbsp; &nbsp; for i,j in enumerate(b):&nbsp; &nbsp; &nbsp; &nbsp; d=l-i-1&nbsp; &nbsp; &nbsp; &nbsp; for k in range(int(j)):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if k==6 or k==8:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if k==6 and "8" not in c:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count=count+9**d&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; elif k==8 and "6" not in c:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count=count+9**d&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; elif "6" not in c and "8" not in c:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count=count+2*((9**d)-(8**d))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; elif "6" in c or "8" in c:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count=count+9**d&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; c.append(j)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if "6" in c and "8" in c:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; return(int(count))L=21345323634H=8392440035734&nbsp; &nbsp;&nbsp;print(coo(H+1)-coo(L))
0

天涯尽头无女友

6秒？这在 Python 中似乎真的很难，与 C、Java 等相比通常很慢。尽管我还没有找到通过测试的方法，但有几个地方可以改进：1. is_luckynbr可以直接转换成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):&nbsp; &nbsp; nbr = [*str(nbr)]&nbsp; &nbsp; if '6' in nbr and '8' in nbr:&nbsp; &nbsp; &nbsp; &nbsp; return False&nbsp; &nbsp; if '6' in nbr or '8' in nbr:&nbsp; &nbsp; &nbsp; &nbsp; return True&nbsp; &nbsp; return False后：def is_lucky(nbr):&nbsp; &nbsp; nbr = str(nbr)&nbsp; &nbsp; return ('6' in nbr) + ('8' in nbr) == 12.循环如果现在已经检查了数字False，我们可以改进它。如果最后一位小于 5，递增 6-n%10。例如，311不是幸运数字。所以当然 312~315 也不是，所以只需通过6-1=5直接添加到316。 为什么不<6？5 加 1 无论如何，所以我们不需要它:]前：n_lucky_number = 0for number in range(L, H + 1):&nbsp; &nbsp; n_lucky_number += is_lucky(number)print(n_lucky_number)后：number, s = L, 0while n <= H:&nbsp; &nbsp; x = is_lucky(number)&nbsp; &nbsp; n_lucky_number += x&nbsp; &nbsp; m = number % 10&nbsp; &nbsp; if not x and m < 5:&nbsp; &nbsp; &nbsp; &nbsp; number += 6-m&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; number += 1print(n_lucky_number)
0
随时随地看视频慕课网APP

相关分类

Python
我要回答