【leetcode+深度/广度优先搜索】841. 钥匙和房间 (DFS,BFS)

leetcode-cn：leetcode面试75道精华：https://leetcode.cn/studyplan/leetcode-75/
841.钥匙和房间：https://leetcode.cn/problems/keys-and-rooms/description/

在这里插入图片描述

一、题目：841. 钥匙和房间

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入所有房间返回 true，否则返回

示例

示例 1：输入：rooms = [[1],[2],[3],[]] 输出：true 解释：我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。然后我们去 2 号房间，拿到钥匙 3。最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：输入：rooms = [[1,3],[3,0,1],[2],[0]] 输出：false 解释：我们不能进入 2 号房间。

提示：

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <=sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
所有 rooms[i] 的值 互不相同

解法1：`深度`优先搜索（DFS, Depth First Search）

深度优先搜索（DFS）（算法笔记）：https://blog.csdn.net/Arabot_/article/details/129702049

深度优先搜索属于搜索问题的一种，当问题可以被描述为“路径搜索”时，就可以采用搜素问题的所有解的方式来进行解决，所以DFS本质还是暴力。

深度搜索具有两个关键词，即“岔道口”和“死胡同”，这两个词来源于迷宫问题，这也是搜索问题最原始的表现。
当碰到岔道口时（一次多个选择时），总是以“深度”作为前进的关键词，不碰到死胡同就不回头，因此被称为“深搜”。
深搜适合于求解需要**遍历所有解或路径的问题**，并且剪枝很重要。
深搜和广搜在数据结构中的应用就是对非线性存储结构进行遍历。
搜索和分治是两大分析问题的方法，而回溯、剪枝、动态规划可以说是对深度搜索和分治算法进行优化。

思路（常用递归）

from https://leetcode.cn/problems/keys-and-rooms/solutions/18826/7xing-dfs-8xing-bfs-liang-chong-fang-fa-san-chong-

先找第０个房间的第一个钥匙
进入那个房间，再找它的第一个钥匙重复以往，直到没钥匙了，
那么退回当前房间，找到房间的第二把钥匙，如果该房间没有，则返回上一间房间，重复以往

递归调用函数的
在这里插入图片描述

python代码

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        # 抽象
        # 一个数字就是一个房间，以及二维数组中数据，也可以通用理解为节点序号
        # set add remove 添加删除原始
        # set1.union(set2)   并集
        # set1.intersection(set2) 交集
        # 如果没有返回，程序自动返回继续执行
        # nonlocal 关键字用于在嵌套函数中声明一个变量不属于本地作用域，
        # 它指向的是上一层函数的局部变量。这意味着你可以在嵌套函数中修改外部函数的变量。
        def dps(x):
            vist.add(x)
            for key in rooms[x]:
                if key not in vist:
                    dps(key)

        vist=set()
        dps(0)
        num_rooms=len(rooms)
        return  len(vist)==num_rooms

python多级嵌套函数如何理解？

嵌套函数可以访问其外部函数的变量和参数，这是一种封装和组织代码的方式

 def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
 	  def dfs(x: int):
 	  	vist.add(x)
	vist=set()

python set 和list 数据结构有什么区别?

vist=set()
# 或 vist={0}

Python 中的 set 和 list 是两种不同的数据结构，它们在元素操作方面有一些显著的区别：

元素唯一性：
set：集合中的元素是唯一的，不允许重复。
list：列表中的元素可以重复，没有唯一性要求。
元素顺序：
set：集合中的元素是无序的，不能通过索引访问元素。
list：列表中的元素是有序的，可以通过索引访问和操作元素。
性能：
set：由于集合使用哈希表实现，因此在查找、添加和删除元素时通常具有较高的性能。
list：列表的查找和删除操作（特别是对于大量元素）可能比集合慢，因为它们需要遍历整个列表。
元素操作：
set：
添加元素：使用 add() 方法。
删除元素：使用 remove()（如果元素不存在会引发错误）或 discard()（如果元素不存在也不会引发错误）方法。
交集、并集、差集等操作：使用 intersection(), union(), difference() 等方法。

