我已經完成了一項編碼游戲評估，但我無法通過關于幸運數字的一項挑戰的所有測試。我需要協助。定義：幸運數字是一個數字中包含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有人可以幫我優化我的代碼嗎？
3 回答
PIPIONE
TA貢獻1829條經驗 獲得超9個贊
這是一個有趣的問題，@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)
滄海一幻覺
TA貢獻1824條經驗 獲得超5個贊
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))
天涯盡頭無女友
TA貢獻1831條經驗 獲得超9個贊
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)
添加回答
舉報
0/150
提交
取消