我有一个问题，我几乎解决了它，但我面临着一个测试用例的问题，给定一个数字数组，允许选择任意数字并交换数字，使数组变为严格递增，例如:[2,4,800,12]，我们可以选择800并将其转换为008，然后数组变为[2,4,008,12]，因此它应该返回true，并且允许它一次，所以任务是检查是否有可能将数组转换为严格递增最多一次交换，这是我的代码
def solution(numbers):
swapped = 0
for i in range(len(numbers)-1):
if numbers[i] > numbers[i+1]:
if swapped >= 1:
return False
s1= int(''.join(sorted(str(numbers[i]))))
if s1 < numbers[i+1]:
if i > 0 and s1 >= numbers[i-1]:
numbers[i] = s1
swapped += 1
continue
s2 = int(''.join(sorted(str(numbers[i+1]), reverse=True)))
if s2 >= numbers[i]:
numbers[i+1] = s2
swapped += 1
continue
return True
代码没有通过的唯一测试用例是[13,31,30](返回True而不是False)，我不知道如何解决这个问题。
(我为我的问题中任何不优雅的部分道歉，我是新来的，我正在努力)
你的逻辑基本上是正确的，除了我会在循环结束时检查交换，我会检查所有的排列，而不仅仅是由数字创建的最小和最大整数。
from itertools import permutations, pairwise
def soln(numbers):
swapped = 0
for i in range(len(numbers)):
perms = list(int(''.join(shuffled_digits)) for shuffled_digits in permutations(str(numbers[i])))
if i == 0:
candidate_nums = [shuffled_number for shuffled_number in perms if shuffled_number < numbers[i+1]]
elif i < len(numbers) - 1:
candidate_nums = [shuffled_number for shuffled_number in perms if numbers[i-1] < shuffled_number < numbers[i+1]]
else:
candidate_nums = [shuffled_number for shuffled_number in perms if shuffled_number > numbers[i-1]]
if candidate_nums:
swapped_num = candidate_nums.pop()
numbers[i] = swapped_num
swapped +=1
if all(x < y for x, y in pairwise(numbers)):
return True
return False
In [80]: inlist
Out[80]: [2, 4, 8, 12]
In [81]: soln(inlist)
Out[81]: True
In [82]: inlist = [2, 4, 800, 12]
In [83]: soln(inlist)
Out[83]: True
In [84]: inlist = [21, 21]
In [85]: soln(inlist)
Out[85]: True
In [86]: inlist = [2, 1, 9, 7]
In [87]: soln(inlist)
Out[87]: False
In [88]: inlist = [2, 1, 1]
In [89]: soln(inlist)
Out[89]: False
In [90]: inlist = [100, 2, 3]
In [91]: soln(inlist)
Out[91]: True
In [92]: inlist = [52, 53, 36]
In [93]: soln(inlist)
Out[93]: True
In [94]: inlist = [44,37,74]
In [95]: soln(inlist)
Out[95]: True
当您有一个需要更改的候选数字时，我建议在排列(虚拟)列表中进行定向搜索，以找到值尽可能接近您比较的值的排列，以便恢复严格升序。
没有必要为此生成所有的排列，当输入数字中的位数超过10时，这会消耗太多的时间和空间。
这个想法是计算每个数字的位数，在需要排列的数字中，然后以尽可能接近目标值的方式取下一个数字进行排列。需要进行一些回溯，但对于每个数字位置，最多需要两次尝试:一次是针对与目标数字(要比较的值)完全匹配的数字，可能是针对另一个数字的第二次尝试。
这是这个想法的一个实现。
第一个辅助函数查找给定值的排列，该排列尽可能接近目标值(但不等于目标值)，并且必须小于或大于(最后一个参数控制此):
def permute_near(value, target, side=1):
# If side is 1, we will look for the minimum permutation of value that is
# greater than the target.
# If side is -1, we will look for the maximum permutation of value that is
# less than the target.
freedigit = 0 if side == 1 else 9
end = freedigit + 10*side
target += side
# Get a count for each digit of value (could also use Counter module for this)
s = str(value)
n = len(s)
digits = [0]*10
for digit in s:
digits[int(digit)] += 1
# Pad the target value to have the same number of digits
limit = [int(digit) for digit in str(target).rjust(n, "0")]
# Use recursion to find the permutation of value that is nearest to the target
def recur(k, isfree, accumulator):
if k >= n: # All digits were processed, we have the result
return accumulator
limitdigit = limit[k]
for i in range(freedigit if isfree else limitdigit, end, side):
if digits[i]:
digits[i] -= 1 # Select this digit for the permutation
permutation = recur(k + 1, isfree or i != limitdigit, accumulator * 10 + i)
digits[i] += 1 # Backtrack
if permutation > -1 or i != limitdigit:
return permutation
# If it failed for the case where the chosen digit was the same
# as in the target, try with one alternative digit in a
# second and also last iteration of this loop.
return -1
return recur(0, False, 0)
下面是主要函数:
def solution(numbers):
try:
# Find the first index where the next value is not greater
i = next(i for i, val in enumerate(numbers) if val >= numbers[i+1])
except:
return numbers # The input is already completely ascending
# Permute numbers[i], so it becomes less than its successor
result = permute_near(numbers[i], numbers[i+1], -1)
# Check that such permutation exists, and is still greater than its predecessor
if result >= 0 and (i == 0 or numbers[i - 1] < result):
numbers[i] = result # OK, we have success
else:
# ... or permute numbers[i+1], so it becomes greater than its predecessor
result = permute_near(numbers[i+1], numbers[i], 1)
# Check that such permutation exists, and is still less than its successor
if result >= 0 and (i + 2 >= len(numbers) or result < numbers[i + 2]):
numbers[i + 1] = result # OK, we have success
if all(a < b for a, b in zip(numbers, numbers[1:])):
return numbers
一些运行:
# A few test cases
print(solution([2,4,800,12])) # [2, 4, 8, 12]
print(solution([44,37,74])) # [44, 73, 74]
print(solution([52,53,36])) # [52, 53, 63]
print(solution([64,52,53])) # [46, 52, 53]
print(solution([89221173000,89221173456,13437127829,89221173477]))
# [89221173000, 89221173456, 89221173473, 89221173477]
如果有解决方案，则返回调整后的列表，否则返回None。
问题中提到的代码在这个测试用例中也失败了:[52,31,30]
如果只交换一个数字，至少有一个递增数组/列表，则返回True。
def solution(numbers):
# Converts to str
numbers = [str(i) for i in numbers]
n = len(numbers)
for j in range(n + 1):
if j != n:
# Reverse number
numbers[j] = str(numbers[j])[::-1]
# Checks if the array is in increasing order
if all([int(numbers[i + 1]) > int(numbers[i]) for i in range(n - 1)]):
return True
if j != n:
numbers[j] = str(numbers[j])[::-1]
return False