51题433题

第一题、51.N皇后（困难）

「N 皇后问题」研究的是如何将 N 个皇后放置在 N×N 的棋盘上，并且使皇后彼此之间不能相互攻击。
皇后的走法是：可以横直斜走，格数不限。因此要求皇后彼此之间不能相互攻击，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。
直观的做法是暴力枚举将 N 个皇后放置在 N×N 的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后彼此之间不相互攻击。暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。
显然，每个皇后必须位于不同行和不同列，因此将 N 个皇后放置在 N×N 的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式寻找可能的解。
回溯的具体做法是：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。每次新放置的皇后都不能和已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的当前行的皇后列下标。当 N 个皇后都放置完毕，则找到一个可能的解。当找到一个可能的解之后，将数组转换成表示棋盘状态的列表，并将该棋盘状态的列表加入返回列表。
由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 N 列可以选择，第二个皇后最多有 N−1 列可以选择，第三个皇后最多有 N−2 列可以选择（如果考虑到不能在同一条斜线上，可能的选择数量更少），因此所有可能的情况不会超过 N! 种，遍历这些情况的时间复杂度是 O(N!)。
为了降低总时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后，显然，最理想的情况是在 O(1) 的时间内判断该位置所在的列和两条斜线上是否已经有皇后。
以下两种方法分别使用集合和位运算对皇后的放置位置进行判断，都可以在 O(1) 的时间内判断一个位置是否可以放置皇后，算法的总时间复杂度都是 O(N!)。

方法一：基于集合的回溯
为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合columns、diagonals1 和 diagonals2 分别记录每一列以及两个方向的每条斜线上是否有皇后。
列的表示法很直观，一共有 N 列，每一列的下标范围从 0 到 N−1，使用列的下标即可明确表示每一列。
如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。
方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

方向一的斜线

方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0) 和 (1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

方向二的斜线

每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

class Solution(object):
    def solveNQueens(self, n):
        def generateBoard():
            board = list()
            for i in range(n):
                # 将第i行对应的皇后位置标记为"Q"
                row[queens[i]] = "Q"
                # 将该行转换为字符串并加入棋盘
                board.append("".join(row))
                # 恢复该行原本的状态
                row[queens[i]] = "."
            return board

        def backtrack(row):
            if row == n:
                # 如果所有行都成功放置了皇后，生成当前棋盘并加入解决方案
                board = generateBoard()
                solutions.append(board)
            else:
                for i in range(n):
                    # 如果第i列或两个对角线已经有皇后，跳过
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    # 记录皇后的位置
                    queens[row] = i
                    # 标记第i列和两个对角线
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)
                    # 递归处理下一行
                    backtrack(row + 1)
                    # 回溯：移除第i列和两个对角线的标记
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)

        # 初始化解决方案列表
        solutions = list()
        # 初始化皇后的位置列表，初始值为-1，表示未放置
        queens = [-1] * n
        # 初始化列、主对角线、副对角线的集合，用于标记皇后占据的位置
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        # 初始化每一行的字符串表示，初始状态下全为"."
        row = ["."] * n
        # 从第0行开始回溯搜索
        backtrack(0)
        # 返回所有找到的解决方案
        return solutions

用时和内存

时间复杂度：O(N!)，其中 N 是皇后数量。
空间复杂度：O(N)，其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 N，数组的长度为 N，每个集合的元素个数都不会超过 N。

示例详解：n=4 ：
初始状态：

solutions = []：存放所有合法的棋盘布局。
queens = [-1, -1, -1, -1]：存放每一行皇后的位置，初始值为 -1 表示未放置。
columns = set()：存放已经放置皇后的列。
diagonal1 = set()：存放已经放置皇后的主对角线（左上到右下的斜线）。
diagonal2 = set()：存放已经放置皇后的副对角线（右上到左下的斜线）。
row = [".", ".", ".", "."]：表示当前行的棋盘状态，初始全为 "."

