开锁 - LeetCode，为什么计数器在每次递归调用中都在递增？

Question

我正在应对 LeetCode 上的 Open the lock 挑战：

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1
Input: deadends = ["0201","0101","0102","1212","2002"], 
       target = "0202"
Output: 6

这是我的尝试：

var openLock = function(deadends, target) {
    let res = 0;
    let seen = []
    let recursion = function(temp,counter=0){
        if(deadends.includes(temp) || seen.includes(temp)) return
        seen.push(temp)
        if(temp ===target){
            res = counter
            return
        }
        for(let i=0; i<temp.length; i++){
            let s1 = temp.substring(0, i) + (+temp[i]+1)%10 + temp.substring(i + 1)
            let s2 = temp.substring(0, i) + (+temp[i]+9)%10 + temp.substring(i + 1)
            recursion(s1,counter+1)
            erecursion(s2,counter+1)
        }
    }
    recursion('0000')
    return res ?? -1;
};

我这里例子的输出是2230，我不明白为什么。就好像 counter 变量值在每次递归调用中都得到更新。

Answer 1

发生这种情况是因为您的代码将每个访问过的组合标记为“已看到”，但没有确保您通过最短路径到达该组合，因此您的代码永远不会尝试用更短的路径达到相同的组合。

对于示例输入，您的代码将按以下顺序访问组合：

...所有这一切都发生了 没有回溯 ！由于你的 for 循环总是会找到一些尚未访问过的可能性，递归只会加深，加深。

...最终它会达到目标组合，但要通过很长很深的递归路径。然后该组合被标记为可见，因此您的代码永远不会考虑可能导致相同解决方案的较短路径。

深度优先与广度优先

虽然您可以使用深度优先搜索来解决这个问题，但使用广度优先搜索更容易解决这个问题，因为它更适合寻找最短路径。使用深度优先搜索，您应该只将 current 路径上的组合标记为“已看到”。所以当递归回溯时，那些更深的节点应该被取消标记。

这是广度优先的解决方案：

var openLock = function(deadends, target) {
    if (target == "0000") return 0; // boundary case
    let seen = new Set(deadends);
    if (seen.has("0000")) return -1; // boundary case
    let frontier = ["0000"];
    let res = 1;
    while (frontier.length) {
        let nextFrontier = [];
        for (let combi of frontier) {
            for (let dial = 0; dial < 4; dial++) {
                for (let add = 1; add < 10; add += 8) {
                    let neighbor = combi.slice(0, dial) + 
                                   (+combi[dial] + add) % 10 +
                                   combi.slice(dial+1);
                    if (!seen.has(neighbor)) {
                        if (neighbor == target) return res;
                        nextFrontier.push(neighbor);
                        seen.add(neighbor);
                    }
                }
            }
        }
        frontier = nextFrontier;
        res++;
    }
    return -1;    
};

这个解决方案可以进一步优化。例如，add 值现在始终是 first 1，然后是 then 9，但是先尝试 9 可能会有好处，当它“更接近”该刻度盘上的目标数字时。这将避免在另一个方向上进行搜索的所有工作，因为在这种情况下，9 号道路很可能会导致更短的解决方案路径。

开锁 - LeetCode，为什么计数器在每次递归调用中都在递增？

Open the lock - LeetCode, why counter keeps incrementing in every recursive call?

javascript

sorting

algorithm

breadth-first-search

greedy

Example 1

深度优先与广度优先