第一题、127.单词接龙（困难）
注：此题的两种思路都很长见识，抽象成图的模型的思维很值得学习，不愧是困难级别的题。代码不会写，看懂也费了老大劲，照着敲了一遍，日后需反复细品此题，并且需要亲手模拟例子。
方法一：广度优先搜索 + 优化建图
本题要求的是最短转换序列的长度，看到最短首先想到的就是广度优先搜索。想到广度优先搜索自然而然的就能想到图，但是本题并没有直截了当的给出图的模型，因此需要把它抽象成图的模型。
把每个单词都抽象为一个点，如果两个单词可以只改变一个字母进行转换，那么说明他们之间有一条双向边。因此只需要把满足转换条件的点相连，就形成了一张图。
基于该图，以 beginWord 为图的起点，以 endWord 为终点进行广度优先搜索，寻找 beginWord 到 endWord 的最短路径。
图的模型
首先为了方便表示，先给每一个单词标号，即给每个单词分配一个 id。创建一个由单词 word 到 id 对应的映射 wordId，并将 beginWord 与 wordList 中所有的单词都加入这个映射中。之后检查 endWord 是否在该映射内，若不存在，则输入无解。可以使用哈希表实现上面的映射关系。
然后建图，依据朴素的思路，可以枚举每一对单词的组合，判断它们是否恰好相差一个字符，以判断这两个单词对应的节点是否能够相连。但是这样效率太低，可以优化建图。
具体地，可以创建虚拟节点。对于单词 hit，创建三个虚拟节点 it、ht、hi*，并让 hit 向这三个虚拟节点分别连一条边即可。如果一个单词能够转化为 hit，那么该单词必然会连接到这三个虚拟节点之一。对于每一个单词，枚举它连接到的虚拟节点，把该单词对应的 id 与这些虚拟节点对应的 id 相连即可。
最后将起点加入队列开始广度优先搜索，当搜索到终点时，就找到了最短路径的长度。注意因为添加了虚拟节点，所以得到的距离为实际最短路径长度的两倍。同时并未计算起点对答案的贡献，所以应当返回距离的一半再加一的结果。
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
# 定义一个内部函数，用于将单词添加到wordId字典中
def addWord(word):
if word not in wordId:
# 使用nonlocal声明，确保nodeNum变量可以在内部函数中修改
global nodeNum
wordId[word] = nodeNum
nodeNum += 1
# 定义一个内部函数，用于将单词和它的“中间状态”单词添加到图的边中
def addEdge(word):
addWord(word)
id1 = wordId[word] # 获取当前单词的编号
chars = list(word) # 将单词转换为字符列表
for i in range(len(chars)):
tmp = chars[i]
chars[i] = "*" # 用'*'替换单词中的第i个字符，形成一个通用状态
newWord = "".join(chars)
addWord(newWord) # 将通用状态添加到字典中
id2 = wordId[newWord] # 获取通用状态的编号
edge[id1].append(id2) # 将当前单词与通用状态之间建立双向边
edge[id2].append(id1)
chars[i] = tmp # 还原字符列表中的第i个字符
wordId = dict() # 创建一个字典，存储每个单词和通用状态的编号
edge = collections.defaultdict(list) # 创建一个默认字典，用于存储图的边
global nodeNum
nodeNum = 0 # 初始化节点编号计数器
for word in wordList:
addEdge(word) # 对单词列表中的每个单词建立边
addEdge(beginWord) # 对起始单词建立边
if endWord not in wordId:
return 0 # 如果结束单词不在字典中，则返回0
dis = [float("inf")] * nodeNum # 初始化距离数组，设置所有节点的距离为正无穷
beginId, endId = wordId[beginWord], wordId[endWord] # 获取起始和结束单词的编号
dis[beginId] = 0 # 设置起始单词的距离为0
que = collections.deque([beginId]) # 初始化队列，并将起始单词编号加入队列
while que:
x = que.popleft() # 弹出队首元素
if x == endId:
return dis[endId] // 2 + 1 # 如果当前节点是结束节点，返回结果
for it in edge[x]:
if dis[it] == float("inf"):
dis[it] = dis[x] + 1 # 更新距离
que.append(it) # 将新的节点编号加入队列
return 0 # 如果无法到达结束单词，返回0
代码语法不熟悉的地方：
①join？
是一个字符串方法，用于将一个可迭代对象（如列表、元组等）中的元素连接成一个字符串，并在每个元素之间插入指定的分隔符。通常用来将多个字符串组合成一个字符串。
separator.join(iterable)
- separator: 分隔符，用来分隔可迭代对象中的元素。可以是任意字符串。
-
iterable: 一个可迭代对象，如列表、元组或字符串。
示例：
将列表中的字符串连接成一个字符串:
在这个例子中，words = ["hello", "world", "python"] result = " ".join(words) print(result) # 输出: "hello world python"" "（一个空格）作为分隔符，将列表words中的每个元素连接成一个字符串。
使用不同的分隔符:
这里使用了words = ["apple", "banana", "cherry"] result = ", ".join(words) print(result) # 输出: "apple, banana, cherry",作为分隔符。
连接元组中的元素:fruits = ("apple", "banana", "cherry") result = "-".join(fruits) print(result) # 输出: "apple-banana-cherry"
连接字符串中的字符:
s = "Python"
result = "_".join(s)
print(result) # 输出: "P_y_t_h_o_n"
连接包含非字符串元素的列表:
如果列表中包含非字符串元素，使用join时需要先将这些元素转换为字符串：
mixed_list = ["age", 30, "height", 180]
result = ":".join(map(str, mixed_list))
print(result) # 输出: "age:30:height:180"
-
join方法只能连接字符串类型的元素。如果可迭代对象中的元素不是字符串类型，需要先转换为字符串。 - 分隔符可以是任意字符串，包括空字符串
""，这意味着元素之间没有分隔符。
用时和内存
时空复杂度
方法二：双向广度优先搜索
根据给定字典构造的图可能会很大，而广度优先搜索的搜索空间大小依赖于每层节点的分支数量。假如每个节点的分支数量相同，搜索空间会随着层数的增长指数级的增加。考虑一个简单的二叉树，每一层都是满二叉树的扩展，节点的数量会以 2 为底数呈指数增长。
如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord 开始，另一边从 endWord 开始。每次从两边各扩展一层节点，当发现某一时刻两边都访问过同一顶点时就停止搜索。这就是双向广度优先搜索，它可以可观地减少搜索空间大小，从而提高代码运行效率。
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
# 添加一个新单词到wordId字典中，如果该单词不在字典中
def addWord(word):
if word not in wordId: # 如果单词不在wordId字典中
wordId[word] = len(wordId) # 将该单词加入字典并分配一个唯一的ID
# 添加一个单词及其所有可能的中间状态到图的边列表中
def addEdge(word):
addWord(word) # 添加单词到字典
id1 = wordId[word] # 获取该单词的ID
chars = list(word) # 将单词转换为字符列表
for i in range(len(chars)):
tmp = chars[i] # 暂存当前位置的字符
chars[i] = "*" # 将当前位置字符替换为通配符
newWord = "".join(chars) # 生成新的通配符单词
addWord(newWord) # 将通配符单词添加到字典
id2 = wordId[newWord] # 获取通配符单词的ID
edge[id1].append(id2) # 在图中添加原单词到通配符单词的边
edge[id2].append(id1) # 在图中添加通配符单词到原单词的边
chars[i] = tmp # 恢复原始字符
wordId = dict() # 初始化wordId字典
edge = collections.defaultdict(list) # 初始化边字典，值为列表
for word in wordList:
addEdge(word) # 为wordList中的每个单词添加边
addEdge(beginWord) # 为起始单词添加边
if endWord not in wordId: # 如果终止单词不在字典中，直接返回0
return 0
nodeNum = len(wordId) # 获取当前字典中单词的数量
disBegin = [float("inf")] * nodeNum # 初始化从起点的距离列表，长度为节点数，所有值为正无穷大
beginId = wordId[beginWord] # 获取起始单词的ID
disBegin[beginId] = 0 # 起始单词到自身的距离为0
queBegin = collections.deque([beginId]) # 初始化从起点出发的队列
disEnd = [float("inf")] * nodeNum # 初始化从终点的距离列表，长度为节点数，所有值为正无穷大
endId = wordId[endWord] # 获取终止单词的ID
disEnd[endId] = 0 # 终止单词到自身的距离为0
queEnd = collections.deque([endId]) # 初始化从终点出发的队列
while queBegin or queEnd: # 当任一队列不为空时执行
queBeginSize = len(queBegin) # 获取起点队列的当前大小
for _ in range(queBeginSize):
nodeBegin = queBegin.popleft() # 弹出队列中的第一个节点
if disEnd[nodeBegin] != float("inf"): # 如果终点队列已经访问过这个节点，说明两端相遇
return (disBegin[nodeBegin] + disEnd[nodeBegin]) // 2 + 1 # 计算并返回转换序列的最小长度
for it in edge[nodeBegin]: # 遍历当前节点的所有邻接节点
if disBegin[it] == float("inf"): # 如果这个邻接节点没有被访问过
disBegin[it] = disBegin[nodeBegin] + 1 # 更新起点队列到该节点的距离
queBegin.append(it) # 将该邻接节点加入起点队列
queEndSize = len(queEnd) # 获取终点队列的当前大小
for _ in range(queEndSize):
nodeEnd = queEnd.popleft() # 弹出队列中的第一个节点
if disBegin[nodeEnd] != float("inf"): # 如果起点队列已经访问过这个节点，说明两端相遇
return (disBegin[nodeEnd] + disEnd[nodeEnd]) // 2 + 1 # 计算并返回转换序列的最小长度
for it in edge[nodeEnd]: # 遍历当前节点的所有邻接节点
if disEnd[it] == float("inf"): # 如果这个邻接节点没有被访问过
disEnd[it] = disEnd[nodeEnd] + 1 # 更新终点队列到该节点的距离
queEnd.append(it) # 将该邻接节点加入终点队列
return 0 # 如果没有路径连接起点和终点，返回0
用时和内存
时空复杂度
第二题、126.单词接龙2（困难）
此题和127的区别是：127只需要输出最短转换序列中的单词数目，而本题需要找出并返回所有的最短转换序列。
方法、广度优先搜索 + 回溯
思路同127方法一，由于要求输出所有的最短路径，因此需要记录遍历路径，然后通过回溯得到所有的最短路径。
本题细节：
从一个单词出发，修改每一位字符，将它修改成为 ‘a’ 到 ‘z’ 中的所有字符，看看修改以后是不是在题目中给出的单词列表中；
有一些边的关系，由于不是最短路径上的边，不可以被记录下来。为此，需要为扩展出的单词记录附加的属性：层数。即下面代码中的 steps。如果当前的单词扩散出去得到的单词的层数在以前出现过，则不应该记录这样的边的关系。
class Solution(object):
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
res = []
# 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入集合，这里命名为「字典」
word_dict = set(wordList)
# 如果根本就不在字典里面，直接返回空列表
if endWord not in word_dict:
return res
# 特殊用例处理，删除起始单词
word_dict.discard(beginWord)
# 第 1 步：广度优先搜索建图
# 记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先搜索的第几层
steps = {beginWord: 0}
# 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系
from_dict = defaultdict(set)
step = 0
found = False
queue = deque([beginWord])
word_len = len(beginWord)
while queue:
step += 1
for _ in range(len(queue)):
currWord = queue.popleft()
nextWord = list(currWord) # 将字符串转为列表以便修改字符
# 将每一位替换成 26 个小写英文字母
for j in range(word_len):
origin = nextWord[j]
for c in 'abcdefghijklmnopqrstuvwxyz':
nextWord[j] = c
newWord = ''.join(nextWord)
if steps.get(newWord, step) == step:
from_dict[newWord].add(currWord)
if newWord not in word_dict:
continue
# 如果从一个单词扩展出来的单词以前遍历过，距离一定更远，为了避免搜索到已经遍历到且距离更远的单词，需要将它从字典中删除
word_dict.discard(newWord)
# 这一层扩展出的单词进入队列
queue.append(newWord)
# 记录 nextWord 从 currWord 而来
from_dict[newWord].add(currWord)
# 记录 nextWord 的 step
steps[newWord] = step
if newWord == endWord:
found = True
nextWord[j] = origin
if found:
break
# 第 2 步：回溯找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
if found:
path = [endWord]
self.backtrack(res, endWord, from_dict, path)
return res
def backtrack(self, res, node, from_dict, path):
"""
:type res: List[List[str]]
:type node: str
:type from_dict: dict
:type path: List[str]
"""
if not from_dict[node]:
res.append(path[::-1]) # 逆序添加路径
return
for parent in from_dict[node]:
path.append(parent)
self.backtrack(res, parent, from_dict, path)
path.pop()
用时和内存
示例详解：
beginWord = "hit"endWord = "cog"-
wordList = ["hot","dot","dog","lot","log","cog"]
目标是找到从beginWord到endWord的所有最短转换序列。每次只能改变一个字符，且每个中间单词必须存在于wordList中。
初始化
-
初始化字典和其他变量：
-
word_dict = {"hot", "dot", "dog", "lot", "log", "cog"}：将wordList转换为集合，以便快速查找。 - 如果
endWord不在字典中，直接返回空列表。由于cog在字典中，所以继续执行。 - 删除
beginWord"hit"，虽然它不在字典中，这步操作是预防特殊用例。 -
steps = {"hit": 0}：记录每个单词到达时的步数。 -
from_dict = defaultdict(set)：记录每个单词是从哪些单词扩展出来的。 -
queue = deque(["hit"])：广度优先搜索队列，用于逐层扩展单词。 -
word_len = 3：beginWord和endWord的长度。
-
广度优先搜索建图
-
第一层扩展 (
hit)：-
step = 1：当前步数增加到1。 - 处理队列中的单词
"hit"。 - 尝试将
"hit"的每一位字符替换为a-z的字母，生成新单词，检查它们是否在word_dict中。- 替换第一个字符：
"ait"，"bit"，...，"zit"都不在字典中，跳过。 - 替换第二个字符：
"hat"，"hbt"，...，"hzt"也不在字典中，跳过。 - 替换第三个字符：
"hia"，"hib"，...，最终发现"hot"在字典中。
- 替换第一个字符：
- 将
"hot"加入队列queue，并更新steps["hot"] = 1和from_dict["hot"] = {"hit"}。 - 将
"hot"从字典中移除，避免重复扩展。
-
-
第二层扩展 (
hot)：-
step = 2：当前步数增加到2。 - 处理队列中的单词
"hot"。 - 类似之前的操作，尝试替换
"hot"的每个字符：- 替换第一个字符：找到
"dot"在字典中，加入队列，并更新steps["dot"] = 2和from_dict["dot"] = {"hot"}。 - 替换第一个字符：找到
"lot"在字典中，加入队列，并更新steps["lot"] = 2和from_dict["lot"] = {"hot"}。
- 替换第一个字符：找到
- 将
"dot"和"lot"从字典中移除。
-
-
第三层扩展 (
dot和lot)：-
step = 3：当前步数增加到3。 - 处理队列中的
"dot"和"lot"。 - 对
"dot"进行扩展，找到"dog"，加入队列，并更新steps["dog"] = 3和from_dict["dog"] = {"dot"}。 - 对
"lot"进行扩展，找到"log"，加入队列，并更新steps["log"] = 3和from_dict["log"] = {"lot"}。 - 将
"dog"和"log"从字典中移除。
-
-
第四层扩展 (
dog和log)：-
step = 4：当前步数增加到4。 - 处理队列中的
"dog"和"log"。 - 对
"dog"进行扩展，找到"cog"，加入队列，并更新steps["cog"] = 4和from_dict["cog"] = {"dog"}。 - 对
"log"进行扩展，也找到"cog"，更新from_dict["cog"] = {"dog", "log"}。 - 由于找到了
endWord"cog"，设置found = True并跳出循环。
-
回溯路径
-
回溯找到所有最短路径：
- 如果找到目标单词
"cog"，调用backtrack函数从endWord开始回溯：- 路径
["cog"]：-
from_dict["cog"] = {"dog", "log"}，尝试扩展路径：- 对
"dog"进行扩展，路径变为["cog", "dog"]，再对"dot"进行扩展，路径变为["cog", "dog", "dot"]，最终到达"hit"，得到一条路径["hit", "dot", "dog", "cog"]。 - 对
"log"进行扩展，路径变为["cog", "log"]，再对"lot"进行扩展，路径变为["cog", "log", "lot"]，最终到达"hit"，得到另一条路径["hit", "lot", "log", "cog"]。
- 对
-
- 最终结果为
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]。
- 路径
- 如果找到目标单词
第三题、200.岛屿数量（中等）
方法一、深度优先搜索
将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量，可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是进行深度优先搜索的次数。
class Solution(object):
def dfs(self, grid, r, c):
# 将当前格子标记为已访问
grid[r][c] = '0'
# 获取网格的行数和列数
nr, nc = len(grid), len(grid[0])
# 检查当前格子的上下左右四个方向
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
# 如果新的坐标在网格范围内，且未访问过（即值为'1'），递归调用dfs
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == '1':
self.dfs(grid, x, y)
def numIslands(self, grid):
# 获取网格的行数
nr = len(grid)
# 如果网格为空，返回0
if nr == 0:
return 0
# 获取网格的列数
nc = len(grid[0])
# 初始化岛屿数量
num_islands = 0
# 遍历网格的每一个格子
for r in range(nr):
for c in range(nc):
# 如果当前格子是未访问的岛屿（即值为'1'）
if grid[r][c] == '1':
# 岛屿数量加1
num_islands += 1
# 使用深度优先搜索将当前岛屿的所有部分标记为已访问
self.dfs(grid, r, c)
# 返回岛屿的总数量
return num_islands
用时和内存
时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。
示例详解：输出：3
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
-
初始化阶段:
- 调用
numIslands函数，传入grid。 - 计算
nr（行数）为4，nc（列数）为5。 - 初始化
num_islands为0，用于计数岛屿的数量。
- 调用
-
第一轮遍历:
- 外层循环从
r=0开始，内层循环从c=0开始：-
第一次循环 (
r=0, c=0):- 检查
grid[0][0]，发现是"1"（未访问的陆地），因此开始处理一个新岛屿。 - 将
num_islands增加1，变为1。 - 调用
dfs函数，从位置(0, 0)开始。
- 检查
-
第一次循环 (
- 外层循环从
-
DFS 过程:
-
第一次 DFS (
r=0, c=0):- 将
grid[0][0]标记为"0"（表示已访问）。 - 检查上下左右的四个方向：
-
(r-1, c)即(-1, 0)超出网格范围，忽略。 -
(r+1, c)即(1, 0)处于网格范围内且值为"1"，递归调用dfs。
-
- 将
-
第二次 DFS (
r=1, c=0):- 将
grid[1][0]标记为"0"（表示已访问）。 - 再次检查上下左右四个方向：
-
(r-1, c)即(0, 0)，已标记为"0"，忽略。 -
(r+1, c)即(2, 0)是"0"，忽略。 -
(r, c-1)即(1, -1)超出范围，忽略。 -
(r, c+1)即(1, 1)是"1"，递归调用dfs。
-
- 将
-
第三次 DFS (
r=1, c=1):- 将
grid[1][1]标记为"0"（表示已访问）。 - 再次检查上下左右四个方向：
-
(r-1, c)即(0, 1)是"1"，递归调用dfs。
-
- 将
-
第四次 DFS (
r=0, c=1):- 将
grid[0][1]标记为"0"（表示已访问）。 - 再次检查上下左右四个方向：
-
(r-1, c)和(r, c-1)已访问或超出范围。 - 其他方向是
"0"，忽略。
-
- 至此，DFS 过程完成，当前岛屿的所有陆地块都被标记为
"0"。
- 将
-
-
继续遍历:
-
继续第一轮遍历:
-
r=0, c=2至r=0, c=4都是"0"，忽略。 -
r=1, c=2至r=1, c=4也是"0"，忽略。 -
r=2, c=0至r=2, c=1是"0"，忽略。 -
当
r=2, c=2:- 检查
grid[2][2]是"1"（未访问的陆地），开始处理一个新岛屿。 - 增加
num_islands为2。 - 调用
dfs从(2, 2)开始，类似上述步骤，将这个单独的岛屿标记为"0"。
- 检查
-
r=2, c=3至r=2, c=4是"0"，忽略。
-
-
继续遍历:
-
r=3, c=0至r=3, c=2是"0"，忽略。 -
当
r=3, c=3:- 检查
grid[3][3]是"1"（未访问的陆地），开始处理一个新岛屿。 - 增加
num_islands为3。 - 调用
dfs从(3, 3)开始，类似上述步骤，将当前岛屿的部分标记为"0"，并包括(3, 4)。
- 检查
-
r=3, c=4是"0"，忽略。
-
-
-
返回结果:
- 完成遍历，
num_islands的值为3，表示网格中有3个独立的岛屿。 - 最终返回
num_islands的值为3。
- 完成遍历，
此题我认为很妙的一个思路：“将深度优先搜索过程中每个搜索到的 1 标记为 0 ”，我想的是用一个专门的vis[]数组进行标记，实际上没有这个必要。
此题很像我考研时候学过的找森林里有几棵树的题。也是用的深度优先搜索，思路和此题非常一致，只是对象换了一下。
方法二：广度优先搜索
可以使用广度优先搜索代替深度优先搜索。
为了求出岛屿的数量，可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。
最终岛屿的数量就是进行广度优先搜索的次数。
class Solution(object):
def numIslands(self, grid):
# 获取网格的行数
nr = len(grid)
# 如果网格为空，返回0
if nr == 0:
return 0
# 获取网格的列数
nc = len(grid[0])
# 初始化岛屿数量
num_islands = 0
# 遍历网格的每一个格子
for r in range(nr):
for c in range(nc):
# 如果当前格子是未访问的岛屿（即值为'1'）
if grid[r][c] == '1':
# 岛屿数量加1
num_islands += 1
# 将当前格子标记为已访问
grid[r][c] = '0'
# 初始化队列并将当前格子添加到队列中
neighbors = collections.deque([(r, c)])
# 开始广度优先搜索（BFS）
while neighbors:
# 取出队列中的第一个格子
row, col = neighbors.popleft()
# 检查当前格子的上下左右四个方向
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
# 如果新的坐标在网格范围内，且未访问过（即值为'1'）
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == '1':
# 将其添加到队列中以便进一步搜索
neighbors.append((x, y))
# 并标记为已访问
grid[x][y] = '0'
# 返回岛屿的总数量
return num_islands
用时和内存
时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
空间复杂度：O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。
示例详解：
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
-
初始化阶段:
- 调用
numIslands函数，传入grid。 - 计算
nr（行数）为4，nc（列数）为5。 - 初始化
num_islands为0，用于计数岛屿的数量。
- 调用
-
第一轮遍历:
- 外层循环从
r=0开始，内层循环从c=0开始：-
第一次循环 (
r=0, c=0):- 检查
grid[0][0]，发现是"1"（未访问的陆地），因此开始处理一个新岛屿。 - 将
num_islands增加1，变为1。 - 将
grid[0][0]标记为"0"（表示已访问）。 - 初始化队列
neighbors，并将(0, 0)加入队列。
- 检查
-
第一次循环 (
- 外层循环从
-
BFS 过程:
-
第一次 BFS:
- 队列中包含
(0, 0)，取出(0, 0)进行处理。 - 检查
(0, 0)的四个方向：-
(r-1, c)即(-1, 0)超出网格范围，忽略。 -
(r+1, c)即(1, 0)处于网格范围内且值为"1"，加入队列并标记为"0"。 -
(r, c-1)即(0, -1)超出范围，忽略。 -
(r, c+1)即(0, 1)处于网格范围内且值为"1"，加入队列并标记为"0"。
-
- 队列现在包含
(1, 0)和(0, 1)。
- 队列中包含
-
第二次 BFS:
- 取出队列中的
(1, 0)进行处理。 - 检查
(1, 0)的四个方向：-
(r-1, c)即(0, 0)已标记为"0"，忽略。 -
(r+1, c)即(2, 0)是"0"，忽略。 -
(r, c-1)即(1, -1)超出范围，忽略。 -
(r, c+1)即(1, 1)处于网格范围内且值为"1"，加入队列并标记为"0"。
-
- 队列现在包含
(0, 1)和(1, 1)。
- 取出队列中的
-
第三次 BFS:
- 取出队列中的
(0, 1)进行处理。 - 检查
(0, 1)的四个方向：-
(r-1, c)和(r, c-1)已标记为"0"或超出范围，忽略。 - 其他方向是
"0"，忽略。
-
- 队列现在只剩下
(1, 1)。
- 取出队列中的
-
第四次 BFS:
- 取出队列中的
(1, 1)进行处理。 - 检查
(1, 1)的四个方向：-
(r-1, c)即(0, 1)已标记为"0"，忽略。 - 其他方向是
"0"，忽略。
-
- 至此，BFS 过程完成，当前岛屿的所有陆地块都被标记为
"0"。
- 取出队列中的
-
-
继续遍历:
-
继续第一轮遍历:
-
r=0, c=2至r=0, c=4都是"0"，忽略。 -
r=1, c=2至r=1, c=4也是"0"，忽略。 -
r=2, c=0至r=2, c=1是"0"，忽略。 -
当
r=2, c=2:- 检查
grid[2][2]是"1"（未访问的陆地），开始处理一个新岛屿。 - 增加
num_islands为2。 - 将
grid[2][2]标记为"0"。 - 初始化队列并将
(2, 2)加入队列，执行BFS，将这个单独的岛屿标记为"0"。
- 检查
-
r=2, c=3至r=2, c=4是"0"，忽略。
-
-
继续遍历:
-
r=3, c=0至r=3, c=2是"0"，忽略。 -
当
r=3, c=3:- 检查
grid[3][3]是"1"（未访问的陆地），开始处理一个新岛屿。 - 增加
num_islands为3。 - 将
grid[3, 3]标记为"0"。 - 初始化队列并将
(3, 3)加入队列，执行BFS，将当前岛屿的部分标记为"0"，并包括(3, 4)。
- 检查
-
r=3, c=4是"0"，忽略。
-
-
-
返回结果:
- 完成遍历，
num_islands的值为3，表示网格中有3个独立的岛屿。 - 最终返回
num_islands的值为3。
- 完成遍历，
方法三、并查集（难，得加强学习）
为了求出岛屿的数量，可以扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。
最终岛屿的数量就是并查集中连通分量的数目。
class UnionFind:
def __init__(self, grid):
m, n = len(grid), len(grid[0]) # 获取网格的行数和列数
self.count = 0 # 记录岛屿的数量
self.parent = [-1] * (m * n) # 初始化并查集的父节点数组，每个位置初始值为-1
self.rank = [0] * (m * n) # 初始化并查集的秩（树的高度）数组，每个位置初始为0
for i in range(m): # 遍历网格的每一行
for j in range(n): # 遍历网格的每一列
if grid[i][j] == "1": # 如果当前格子是陆地（值为"1"）
self.parent[i * n + j] = i * n + j # 将当前格子在并查集中设置为自己的父节点
self.count += 1 # 岛屿数量增加1
def find(self, i):
if self.parent[i] != i: # 如果当前节点不是它自己的父节点
self.parent[i] = self.find(self.parent[i]) # 递归地找到根节点，并进行路径压缩
return self.parent[i] # 返回当前节点的根节点
def union(self, x, y):
rootx = self.find(x) # 找到x的根节点
rooty = self.find(y) # 找到y的根节点
if rootx != rooty: # 如果x和y的根节点不同
if self.rank[rootx] < self.rank[rooty]: # 比较两个根节点的秩，秩小的作为子树
rootx, rooty = rooty, rootx
self.parent[rooty] = rootx # 将秩小的根节点连接到秩大的根节点上
if self.rank[rootx] == self.rank[rooty]: # 如果两个根节点的秩相同
self.rank[rootx] += 1 # 增加新根节点的秩
self.count -= 1 # 岛屿数量减少1
def getCount(self):
return self.count # 返回当前的岛屿数量
class Solution(object):
def numIslands(self, grid):
nr = len(grid) # 获取网格的行数
if nr == 0: # 如果网格为空
return 0 # 直接返回0
nc = len(grid[0]) # 获取网格的列数
uf = UnionFind(grid) # 创建并查集实例
num_islands = 0 # 初始化岛屿数量为0
for r in range(nr): # 遍历网格的每一行
for c in range(nc): # 遍历网格的每一列
if grid[r][c] == "1": # 如果当前格子是陆地
grid[r][c] = "0" # 将当前格子标记为已访问（设为"0"）
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]: # 检查上下左右四个相邻格子
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1": # 如果相邻格子在网格范围内且为陆地
uf.union(r * nc + c, x * nc + y) # 将当前格子与相邻格子进行合并
return uf.getCount() # 返回岛屿数量
用时和内存
时空复杂度
示例详解：
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
- 初始化
UnionFind类
uf = UnionFind(grid)
- 行数
m = 4，列数n = 5。 -
self.count = 0表示岛屿的数量，初始为0。 -
self.parent和self.rank数组长度为m * n = 20，分别初始化为[-1, -1, ..., -1]和[0, 0, ..., 0]。
遍历网格中的每个格子，如果格子为 "1"（即陆地），则将其在并查集中设置为自己的父节点，并将 count 增加1。
遍历网格：
- 遍历第1行：
- 第1个格子
(0,0)是 "1"：self.parent[0] = 0，self.count += 1（count = 1）。 - 第2个格子
(0,1)是 "1"：self.parent[1] = 1，self.count += 1（count = 2）。
- 第1个格子
- 遍历第2行：
- 第1个格子
(1,0)是 "1"：self.parent[5] = 5，self.count += 1（count = 3）。 - 第2个格子
(1,1)是 "1"：self.parent[6] = 6，self.count += 1（count = 4）。
- 第1个格子
- 遍历第3行：
- 第3个格子
(2,2)是 "1"：self.parent[12] = 12，self.count += 1（count = 5）。
- 第3个格子
- 遍历第4行：
- 第4个格子
(3,3)是 "1"：self.parent[18] = 18，self.count += 1（count = 6）。 - 第5个格子
(3,4)是 "1"：self.parent[19] = 19，self.count += 1（count = 7）。
- 第4个格子
初始化完成后，parent 和 rank 数组如下：
parent = [0, 1, -1, -1, -1, 5, 6, -1, -1, -1, -1, -1, 12, -1, -1, -1, -1, -1, 18, 19]rank = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]-
count = 7。
2. 遍历网格并合并相邻的陆地
在 Solution 类中的 numIslands 方法中：
- 遍历每个格子，如果格子是 "1"，则将其置为 "0"（表示已访问过），并将其与相邻的四个格子合并。
- 遍历第1行：
- 第1个格子
(0,0)是 "1"：- 将
(0,0)置为 "0"。 - 检查相邻的格子
(1,0)是 "1"，执行uf.union(0, 5)：-
find(0)返回0。 -
find(5)返回5。 -
rootx = 0，rooty = 5，self.parent[5] = 0，count = 6。
-
- 检查相邻的格子
(0,1)是 "1"，执行uf.union(0, 1)：-
find(0)返回0。 -
find(1)返回1。 -
rootx = 0，rooty = 1，self.parent[1] = 0，count = 5。
-
- 将
- 第2个格子
(0,1)已经被置为 "0"（跳过）。
- 第1个格子
- 遍历第2行：
- 第1个格子
(1,0)已经被置为 "0"（跳过）。 - 第2个格子
(1,1)是 "1"：- 将
(1,1)置为 "0"。 - 检查相邻的格子
(0,1)和(1,0)都已被置为 "0"（跳过）。
- 将
- 第1个格子
- 遍历第3行：
- 第3个格子
(2,2)是 "1"：- 将
(2,2)置为 "0"。
- 将
- 第3个格子
- 遍历第4行：
- 第4个格子
(3,3)是 "1"：- 将
(3,3)置为 "0"。 - 检查相邻的格子
(3,4)是 "1"，执行uf.union(18, 19)：-
find(18)返回18。 -
find(19)返回19。 -
rootx = 18，rooty = 19，self.parent[19] = 18，count = 4。
-
- 将
- 第4个格子
3. 返回岛屿数量
所有格子遍历完后，uf.getCount() 返回 4，但由于这段代码实际上实现了3个岛屿【初始自带】，其中两个岛屿被分别合并（合并前值是5，最后变为3），最终返回的 count 是 3。
注：在这个代码中，使用了两个类（UnionFind 和 Solution），主要是为了代码的组织和可读性。
UnionFind 类专注于实现并查集数据结构及其操作，如 find 和 union。这个类可以独立地用于任何涉及连通性的问题，不仅仅是岛屿问题。
Solution 类则专注于解决具体的岛屿数量计算问题，它使用了 UnionFind 类来帮助实现算法。
