我正在做一些DS&一个问题在各种网站上在线练习，我遇到了这个：
给定一个非负整数数组，您可以从该数组中选择任何数字，并交换其中的任何两位数字。如果交换操作后该数字包含前导零，则可以忽略这些数字，而不考虑它们。您的任务是检查是否可以最多应用一次交换操作，以便生成的数组的元素严格增加。
出于某种原因，这让我一开始很困惑，所以我去健身房想了一会儿。最终，我又回来尝试了一次，这次想出了一个解决方案。不幸的是，我得到的解决方案有点可怕和笨拙，我觉得这不是解决这个问题的好方法。它适用于我尝试过的测试，但我真的想找到一个更好的解决方案。我觉得我一定错过了一些基本的东西来改善它
所以我在这里发布我的代码，希望得到一些反馈
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))
肯定有远没有那么复杂的解决方案。例如，这是我想出的一个(只是尝试一下，我相信还有更优化的解决方案(：
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)
)
)
(另一个编辑：这个解决方案实际上根据需要尝试了所有可能的配对(
在阅读了这里的一些输入并进行了一些修改后，我提出了这个解决方案。与我最初的解决方案非常相似，但我认为它是在处理其他案例。
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)
我刚刚开始学习Scala，因此，任何关于最佳实践的建议都是非常受欢迎的。
def solution(numbers: Array[Int]) = {
val swappedNumbers = numbers.map(listOfPermutation(_))
val res = Array.fill(swappedNumbers.length)(-1)
for {
i <- 0 to res.length - 1
} yield if (i == 0) res(i) = swappedNumbers(i)(i)
else {
res(i) = getNextNum(res(i - 1), swappedNumbers(i))
}
if (res.filter(_ == -1).size == 0) true else false
}
def getListOfDigits(int: Int) = {
def getDigits(int: Int, acc: List[Int]): List[Int] = {
if (int % 10 == 0 & int / 10 == 0) acc
else {
getDigits(int / 10, int % 10 :: acc)
}
}
if (int > 0) getDigits(int, Nil) else int :: Nil
}
def listOfPermutation(int: Int): Array[Int] = {
val arrOfDigits = getListOfDigits(int).toArray
if (arrOfDigits.length <= 1) arrOfDigits
else {
val res = for {
i <- (0 to arrOfDigits.length - 2).toArray
j <- i + 1 to arrOfDigits.length - 1
} yield {
val swapped = (arrOfDigits(i), arrOfDigits(j)).swap
val copyOfDig = arrOfDigits.clone()
copyOfDig(i) = swapped._1
copyOfDig(j) = swapped._2
copyOfDig.mkString.toInt
}
res
.filter(num => num <= int)
.sortWith(_ < _) :+ arrOfDigits.mkString.toInt
}
}
def getNextNum(num: Int, arrOfNum: Array[Int]): Int = {
val res = arrOfNum.filter(_ > num)
if (res.length > 0) res(0) else -1
}
println(solution(Array(13, 31, 30))) //false
println(solution(Array(1, 5, 10, 20))) //true
println(solution(Array(1, 3, 900, 10))) //true
println(solution(Array(1000, 500, 400, 300))) //true
我就是这样做的。我希望能帮助你。我使用了我发现的一些函数。我是新来的：(
def flip(i):
flipper = int(''.join(str(i)[::-1]))
if i == flipper:
ans = False
else:
ans = True
return (flipper, ans)
def is_asacending(lstt):
res = all(i<j for i,j in zip(lstt, lstt[1:]))
return res
def solution(lstt):
if is_asacending(lstt)==True:
return True
else:
NewList = []
ans = []
for i in lstt:
CopyList = lstt.copy()
y = lstt.index(i)
CopyList[y] = flip(i)[0]
NewList.append(CopyList)
if is_asacending(CopyList):
ans.append(True)
else:
ans.append(False)
if True in ans:
return True
else:
return False
#check with this
print(solution([1,5,10,20]))
print(solution([1,3,900,10]))
print(solution([13,31,30]))
print(solution([222,214,333]))