leetcode刷题记录——图的广度优先遍历

909 蛇形棋 Medium

给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式 ，从左下角开始 （即，从 board[n - 1][0] 开始）每一行交替方向。

玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。

每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：

选定目标方格 next ，目标方格的编号符合范围 [curr + 1, min(curr + 6, n_2)] 。

该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。

传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。

当玩家到达编号 $n_2$ 的方格时，游戏结束。

r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 $n_2$ 的方格不是任何蛇或梯子的起点。

注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。

举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但 不能 顺着方格 3 上的梯子前往方格 4 。
返回达到编号为 $n_2$ 的方格所需的最少移动次数，如果不可能，则返回 -1。

示例 1：

输入：board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
输出：4
解释：
首先，从方格 1 [第 5 行，第 0 列] 开始。 
先决定移动到方格 2 ，并必须爬过梯子移动到到方格 15 。
然后决定移动到方格 17 [第 3 行，第 4 列]，必须爬过蛇到方格 13 。
接着决定移动到方格 14 ，且必须通过梯子移动到方格 35 。 
最后决定移动到方格 36 , 游戏结束。 
可以证明需要至少 4 次移动才能到达最后一个方格，所以答案是 4 。 

示例 2：

输入：board = [[-1,-1],[-1,3]]
输出：1

提示：

n == board.length == board[i].length

2 <= n <= 20

board[i][j] 的值是 -1 或在范围 [1, n2] 内

编号为 1 和 $n_2$ 的方格上没有蛇或梯子

思路

这里我的想法是先对棋盘进行处理，后续就不用管奇偶行怎么变化了。

然后用一个 snake 参数来存储棋盘中有效位置和其映射，这个主要是用于对梯子和蛇进行标记。

循环部分符合BFS的模板就不多说了，直接看代码

代码

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        snt = []
        for j, bd in enumerate(board[::-1]):
            snt.append(bd if j % 2 == 0 else bd[::-1])
        snake = {}
        n = len(board)
        
        for x in range(n):
            for y in range(n):
                cur = n * x + y + 1
                if snt[x][y] != -1:
                    snake[cur] = snt[x][y]
        start = {1}
        visited = {1}
        step = 1
        while start:
            next = set()
            for num in start:
                for j in range(1, 7):
                    newnum = num + j
                    if newnum in snake:
                        newnum = snake[newnum]
                    if newnum == n * n:
                        return step
                    if newnum not in visited:
                        next.add(newnum)
                        visited.add(newnum)
            step += 1
            start = next
        return -1

时间复杂度

时间复杂度O(n²)，空间复杂度O(n²)，执行时间65ms，消耗内存16.6MB

433 最小基因变化 Medium

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

提示：

start.length == 8

end.length == 8

0 <= bank.length <= 10

bank[i].length == 8

start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

思路

首先排除我们 end 和 bank 不匹配的情况。然后后续我们进行匹配，只需要ACGT里面匹配到就可以构建新的 gene 同时我们需要判断 gene 是否在 bank 中，只要在里面就一个添加一个删除。

代码

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        if endGene not in bank:
            return -1
        bank = set(bank)
        queue = deque([startGene])
        step = 0
        while queue:
            for _ in range(len(queue)):
                gene = queue.popleft()
                if gene == endGene:
                    return step
                for i in range(len(gene)):
                    for c in 'ACGT':
                        if c == gene[i]:
                            continue
                        new_gene = gene[ : i] + c + gene[i + 1:]
                        if new_gene in bank:
                            queue.append(new_gene)
                            bank.remove(new_gene)
            step += 1
        return -1

时间复杂度

时间复杂度O(n²)，空间复杂度O(n²)，执行时间41ms，消耗内存16.5MB

127 单词接龙 Hard

字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

每一对相邻的单词只差一个字母。

对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。

sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

1 <= beginWord.length <= 10

endWord.length == beginWord.length

1 <= wordList.length <= 5000

wordList[i].length == beginWord.length

beginWord、endWord 和 wordList[i] 由小写英文字母组成

beginWord != endWord

wordList 中的所有字符串 互不相同

思路

和上一题几乎一模一样，把元素从ACGT改为26个字母，step初始化为1（因为步数在计算的时候是不包括最开始的变量本身，所以初始化为1）。最后把没匹配到的从-1改为0，搞定。

代码

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        word = set(wordList)
        queue = deque([beginWord])
        step = 1
        while queue:
            for _ in range(len(queue)):
                gene = queue.popleft()
                if gene == endWord:
                    return step
                for i in range(len(gene)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        if c == gene[i]:
                            continue
                        new_gene = gene[ : i] + c + gene[i + 1:]
                        if new_gene in word:
                            queue.append(new_gene)
                            word.remove(new_gene)
            step += 1
        return 0

时间复杂度

时间复杂度O(n²)，空间复杂度O(n²)，执行时间373ms，消耗内存17.1MB