我正在嘗試解決以下問題：
給定一個長度為 1-9 個元素的陣列，由數字
0-組成9，使用陣列中的一些/所有元素可以形成的可被 3 整除的最大數是多少？
這個問題只接受Java和Python，盡管完全沒有經驗，我還是選擇了Python。
我環顧四周，似乎總體思路是啟動最小元素以使數字總能被 3 整除，并撰寫了以下“減法”方法：
def maxdiv3(l):
l.sort()
tot = 0
for i in l:
tot = i
if tot % 3 == 0:
l.sort(reverse=True)
return int(''.join(str(e) for e in l))
elif tot % 3 == 1:
cl = [] # A copy of the list but only for elements % 3 != 0
acl = [] # Anti copy of the list, only for elements % 3 = 0
for i in l:
if i % 3 == 0:
acl.append(i)
else:
cl.append(i)
removed = False
nl = [] # A new list for the final results
for i in cl:
if not removed:
if i % 3 == 1:
removed = True
else:
nl.append(i)
else:
nl.append(i)
if removed:
nl.extend(acl)
nl.sort(reverse=True)
if len(nl) > 0:
return int(''.join(str(e) for e in nl))
else:
return 0
else:
if len(acl) > 0:
acl.sort(reverse=True)
return int(''.join(str(e) for e in acl))
return 0
elif tot % 3 == 2:
cl = []
acl = []
for i in l:
if i % 3 == 0:
acl.append(i)
else:
cl.append(i)
removed2 = False
nl = []
for i in cl:
if not removed2:
if i % 3 == 2:
removed2 = True
else:
nl.append(i)
else:
nl.append(i)
if removed2:
nl.extend(acl)
nl.sort(reverse=True)
if len(nl) > 0:
return int(''.join(str(e) for e in nl))
removed1 = 0
nl = []
for i in cl:
if removed1 < 2:
if i % 3 == 1:
removed1 = 1
else:
nl.append(i)
else:
nl.append(i)
if removed1 == 2:
nl.extend(acl)
nl.sort(reverse=True)
if len(nl) > 0:
return int(''.join(str(e) for e in nl))
if len(acl) > 0:
acl.sort(reverse=True)
return int(''.join(str(e) for e in acl))
else:
return 0
這種方法一直停留在隱藏的測驗用例上，這意味著我無法弄清楚是什么或為什么。
基于此，我寫了一個新的：
def maxdiv3(l):
l.sort()
l0 = []
l1 = []
l2 = []
for i in l:
if i % 3 == 0:
l0.append(i)
elif i % 3 == 1:
l1.append(i)
elif i % 3 == 2:
l2.append(i)
tot = sum(l)
nl = []
if tot % 3 == 0:
nl = l
nl.sort(reverse=True)
if len(nl) > 0:
return int(''.join(str(e) for e in nl))
return 0
elif tot % 3 == 1:
if len(l1) > 0:
l1.remove(l1[0])
nl.extend(l0)
nl.extend(l1)
nl.extend(l2)
nl.sort(reverse=True)
if len(nl) > 0:
return int(''.join(str(e) for e in nl))
return 0
elif len(l2) > 1:
l2.remove(l2[0])
l2.remove(l2[0])
nl.extend(l0)
nl.extend(l1)
nl.extend(l2)
nl.sort(reverse=True)
if len(nl) > 0:
return int(''.join(str(e) for e in nl))
return 0
else:
return 0
elif tot % 3 == 2:
if len(l2) > 0:
l2.remove(l2[0])
nl.extend(l0)
nl.extend(l1)
nl.extend(l2)
nl.sort(reverse=True)
if len(nl) > 0:
return int(''.join(str(e) for e in nl))
return 0
elif len(l1) > 1:
l1.remove(l1[0])
l1.remove(l1[0])
nl.extend(l0)
nl.extend(l1)
nl.extend(l2)
nl.sort(reverse=True)
if len(nl) > 0:
return int(''.join(str(e) for e in nl))
return 0
else:
return 0
而這個確實通過了所有的測驗用例，包括隱藏的測驗用例。
Here are some of the test cases that I ran my attempt through:
[3, 9, 5, 2] -> 93
[1, 5, 0, 6, 3, 5, 6] -> 665310
[5, 2] -> 0
[1] -> 0
[2] -> 0
[1, 1] -> 0
[9, 5, 5] -> 9
It seems to me that my attempt and the SO solution had the same idea in mind, so what did I neglect to consider? How is the SO solution different from mine and how does that catch whatever it is that my attempt didn't?
Thank you for your time.
A slightly off topic additional question: How do I find edge cases when dealing with blind test cases? I built a random input generator for this question but that didn't help anywhere near I wished it would and is likely not a good general solution.
uj5u.com熱心網友回復：
在處理盲測用例時如何找到邊緣用例？
這是我作為測驗人員所做的：
digits = list(range(10))
for k in range(1, 10): # Try different sizes
for _ in range(100): # Repeat many times
lst = random.choices(digits, k=k) # Produce random digits
a = maxdiv3(lst) # Run working solution
b = maxdiv3b(lst) # Run solution with a problem
if a != b: # Found a deviation!
print(lst)
break
這是我得到的清單之一：
[2, 2, 5, 5, 8]
然后我用那個輸入追溯了你的代碼并進入了這個塊：
else:
if len(acl) > 0:
acl.sort(reverse=True)
return int(''.join(str(e) for e in acl))
我們在這里的情況是，當總數除以 3 時余數為 1。當else沒有單個數字具有這樣的余數時，我們進入這個塊。然后它只輸出所有 3 的倍數的數字。但這并不總是正確的。當至少有兩位數的余數為 2（即 2、5、8）時，這樣的對表示余數為 1 的總數，即您只需洗掉兩位數，而不是更多。
更正方法是洗掉其中兩個數字（最小的），然后像在代碼中其他地方所做的那樣加入兩個串列：
else:
del nl[0:2]
nl.extend(acl)
nl.sort(reverse=True)
if len(nl) > 0:
return int(''.join(str(e) for e in nl))
else:
return 0
注意：選擇的名稱不是很有描述性，這并沒有幫助。我不知道acl, nl, orcl是什么的縮寫。
uj5u.com熱心網友回復：
您可以使用遞回來“改進”數字選擇，一旦數字總和是 3 的倍數就停止（所有可被 3 整除的數字總和都是 3 的倍數）。只有去除不是 3 的倍數的數字才能改善結果
最大的數字是數字按降序排列的數字。
def div3(D):
if sum(D)%3 == 0:
return sum(d*10**i for i,d in enumerate(sorted(D)))
return max(div3(D[:i] D[i 1:]) for i,d in enumerate(D) if d%3)
d = [1,2,3,4,5]
print(div3(d))
# 54321
d = [2, 2, 5, 5, 8]
print(div3(d))
# 855
print(div3([4,1]))
# 0
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417245.html
標籤：
上一篇：在Javascript中計算二維陣列中元素之間的距離
下一篇：生成概率為p的隨機圖