当前位置：首页 > news >正文

433. 最小基因变化（Queue使用ArrayList和LinkedList进行声明）

news 2025/8/7 17:15:58

这道题可以看成一个24叉树。

因为基因序列长度固定为8，且每个位置的字母固定是AGCT，可以选择改变的只有3个字母，所以一次最多24种情况。

然后检查变化后的结果是否存在bank中（使用hashSet来存储），同时设置一个visited集合来检查是否访问过。

class Solution {public int minMutation(String startGene, String endGene, String[] bank) {if (startGene.equals(endGene))return 0;char[] keys = { 'A', 'G', 'C', 'T' };Set<String> cnt = new HashSet<>();Set<String> visited = new HashSet<>();for (String str : bank) {cnt.add(str);}if (!cnt.contains(endGene))return -1;Queue<String> q = new ArrayDeque<>();q.offer(startGene);visited.add(startGene);int step = 1;while (!q.isEmpty()) {int size = q.size();for (int i = 0; i < size; ++i) {String curr = q.poll();for (int u = 0; u < 8; ++u) {for (int v = 0; v < 4; ++v) {if (keys[v] != curr.charAt(u)) {StringBuffer sb = new StringBuffer(curr);sb.setCharAt(u, keys[v]);String next = sb.toString();if (!visited.contains(next) && cnt.contains(next)) {if (next.equals(endGene))return step;visited.add(next);q.offer(next);}}}}}++step;}return -1;}
}

拓展：Queue使用ArrayList和LinkedList进行声明的区别
在Java中，Queue可以使用ArrayList和LinkedList进行声明。这两种数据结构在实现Queue时有一些区别。

使用ArrayList声明Queue的区别：

底层数据结构：
- ArrayList基于动态数组实现，它可以动态增长和缩小。
- 插入和删除元素可能涉及重新分配内存和数据复制。
适用场景：
- 当需要随机访问队列中的元素时，ArrayList是更好的选择，因为它支持通过索引直接访问元素。
- 如果需要频繁对队列进行随机访问、而且对队列的修改操作相对较少时，可以考虑使用ArrayList实现Queue。

使用LinkedList声明Queue的区别：

底层数据结构：
- LinkedList基于双向链表实现，每个元素都指向前一个和后一个元素。
- 插入和删除元素的时间复杂度为O(1)，因为只需要调整指针而不需要大量数据的搬移。
适用场景：
- 当需要频繁对队列进行插入、删除操作时，LinkedList是更好的选择，因为它的插入和删除操作效率更高。
- 如果队列的操作主要是在两端进行（即头部和尾部），比如经常需要在队列头部和尾部进行插入、删除操作，可以考虑使用LinkedList实现Queue。