LeetCode题练习与总结：最小基因变化--433
一、题目描述
基因序列可以表示为一条由 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 == 8end.length == 80 <= bank.length <= 10bank[i].length == 8start、end和bank[i]仅由字符['A', 'C', 'G', 'T']组成
二、解题思路
这个问题可以看作是一个无向图的最短路径问题，其中每个基因序列是一个节点，如果两个基因序列之间只有一个字符不同，那么这两个节点之间有一条边。我们的目标是找到从起点基因序列到终点基因序列的最短路径。
以下是解题步骤：
- 创建一个集合（或使用布尔数组）来记录基因库中哪些基因序列已经被使用过，以避免重复访问。
- 使用一个队列来进行广度优先搜索（BFS）。初始时，将起点基因序列放入队列中。
- 在队列不为空的情况下，进行以下操作：
- 从队列中取出一个基因序列。
- 如果这个基因序列与终点基因序列相同，返回当前的变化次数。
- 否则，遍历基因库中的每个基因序列，检查是否只有一个字符不同，并且该基因序列没有被使用过。如果是，将其加入队列，并标记为已使用。
- 如果队列为空还没有找到终点基因序列，返回 -1。
三、具体代码
import java.util.*;
public class Solution {
public int minMutation(String start, String end, String[] bank) {
// 使用集合来记录已经使用过的基因序列
Set<String> visited = new HashSet<>();
// 使用队列进行广度优先搜索
Queue<String> queue = new LinkedList<>();
// 初始化队列和访问集合
queue.offer(start);
visited.add(start);
// 变化次数
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
// 遍历当前层的所有节点
for (int i = 0; i < size; i++) {
String current = queue.poll();
// 如果当前节点与终点相同，返回变化次数
if (current.equals(end)) {
return steps;
}
// 遍历基因库中的每个基因序列
for (String gene : bank) {
// 如果基因序列没有被使用过，并且只有一个字符不同
if (!visited.contains(gene) && isMutation(current, gene)) {
queue.offer(gene);
visited.add(gene);
}
}
}
// 增加变化次数
steps++;
}
// 如果无法完成变化，返回 -1
return -1;
}
// 检查两个基因序列是否只有一个字符不同
private boolean isMutation(String start, String end) {
int diff = 0;
for (int i = 0; i < start.length(); i++) {
if (start.charAt(i) != end.charAt(i)) {
diff++;
if (diff > 1) {
return false;
}
}
}
return diff == 1;
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
-
初始化阶段，将起始基因序列
start加入队列，这一步的时间复杂度是 O(1)。 -
在广度优先搜索（BFS）过程中，我们遍历队列中的每个元素，并对每个元素检查基因库中的所有基因序列。假设基因库的大小为 n，那么在每层BFS中，我们需要检查 n 个基因序列，并且对于每个基因序列，我们执行
isMutation方法来检查是否只有一个字符不同，isMutation方法的时间复杂度是 O(8)，因为每个基因序列的长度是固定的 8。 -
BFS 可能会遍历所有 n 个基因序列，因为最坏情况下每个基因序列都可能被加入到队列中。因此，队列的大小最多可能是 n。
综合以上分析，总的时间复杂度是 O(n^2 * 8)，可以简化为 O(n^2)，因为 8 是一个常数。
2. 空间复杂度
-
visited集合用于存储已经访问过的基因序列，最坏情况下需要存储 n 个基因序列，因此空间复杂度是 O(n)。 -
队列
queue在最坏情况下可能包含所有 n 个基因序列，因此空间复杂度也是 O(n)。
综合以上分析，总的空间复杂度是 O(n) + O(n)，可以简化为 O(n)，因为两个 O(n) 是同阶的。
五、总结知识点
-
面向对象编程（OOP）：
- 类定义（
public class Solution）。 - 方法定义（
public int minMutation(...)和private boolean isMutation(...)）。
- 类定义（
-
数据结构：
- 集合（
Set<String>）：用于存储已经访问过的基因序列，确保不会重复访问。 - 队列（
Queue<String>）：用于实现广度优先搜索（BFS）。
- 集合（
-
算法：
- 广度优先搜索（BFS）：用于在无向图中找到从起点到终点的最短路径。
- 字符串比较：用于判断两个基因序列是否只有一个字符不同。
-
字符串操作：
- 使用
charAt(int index)方法获取字符串中指定位置的字符。 - 使用
equals(Object anObject)方法比较两个字符串是否相等。
- 使用
-
控制结构：
- 循环结构：
for循环用于遍历队列中的元素和字符串中的字符。 - 条件语句：
if语句用于检查条件是否满足，并据此执行不同的操作。
- 循环结构：
-
集合操作：
- 使用
add(E e)方法向集合中添加元素。 - 使用
contains(Object o)方法检查集合中是否包含特定的元素。
- 使用
-
队列操作：
- 使用
offer(E e)方法向队列中添加元素。 - 使用
poll()方法从队列中取出并移除头部元素。 - 使用
size()方法获取队列中的元素数量。
- 使用
-
错误处理：
- 如果无法从起始基因序列变换到目标基因序列，则返回
-1。
- 如果无法从起始基因序列变换到目标基因序列，则返回
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
原文地址：https://blog.csdn.net/weixin_62860386/article/details/144123665
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！