嗨，我目前正在尝试解决以下问题：
假设您有一个随机的队列人员列表。每个人都由一对整数(h, k)描述，其中h是人的身高，k是这个人前面身高大于或等于h的人数。编写算法来重建队列。
注意： 人数不到1,100人。
例
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
这是我目前的解决方案：
answer = []
def reconstructQueue(people):
if len(answer) == len(people) and is_valid(answer):
return True
for person in people:
answer.append(person)
if is_valid(answer):
reconstructQueue([x for x in people if x != person])
else:
answer.pop()
def is_valid(answer):
answer = answer[::-1]
for i in range(len(answer)):
count = 0
for j in answer[i+1:]:
if answer[i][0] <= j[0]:
count+=1
if count != answer[i][1]:
return False
return True
我的is_valid函数正在工作，但recontructQueue中实现的回溯出错了！
以下是我认为它应该如何工作：
- 检查我们是否有包含所有原始列表值的有效答案，如果是，我们就完成了。
- 如果不是，则将其他人添加到列表中
answer并查看是否有效。 - 如果它是有效的，那么递归调用函数，删除我们刚刚添加的元素。
- 如果它无效，那么我们就犯了一个错误，所以我们通过从答案中弹出该元素来回溯。
不过，它并没有给我正确的答案。
有人可以帮助解释我哪里出错了，我不擅长回溯！
谢谢。
将全局answer作为递归内部工作的一部分并不是一个好主意。 我们将用默认的第二个参数替换它。
正如@MattTimmermans所指出的，你犯了递归初学者的错误，即递归函数返回一个有用的结果，但在递归调用它时忽略了该结果。 该递归调用将导致成功或失败，您需要采取相应的措施：
def reconstructQueue(people, todo=None):
if not todo and is_valid(people):
return people
if todo is None:
todo = people
people = []
tossed = []
while todo:
people.append(todo.pop())
if is_valid(people):
result = reconstructQueue(people, todo + tossed)
if result:
return result
tossed.append(people.pop())
return None # there is no solution from this starting point
def is_valid(answer):
for index, (my_height, my_count) in enumerate(answer):
their_count = sum(my_height <= their_height for their_height, _ in answer[:index])
if their_count != my_count:
return False
return True
scrambled = [(7, 0), (4, 4), (7, 1), (5, 0), (6, 1), (5, 2)]
print(reconstructQueue(scrambled))
我还将您的数据结构从列表列表切换到元组列表，因为这对我来说更有意义。
输出
> python3 test.py
[(5, 0), (7, 0), (5, 2), (6, 1), (4, 4), (7, 1)]
>