时间戳

首页 > 解决方案 > BFS 解决 openLock

python - BFS 解决 openLock

问题描述

Leetcode 引入了两个 BFS-Template，第二个：

#Return the length of the shortest path between root and target node.
#the pseudocode 
def bfs(root, target) 
    #declare data
    queue = deque()  # store all nodes which are waiting to be processed
    visited = set() # store all the nodes that we've visited
    #step to monitro the implemantions
    step = 0;       # number of steps neeeded from root to current node
    # initialize
    add root to queue
    add root to visited;
    # BFS
    while (queue is not empty) {
        step = step + 1;
        # iterate the nodes which are already in the queue
        size = len(queue); 
        for (int i = 0; i < size; ++i) 
            Node cur = the first node in queue; 
            return step if cur is target; 
            for (Node next : the neighbors of cur) #stretch .
                if (next is not in used) #
                    add next to queue;
                    add next to visited;
            remove the first node from queue; #
    return -1;           #failure

模板很清晰，因为它一次只做一件事，
1）做terminating check在Node cur = the first node in queue；
2）在以下迭代中拉伸以查找邻居。
相比之下，if next == target, return step +1 当前级别的许多实施检查混合了终止检查和拉伸工作。

使用模板解决openLock问题

您前面有一把带有 4 个圆形轮子的锁。每个轮子有 10 个插槽：'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. 轮子可以自由旋转和环绕：例如我们可以转动'9'to be'0'或'0'to be '9'。每一步都包括转动一个轮子一个槽。

锁最初从 开始'0000'，一个代表 4 个轮子状态的字符串。

你会得到一个deadends死胡同列表，这意味着如果锁显示任何这些代码，锁的轮子将停止转动，你将无法打开它。

给定 atarget表示将解锁锁的轮子的值，返回打开锁所需的最小总转数，如果不可能，则返回 -1。

示例 1：

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

我的解决方案

class Solution5:
    def openLock(self, deadends, target):
        from collections import deque
        #declare 
        queue = deque()
        visited = set()
        root = '0000'
        #initiate 
        step = 0
        deads = set(deadends)
        queue.append(root)
        visited.add(root)

        if root in deads: return -1 #fast fail

        while queue: 
            step += 1  
            size = len(queue)  

            for i in range(size):
                cur = queue.popleft()
                #logging.debug(f"cur: {cur}, step: {step}")
                if cur == target: return step 
                #collect the next node.
                #stretch and add next to queue
                for i in range(0, 4):
                    for j in [-1, 1]: 
                        nxt = cur[:i] + str((int(cur[i]) + j + 10) % 10) + cur[i+1:]
                        if (nxt not in deads) and  (nxt not in visited): 
                            queue.append(nxt)
                            visited.add(nxt)
        return -1 #failure case

用案例测试：

    def test_b(self):
        deadends = ["8888"] #0000-> 0009 one step 
        target = "0009"
        answer = 1
        check = self.solution.openLock(deadends, target)
        self.assertEqual(answer, check)

不幸的是，它报告错误

base) 10:48AM 15/04 Monday:me@host:~/Documents/Programs/Algorithms:
$ python 752.OpenTheLock.py  MyCase.test_b
DEBUG cur: 0000, step: 1
DEBUG cur: 9000, step: 2
DEBUG cur: 1000, step: 2
DEBUG cur: 0900, step: 2
DEBUG cur: 0100, step: 2
DEBUG cur: 0090, step: 2
DEBUG cur: 0010, step: 2
DEBUG cur: 0009, step: 2
F
======================================================================
FAIL: test_b (__main__.MyCase)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "752.OpenTheLock.py", line 184, in test_b
    self.assertEqual(answer, check)
AssertionError: 1 != 2

----------------------------------------------------------------------
Ran 1 test in 0.002s

FAILED (failures=1)

必须重新启动step = -1

.
----------------------------------------------------------------------
Ran 3 tests in 0.750s

OK

Templeate II 的 java 和 C++ 实现使用了 pre-increment ++step，

那么，检查根是否被视为步骤0？
step = -1是python实现中的适当启动吗？

标签： python

解决方案

提问：

检查根是否被视为步骤0？
step = -1 是python实现中的适当启动吗？

是的，我们应该step = -1在这里使用，因为队列中的第一个元素是0000，它不在结果中，所以我们应该减少step到-1。

提问：

“相比之下，if next == target, return step +1当前级别的许多实施检查混合了终止检查和延伸工作。”

这是一种提前停止的方法，因为我们已经知道它不会通过递归的终止检查，所以我们只是不输入它，并对其进行修剪。它将减少一个递归深度。

但正如您所说，在许多情况下，不推荐这种实现，因为它会将终止检查和拉伸工作混合在一起。

推荐阅读