我正在尝试将这个solution适应Python的代码阻塞问题Dice Straight。不幸的是,它需要太深的递归才能在Python中正常工作(除非递归限制和堆栈大小都显著增加)。所以我试着把这个递归的method转换成迭代的:
/**
* Attempt to recursively free a die by selecting a different die for the same value.
* @return true if the die has been freed, false if no other die can be found.
*/
boolean freeByShuffling(Die die) {
assert die.valueUsing != null;
// First check if we can just use another dice for the previous value
for (Die otherDie : die.valueUsing.dice) {
if (otherDie.valueUsing == null) {
otherDie.valueUsing = die.valueUsing;
die.valueUsing = null;
return true;
}
}
// Nope, we must free a die recursively
diceVisitedWhileShuffling.add(die);
for (Die otherDie : die.valueUsing.dice) {
if (diceVisitedWhileShuffling.contains(otherDie)) continue;
if (freeByShuffling(otherDie)) {
otherDie.valueUsing = die.valueUsing;
die.valueUsing = null;
return true;
}
}
return false;
}
这是我的Python代码,虽然它解决了大多数测试用例,但并不十分有效:
def free_by_shuffling(self, die):
assert die.current_value is not None
stack = [(None, die)]
found = False
while stack:
this_die, other_die = stack.pop()
self.visited.add(other_die)
if found:
other_die.current_value = this_die.current_value
this_die.current_value = None
continue
for next_die in other_die.current_value.dice:
if next_die in self.visited:
continue
if next_die.current_value is None:
found = True
stack.append((other_die, next_die))
break
else:
for next_die in other_die.current_value.dice:
if next_die in self.visited:
continue
stack.append((other_die, next_die))
return found
如何将原始方法转换为使用迭代而不是递归?你知道吗
这个Python实现对“小”和“大”输入文件都适用:
欢迎提出意见和建议。你知道吗
相关问题 更多 >
编程相关推荐