代码之家 › 专栏 › 技术社区 › Eugene Yarmash

如何将这种递归Java方法转换为迭代方法?(CodeJam挑战)

iteration recursion python-3.x python java

Eugene Yarmash · 技术社区 · 7 年前

我正在努力适应这个 solution 到代码阻塞 Dice Straight Python的问题。不幸的是,它需要太深的递归才能在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

如何将原始方法转换为使用迭代而不是递归?

1 回复 | 直到 7 年前

Eugene Yarmash 7 年前

这种Python实现对于“小”和“大”输入文件都很有效:

def free_by_shuffling(self, die):
    assert die.current_value is not None

    stack = [die]
    found = False

    while stack:
        this_die = stack.pop()

        if found:
            if stack:
                this_die.current_value = stack[-1].current_value
                stack[-1].current_value = None
            continue

        for other_die in this_die.current_value.dice:
            if other_die.current_value is None:
                stack.extend((this_die, other_die))
                found = True
                break
        else:
            self.visited.add(this_die)

            for other_die in this_die.current_value.dice:
                if other_die not in self.visited:
                    stack.extend((this_die, other_die))
                    break
            else:
                if stack:
                    for other_die in stack[-1].current_value.dice:
                        if other_die not in self.visited:
                            stack.append(other_die)
                            break
    return found

欢迎提出任何意见和建议。