开始：backtrack(0)
进入第 0 行开始尝试放置皇后。
- 尝试第 0 行，第 0 列：i=0
  - columns、diagonal1、diagonal2 都为空，可以放置皇后。
  - 更新 queens：queens[0] = 0
  - 更新 columns：columns = {0}
  - 更新 diagonal1：diagonal1 = {0}（计算方式：row - i = 0 - 0）
  - 更新 diagonal2：diagonal2 = {0}（计算方式：row + i = 0 + 0）
    然后递归到下一行：backtrack(1)。
进入第 1 行：backtrack(1)
- 尝试第 1 行，第 0 列：i=0
  - 第 0 列已经有皇后 (i in columns)，跳过。
- 尝试第 1 行，第 1 列：i=1
  - 主对角线 0 上已经有皇后 (row - i = 1 - 1 = 0 in diagonal1)，跳过。
- 尝试第 1 行，第 2 列：i=2
  - 没有冲突，可以放置皇后。
  - 更新 queens：queens[1] = 2
  - 更新 columns：columns = {0, 2}
  - 更新 diagonal1：diagonal1 = {0, -1}（计算方式：row - i = 1 - 2 = -1）
  - 更新 diagonal2：diagonal2 = {0, 3}（计算方式：row + i = 1 + 2 = 3）
    然后递归到下一行：backtrack(2)。
进入第 2 行：backtrack(2)
- 尝试第 2 行，第 0 列：i=0
  - 第 0 列已经有皇后 (i in columns)，跳过。
- 尝试第 2 行，第 1 列：i=1
  - 副对角线 3 上已经有皇后 (row + i = 2 + 1 = 3 in diagonal2)，跳过。
- 尝试第 2 行，第 2 列：i=2
  - 第 2 列已经有皇后 (i in columns)，跳过。
