我在各種在線網站上做一些 DS&A 問題以進行練習，我遇到了這個問題：
給定一個非負整數陣列，您可以從該陣列中選擇任何數字并交換其中的任意兩位數字。如果在交換操作后數字包含前導零，則可以將其省略并且不考慮。您的任務是檢查是否可以最多應用一次交換操作，以便結果陣列的元素嚴格遞增。
出于某種原因，這讓我一開始難住了，所以我去了健身房并考慮了一段時間。最終我回到它并再次嘗試，這次想出了一個解決方案。不幸的是，我得到的解決方案有點丑陋和笨拙，我覺得這不是解決這個問題的好方法。它適用于我嘗試過的測驗，但我真的很想為此找到更好的解決方案。我覺得我必須缺少一些可以改進它的基本東西。
所以我在這里發布我的代碼，希望得到一些反饋。
def solution(numbers):
swaps = 0
index = 0
for i in range(len(numbers)-1):
if numbers[i] >= numbers[i 1]:
swaps =1
index=i
if swaps > 1:
return False
elif not swaps:
return True
swappedI = swapToSmallest(numbers[index])
if (index-1 < 0 or numbers[index-1] < swappedI) and numbers[index 1] > swappedI:
return True
swappedIPlus1 = swapToSmallest(numbers[index])
if (index 1 > len(numbers) or numbers[index 1] < swappedIPlus1) and numbers[index-1] < swappedIPlus1:
return True
return False
def swapToSmallest(num) -> int:
num = str(num)
smallIndex = 0
smallestRight = num[smallIndex]
for i in range(1, len(num)):
if num[i] <= smallestRight:
smallestRight = num[i]
smallIndex = i
largeIndex = -1
largeLeft = num[largeIndex]
for i in range(len(num)-2, -1, -1):
if num[i] >= largeLeft:
largeLeft = num[i]
largeIndex = i
res = ""
for i, v in enumerate(num):
if i == largeIndex:
res =smallestRight
elif i == smallIndex:
res =largeLeft
else:
res =v
return int(res)
#tests
numbers = [1, 5, 10, 20]
print(solution(numbers))
numbers = [1, 3, 900, 10]
print(solution(numbers))
numbers = [1000, 10, 100]
print(solution(numbers))
numbers = [1, 2, 10, 7]
print(solution(numbers))
numbers = [1, 3, 3, 3]
print(solution(numbers))
numbers = [1000, 10, 9]
print(solution(numbers))
uj5u.com熱心網友回復：
肯定有遠沒有那么復雜的解決方案。例如，這是我想出的（只是試一試，我敢肯定還有更優化的解決方案）：
def flip(i):
return int(''.join(str(i)[::-1]))
def strict_inc(xs, single_flip_allowed=True):
for n, (a, b) in enumerate(zip(xs, xs[1:])):
if a >= b:
break
else:
return True
# here, n will be the index at which the first problem occurs
return single_flip_allowed and (
(
(n == 0 or xs[n-1] < flip(xs[n]))
and (n == len(xs) or flip(xs[n]) < xs[n 1])
and strict_inc(xs[n 1:], False)
)
or
(
(xs[n] < flip(xs[n 1]))
and (n 1 == len(xs) or flip(xs[n 1]) < xs[n 2])
and strict_inc(xs[n 2:], False)
)
)
（請注意，這實作了您的解決方案，增加了翻轉，但不是正確的，請繼續閱讀）
盡管該函式以遞回方式呼叫自身，但它不會多次呼叫，因此沒有問題。
它的基本原理是在原始正整數系列中只能有一個缺陷。因此，它找到第一個缺陷，查看是否可以通過“翻轉”缺陷中的第一個或第二個整數來修復它，并檢查在這種情況下序列的其余部分是否仍然嚴格增加（不允許進一步翻轉）。
您要求對您的代碼進行審查，但鑒于它顯然遠非最佳，這將是一項全面的作業。
如果您確實想要評論，我建議您嘗試https://codereview.stackexchange.com/，因為 StackOverflow 確實更適合尋求具體技術問題的解決方案。
事實證明（感謝@barmar 指出我的錯誤，并感謝@kellybundy 指出 OP 的錯誤）一個有效的解決方案也沒有那么復雜（同樣有改進的空間）：
def check(xs):
x = str(xs[1])
return any(xs[0] < int(f'{x[0:i]}{x[j]}{x[i 1:j]}{x[i]}{x[j 1:]}') < xs[2]
for i in range(len(x)) for j in range(i 1, len(x)))
def strict_inc(xs, single_flip_allowed=True):
for n, (a, b) in enumerate(zip(xs, xs[1:])):
if a >= b:
break
else:
return True
# here, n will be the index at which the first problem occurs
return single_flip_allowed and (
(
check(xs[n-1:n 2] if n > 0 else [-1] xs[n:n 2])
and strict_inc(xs[n 1:], False)
)
or
(
check(xs[n:n 3] if n < len(xs)-2 else xs[n:n 2] [int('9'*len(str(xs[n 1])))])
and strict_inc(xs[n 2:], False)
)
)
（另一個編輯：這個解決方案實際上會根據需要嘗試所有可能的配對）
uj5u.com熱心網友回復：
在閱讀了這里的一些輸入并進行了一些修改后，我想出了這個解決方案。與我最初的解決方案非常相似，但我認為它正在處理另一個沒有的情況。
def solution(numbers):
flaw = False
for i in range(len(numbers)-1):
if numbers[i] >= numbers[i 1]:
if flaw:
return False
else:
flaw = True
flawIndex = i
if not flaw:
return True
a = swap(numbers[flawIndex])
b = swap(numbers[flawIndex 1]) if flawIndex < len(numbers)-1 else None
return (
(
True if (flawIndex != 0 or a > numbers[flawIndex]) and a < numbers[flawIndex 1] else False
) or (
True if b < numbers[flawIndex] and (flawIndex < len(numbers)-1 or b < numbers[flawIndex 1]) else False
)
)
def swap(num):
sn = str(num)
l, r = max(sn), min(sn)
largeIndex = sn.index(l)
smallIndex = sn.rindex(r)
res = ""
for i in range(len(sn)):
if i==smallIndex:
res =sn[largeIndex]
elif i==largeIndex:
res =sn[smallIndex]
else:
res =sn[i]
return int(res)
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/377848.html
上一篇：使用二進制操作的反向解密演算法