list：
添加元素：使用 append() 方法或 insert() 方法。
删除元素：使用 remove() 方法（删除第一个匹配的元素）或 pop() 方法（删除指定索引处的元素）。
排序、反转等操作：使用 sort(), reverse() 等方法。

解法2 ：广度优先搜索（BFS）

https://leetcode.cn/problems/keys-and-rooms/solutions/18826/7xing-dfs-8xing-bfs-liang-chong-fang-fa-san-chong-

首先，建立一个登记表（python中用双向队列或者list实现），把０号房间的所有钥匙都依次记录，
然后删除0号房间在登记表（队列）记录，同时用一个visited表（set）记录已经去过的房间，防止重复登记
进入队列记录表中最早登记的房间（X号房间），结合（visited表）进行登记，去过的就不登记到队列记录表，登记完钥匙后，删除x号房间的记录
继续按按队列登记表的房间进入查找、登记，直到队列登记表没有要去的房间，表示所有能打开的房间都检查完了，
最后根据（visited表）房间的数量与已知房间数量对比，得出能否打开所有的房间（len(visited)==len(rooms)）

BFS的python代码

其中 collections.deque() # 创建一个空队列，这个是双向的队列

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        queue=collections.deque()  # 创建一个空队列，这个是双向的队列
        # 先将第0号房间添加到检查列表
        queue.extend(rooms[0])
        visited={0}  # 已经去过的房间
        while(len(queue)!=0):
            search_room_id=queue.pop() #  移除并返回队列的右端元素
            visited.add(search_room_id)
            for key in rooms[search_room_id]:
                if key not in visited:  # 获得钥匙是否去过，非常重要，否则会反复去
                    queue.append(key)

        print(visited,num_room)
         
        return  len(visited)==len(rooms)

python双向队列deque的操作方法

append(x)    在队列的**右端**添加一个元素。
appendleft(x)  在队列的**左端**添加一个元素。

extend(iterable) 在队列的右端添加多个元素，其中 iterable 可以是列表、集合或任何迭代器。
extendleft(iterable)，在队列的左端添加多个元素，iterable 中的元素会被逆序添加到队列中。


pop()   **移除并返回**队列的右端元素。
popleft()  移除并返回队列的左端元素。
remove(value)  移除队列中第一个匹配的 value 元素
clear()移除队列中的所有元素。

count(x)计算队列中元素 x 出现的次数。
reverse()  将队列中的元素反转。
copy()  创建并返回队列的一个浅拷贝。

index(x, start=0, stop=sys.maxsize)返回找到的第一个 x 元素的索引，索引范围从 start 到 stop。
insert(i, x)  在队列的指定位置 i 插入元素 x。如果插入会导致 deque 超过 maxlen 的限制，则会引发 IndexError。

具体操作



# 使用 extendleft 方法在队列头部添加列表中的所有元素
queue.extendleft(list_elements)

print("队列的内容:", list(queue))

二、巩固：547. 省份数量 (分类)

https://leetcode.cn/problems/number-of-provinces/description/?envType=study-plan-v2&envId=leetcode-75
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量
在这里插入图片描述

算法-深度优先

思路：
对于每个城市，如果该城市尚未被访问过，则从该城市开始深度优先搜索，通过矩阵 isConnected 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个连通分量，然后对这些城市继续深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份。
遍历完全部城市以后，即可得到连通分量的总数，即省份的总数。

链接：https://leetcode.cn/problems/number-of-provinces/solutions/549895/sheng-fen-shu-liang-by-leetcode-solution-eyk0/

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        visited=set()
        
        def dfs(city_id):
            visited.add(city_id)
            for j in range(0,len(isConnected)):
                if j not in visited and  isConnected[city_id][j] == 1:
                    dfs(j)
        count=0
        # 每次迭代，就把把一个省的城市找完
        for i in range(len(isConnected)):
            # 检查过的城市不用去了
            if  i not in visited:
                count+=1
                dfs(i)
        return count