- 尝试第 2 行，第 3 列：i=3
  - 主对角线 -1 上已经有皇后 (row - i = 2 - 3 = -1 in diagonal1`)，跳过。
回溯：第 2 行无法放置皇后，回溯到第 1 行，继续尝试下一个位置。
- 回溯操作包括：
  - 移除 queens[1] = 2，即将第 1 行的皇后移除。
  - 更新 columns：columns = {0}
  - 更新 diagonal1：diagonal1 = {0}
  - 更新 diagonal2：diagonal2 = {0}
    然后在第 1 行继续尝试放置皇后。
- 尝试第 1 行，第 3 列：i=3
  - 没有冲突，可以放置皇后。
  - 更新 queens：queens[1] = 3
  - 更新 columns：columns = {0, 3}
  - 更新 diagonal1：diagonal1 = {0, -2}（计算方式：row - i = 1 - 3 = -2）
  - 更新 diagonal2：diagonal2 = {0, 4}（计算方式：row + i = 1 + 3 = 4）
    然后递归到下一行：backtrack(2)。
进入第 2 行：backtrack(2)
- 尝试第 2 行，第 0 列：i=0
  - 第 0 列已经有皇后 (i in columns)，跳过。
- 尝试第 2 行，第 1 列：i=1
  - 没有冲突，可以放置皇后。
  - 更新 queens：queens[2] = 1
  - 更新 columns：columns = {0, 1, 3}
  - 更新 diagonal1：diagonal1 = {0, 1, -2}（计算方式：row - i = 2 - 1 = 1）
  - 更新 diagonal2：diagonal2 = {0, 3, 4}（计算方式：row + i = 2 + 1 = 3）
    然后递归到下一行：backtrack(3)。
进入第 3 行：backtrack(3)
- 尝试第 3 行，第 0 列：i=0
  - 第 0 列已经有皇后 (i in columns)，跳过。
- 尝试第 3 行，第 1 列：i=1
  - 副对角线 3 上已经有皇后 (row + i = 3 + 1 = 4 in diagonal2)，跳过。
- 尝试第 3 行，第 2 列：i=2
  - 主对角线 1 上已经有皇后 (row - i = 3 - 2 = 1 in diagonal1)，跳过。
- 尝试第 3 行，第 3 列：i=3
  - 第 3 列已经有皇后 (i in columns)，跳过。
回溯：第 3 行无法放置皇后，回溯到第 2 行，继续尝试下一个位置。
- 回溯操作包括：
  - 移除 queens[2] = 1，即将第 2 行的皇后移除。
  - 更新 columns：columns = {0, 3}
  - 更新 diagonal1：diagonal1 = {0, -2}
  - 更新 diagonal2：diagonal2 = {0, 4}
    然后在第 2 行继续尝试放置皇后。
- 尝试第 2 行，第 2 列：i=2
  - 第 2 列已经有皇后 (i in columns)，跳过。
- 尝试第 2 行，第 3 列：i=3
  - 副对角线 4 上已经有皇后 (row + i = 2 + 3 = 5 in diagonal2)，跳过。
回溯：第 2 行无法放置皇后，回溯到第 1 行，继续尝试下一个位置。
- 回溯操作包括：
  - 移除 queens[1] = 3，即将第 1 行的皇后移除。
  - 更新 columns：columns = {0}
  - 更新 diagonal1：diagonal1 = {0}
  - 更新 diagonal2：diagonal2 = {0}
    然后在第 1 行继续尝试放置皇后。
- 第 1 行所有列已尝试过，继续回溯到第 0 行，尝试下一个位置。
继续回溯到第 0 行：
- 尝试第 0 行，第 1 列：i=1
  - 没有冲突，可以放置皇后。
  - 更新 queens：queens[0] = 1
  - 更新 columns：columns = {1}
  - 更新 diagonal1：diagonal1 = {-1}（计算方式：row - i = 0 - 1 = -1）
  - 更新 diagonal2：diagonal2 = {1}（计算方式：row + i = 0 + 1 = 1）
    然后递归到下一行：backtrack(1)。
接下来就是在每一行上继续重复上述步骤，直到找到合法解或所有可能位置都尝试过。

generateBoard 函数生成棋盘的过程：
假设 queens = [1, 3, 0, 2]，这意味着：

第 0 行的皇后在第 1 列（"Q" 位于第 1 列）。
第 1 行的皇后在第 3 列（"Q" 位于第 3 列）。
第 2 行的皇后在第 0 列（"Q" 位于第 0 列）。
第 3 行的皇后在第 2 列（"Q" 位于第 2 列）。
逐行生成棋盘：

第 0 行：
- queens[0] = 1，意味着第 0 行的皇后在第 1 列。
- 初始 row = [".", ".", ".", "."]。
- 将 row[1] 设为 "Q"，变成 [".", "Q", ".", "."]。
- 将这个列表转换为字符串 ".Q.." 并加入 board。
第 1 行：
- queens[1] = 3，意味着第 1 行的皇后在第 3 列。
- 初始 row = [".", ".", ".", "."]。
- 将 row[3] 设为 "Q"，变成 [".", ".", ".", "Q"]。
- 将这个列表转换为字符串 "....Q" 并加入 board。
第 2 行：
- queens[2] = 0，意味着第 2 行的皇后在第 0 列。
- 初始 row = [".", ".", ".", "."]。
- 将 row[0] 设为 "Q"，变成 ["Q", ".", ".", "."]。
- 将这个列表转换为字符串 "Q..." 并加入 board。
第 3 行：
- queens[3] = 2，意味着第 3 行的皇后在第 2 列。
- 初始 row = [".", ".", ".", "."]。
- 将 row[2] 设为 "Q"，变成 [".", ".", "Q", "."]。
- 将这个列表转换为字符串 "..Q." 并加入 board。

方法二：基于位运算的回溯（未学习，二刷时候再说吧，方法一我感觉非常清晰易懂，先学会方法一）

第二题、433.最小基因变化（中等）

此题一开始我对题意有误解，疑问为什么不能直接比较start和end两个字符串对应位置上不同的字母有几个即变化个数是几？
忽略了题目中重要信息：变化后的中间基因序列也必须在bank中。
方法一、广度优先搜索
题目要求将一个基因序列 A 变化至另一个基因序列 B，需要满足以下条件：
①序列 A 与序列 B 之间只有一个字符不同；
②变化字符只能从 ‘A’, ‘C’, ‘G’, ‘T’ 中进行选择；
③变换后的序列 B 一定要在字符串数组 bank 中。
算法步骤：
-如果 start 与 end 相等，此时直接返回 0；如果最终的基因序列不在 bank 中，则此时按照题意要求，无法生成，直接返回 −1；
-首先将可能变换的基因 s 从队列中取出，按照上述的变换规则，尝试所有可能的变化后的基因，比如一个 AACCGGTA，依次尝试改变基因 s 的一个字符，并尝试所有可能的基因变化序列 s0,s1,s2,⋯,si,⋯,s23，变化一次最多可能会生成
3×8=24 种不同的基因序列。
-需要检测当前生成的基因序列的合法性 si ，首先利用哈希表检测 si 是否在数组 bank 中，如果是则认为该基因合法，否则该变化非法直接丢弃；其次还需要用哈希表记录已经遍历过的基因序列，如果该基因序列已经遍历过，则此时直接跳过；如果合法且未遍历过的基因序列，则将其加入到队列中。
-如果当前变换后的基因序列与 end 相等，则此时直接返回最小的变化次数即可；如果队列中所有的元素都已经遍历完成还无法变成 end，则此时无法实现目标变化，返回 −1。

class Solution(object):
    def minMutation(self, start, end, bank):
        # 如果起始基因序列和目标基因序列相同，返回0
        if start == end:
            return 0
        
        # 将基因库转换为集合以加快查找速度
        bank = set(bank)
        
        # 如果目标基因序列不在基因库中，返回-1
        if end not in bank:
            return -1
        
        # 初始化队列，存储当前基因序列和步数
        q = deque([(start, 0)])
        
        # 广度优先搜索
        while q:
            cur, step = q.popleft()  # 从队列中取出当前基因序列和步数
            
            # 遍历当前基因序列中的每一个位置
            for i, x in enumerate(cur):
                # 尝试用每一种可能的碱基替换当前碱基
                for y in "ACGT":
                    if y != x:
                        # 生成新的基因序列
                        nxt = cur[:i] + y + cur[i + 1:]
                        
                        # 如果新基因序列在基因库中
                        if nxt in bank:
                            # 如果新基因序列是目标基因序列，返回步数加1
                            if nxt == end:
                                return step + 1
                            
                            # 从基因库中移除已访问的基因序列
                            bank.remove(nxt)
                            
                            # 将新基因序列和步数加1入队列
                            q.append((nxt, step + 1))
        
        # 如果无法转换到目标基因序列，返回-1
        return -1

代码语法不熟悉的地方：
①enumerate() 是一个 Python 内置函数，用于遍历序列时同时获取元素的索引和值。

for i, x in enumerate(cur):
    # i 是索引，x 是字符

用时和内存

（这是第一次用时击败100%！）
时间复杂度：O(C×n×m)，其中 n 为基因序列的长度，m 为数组 bank 的长度。对于队列中的每个合法的基因序列每次都需要计算 C×n 种变化，在这里 C=4；队列中最多有 m 个元素，因此时间复杂度为 O(C×n×m)。
空间复杂度：O(n×m)，其中 n 为基因序列的长度，m 为数组 bank 的长度。合法性的哈希表中一共存有 m 个元素，队列中最多有 m 个元素，每个元素的空间为 O(n)；队列中最多有 m 个元素，每个元素的空间为 O(n)，因此空间复杂度为 O(n×m)。

示例详解：
输入:

start = "AACCGGTT"
end = "AAACGGTA"
bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
输出: 2
代码运行过程模拟：

初始化:
- bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"}
- q = deque([("AACCGGTT", 0)])
广度优先搜索 (BFS) 过程:
- 第一轮迭代:
  - 从队列中取出 (cur, step)，即 ("AACCGGTT", 0)
  - 遍历每个位置的碱基：
    - 位置 0 的碱基 A 尝试变为 C, G, T：
      - "CACCGGTT", "GACCGGTT", "TACCGGTT" 都不在 bank 中，忽略。
    - 位置 1 的碱基 A 尝试变为 C, G, T：
      - "ACCCGGTT", "AGCCGGTT", "ATCCGGTT" 都不在 bank 中，忽略。
    - 位置 2 的碱基 C 尝试变为 A, G, T：
      - "AAACGGTT", "AGACGGTT", "ATACGGTT" 都不在 bank 中，忽略。
    - 位置 3 的碱基 C 尝试变为 A, G, T：
      - "AAAGGGTT", "AAGCGGTT", "AATCGGTT" 都不在 bank 中，忽略。
    - 位置 4 的碱基 G 尝试变为 A, C, T：
      - "AACAGGTT", "AACCGATT", "AACCTGTT" 都不在 bank 中，忽略。
    - 位置 5 的碱基 G 尝试变为 A, C, T：
      - "AACCGATT", "AACCGCTT", "AACCGTTT" 都不在 bank 中，忽略。
    - 位置 6 的碱基 T 尝试变为 A, C, G：
      - "AACCGGAT", "AACCGGCT", "AACCGGGT" 都不在 bank 中，忽略。
    - 位置 7 的碱基 T 尝试变为 A, C, G：
      - "AACCGGTA" 在 bank 中，将其添加到队列，步数为 1。
  - 更新队列为 deque([("AACCGGTA", 1)])
- 第二轮迭代:
  - 从队列中取出 (cur, step)，即 ("AACCGGTA", 1)
  - 遍历每个位置的碱基：
    - 位置 0 的碱基 A 尝试变为 C, G, T：
      - "CACCGGTA", "GACCGGTA", "TACCGGTA" 都不在 bank 中，忽略。
    - 位置 1 的碱基 A 尝试变为 C, G, T：
      - "ACCCGGTA", "AGCCGGTA", "ATCCGGTA" 都不在 bank 中，忽略。
    - 位置 2 的碱基 C 尝试变为 A, G, T：
      - "AAACGGTA" 在 bank 中，且是目标序列 end，返回 step + 1，即 2。

方法二、预处理优化
已知方法一中广度优先搜索方法，可以对 bank 进行预处理，即只在合法的基因变化进行搜索。由于题目中给定的 bank 基因库的长度较小，因此可以直接对 bank 进行预处理，找到基因库中的每个基因的合法变换，而不需要像方法一中每次都需要去计算基因的变化序列。因此将每个基因的合法变化关系存储在邻接表 adj 中，每次基因变化搜索只在 adj 中进行即可。

class Solution(object):
    def minMutation(self, start, end, bank):
        # 如果起始基因序列已经等于目标基因序列，直接返回0
        if start == end:
            return 0

        # 定义一个函数来检查两个基因序列是否只有一个字符不同
        def diffOne(s, t):
            return sum(x != y for x, y in zip(s, t)) == 1

        # 获取基因库的大小
        m = len(bank)
        # 创建一个邻接列表来存储基因库中每个基因的相邻基因
        adj = [[] for _ in range(m)]
        # 记录目标基因在基因库中的索引
        endIndex = -1
        # 遍历基因库中的每个基因
        for i, s in enumerate(bank):
            # 如果当前基因是目标基因，记录它的索引
            if s == end:
                endIndex = i
            # 对比当前基因和其他基因，构建图的邻接关系
            for j in range(i + 1, m):
                # 如果两个基因序列只有一个字符不同，更新邻接列表
                if diffOne(s, bank[j]):
                    adj[i].append(j)
                    adj[j].append(i)
        # 如果目标基因不在基因库中，返回-1
        if endIndex == -1:
            return -1

        # 初始化队列，包含所有与起始基因序列只有一个字符不同的基因
        q = [i for i, s in enumerate(bank) if diffOne(start, s)]
        # 使用集合记录已访问的基因
        vis = set(q)
        # 初始化步数
        step = 1
        # 广度优先搜索
        while q:
            # 临时保存当前层的基因
            tmp = q
            # 清空当前队列，为下一层准备
            q = []
            # 遍历当前层的基因
            for cur in tmp:
                # 如果当前基因是目标基因，返回步数
                if cur == endIndex:
                    return step
                # 遍历当前基因的相邻基因
                for nxt in adj[cur]:
                    # 如果相邻基因未被访问过，添加到队列和访问集合中
                    if nxt not in vis:
                        vis.add(nxt)
                        q.append(nxt)
            # 增加步数
            step += 1
        # 如果队列为空且未找到目标基因，返回-1
        return -1

代码语法不熟悉的地方：
1.sum(x != y for x, y in zip(s, t)) == 1 ？
①zip(s, t)：

zip 函数将两个字符串 s 和 t 中的字符按位置配对，形成一个由元组组成的迭代器。

例如，如果 s = "AACCGGTT" 和 t = "AACCGGTA"，那么 zip(s, t) 将会生成一个迭代器：

[('A', 'A'), ('A', 'A'), ('C', 'C'), ('C', 'C'), ('G', 'G'), ('G', 'G'), ('T', 'T'), ('T', 'A')]

②生成器表达式 x != y for x, y in zip(s, t)：

这个生成器表达式遍历 zip(s, t) 生成的每个 (x, y) 元组，并检查 x 是否不等于 y。
它返回一个布尔值的迭代器，其中每个布尔值表示两个字符是否不同。
例如，对于上述的字符串对，这个生成器表达式的结果将是：
```
[False, False, False, False, False, False, False, True]
```
这里的 True 表示 s 和 t 在最后一对字符中不同。
③sum(x != y for x, y in zip(s, t))：
sum 函数对生成器表达式返回的布尔值进行求和。
True 在 Python 中被视为 1，False 被视为 0。
因此，这个求和操作实际上是在计算 s 和 t 中字符不同的总数。
继续上述例子，sum([False, False, False, False, False, False, False, True]) 的结果是 1，因为 s 和 t 只有一个字符不同。
④== 1：
最后，比较 sum 的结果是否等于 1。
如果结果是 1，说明 s 和 t 只有一个字符不同；如果结果不是 1，则说明它们的不同字符数不为 1。
⑤总结
sum(x != y for x, y in zip(s, t)) == 1 的意思是：
比较两个字符串 s 和 t 是否仅有一个字符不同。
它通过生成字符串中每一对字符是否相同的布尔值，然后计算这些布尔值为 True 的数量（即字符不同的数量），最终检查这个数量是否正好为 1。
这样可以快速判断两个字符串是否只有一个字符不同，在某些算法中（例如变异路径计算）非常有用。

用时和内存

（很神奇，优化后时间复杂度还不如优化前。。）

时空复杂度

示例详解：
输入:

start = "AACCGGTT"
end = "AAACGGTA"
bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
输出: 2
代码运行过程模拟：
构建邻接列表如下：
adj[0] = [1, 2]
adj[1] = [0]
adj[2] = [0]
BFS 过程：
初始化：
- 队列 q：[0]（与 start 只有一个字符不同的基因 "AACCGGTA" 的索引）。
- 访问集合 vis：{0}。
- 步数 step = 1。
第一轮：
- tmp = q，tmp = [0]。
- 清空队列 q。
- 遍历 tmp：
  - 对于 cur = 0（基因 "AACCGGTA"）：
    - 检查它的相邻基因：
      - 相邻基因 1（"AACCGCTA"）：
        
        还未访问，将其添加到队列 q 并标记为已访问。
      - 相邻基因 2（"AAACGGTA"）：
        
        还未访问，将其添加到队列 q 并标记为已访问。
- 更新队列 q：[1, 2]。
- 步数：step += 1，步数变为 2。
第二轮：
- tmp = q，tmp = [1, 2]。
- 清空队列 q。
- 遍历 tmp：
  - 对于 cur = 1（基因 "AACCGCTA"）：
    - 检查它的相邻基因：
      - 相邻基因 0（"AACCGGTA"）：
        
        已经访问过，不做处理。
  - 对于 cur = 2（基因 "AAACGGTA"）：
    - 发现 cur 与目标基因 end 相同（cur == endIndex），因此直接返回当前步数 2。

最后编辑于：2024.08.10 14:37:59

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,590评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 86,808评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,151评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,779评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,773评论 5赞 367
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,656评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,022评论 3赞 398
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,678评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 41,038评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,659评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,756评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,411评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,005评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,973评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,203评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,053评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,495评论 2赞 343

51题433题

第一题、51.N皇后（困难）

第二题、433.最小基因变化（中等）

推荐阅读更多精彩内容