Leetcode刷题（18）栈的应用：钥匙和房间 (深度分析堆栈使用的易

题目
841. 钥匙和房间

难度：中等
题目分析：

1. 解法一：我自己想的，兜圈了……

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        # 基于栈的探索可以解决，反正就是一个个试
        # 建立一个答案数组，没探索的标1，
        # 等栈探索完，看答案数组的和是否为0，是可以走遍
        if len(rooms) == 1:
            return True # 一间房，肯定可以
        ans =[1]*len(rooms) # 默认都是1，如果能进入，就标位0
        my_stack = []        visited = set()
        # 第一个房间进栈
        if rooms[0] == []: # 没有钥匙
            return False
        ans[0] = 0
        visited.add(0)
        my_stack.append((0, 0))  # room_index, key_index
        while my_stack:
            room, i = my_stack.pop()
                # 把能打开的门标记上
            if rooms[room] == []: # 空房间不看
                continue
            for k in rooms[room]:
                if ans[k] == 1:   # 还没有钥匙
                    ans[k] = 0
            if sum(ans) ==0: # 检查是否探索好
                return True
            #while i<len(rooms[room]) and rooms[room][i] == room: # 防止回到自身
            #    i += 1
            # 前往下一个房间
            while i < len(rooms[room]) and rooms[room][i] in visited:
                i += 1
            if i == len(rooms[room]):
                continue  # 这里就没什么可以探索的了
            nxt = rooms[room][i] # 要进入下个房间
            visited.add(nxt)
            # 未探索的进栈
            if i+1 < len(rooms[room]):
                my_stack.append((room, i+1))
            my_stack.append((nxt, 0))
        return sum(ans) == 0

1.2 分析：

在完成栈的问题时，我还没能从教材的迷宫模板中走出来，导致了这道题走了弯路。上述代码有超级多的冗余。

 1/3    1 2 3 下一页 尾页