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

本文介绍: 这道题可以看成一个24叉树。因为基因序列长度固定为8，且每个位置的字母固定是AGCT，可以选择改变的只有3个字母，所以一次最多24种情况。然后检查变化后的结果是否存在bank中（使用hashSet来存储），同时设置一个visited集合来检查是否访问过。拓展：Queue使用ArrayList和LinkedList进行声明的区别在Java中，Queue可以使用ArrayList和LinkedList进行声明。这两种数据结构在实现Queue时有一些区别。

这道题可以看成一个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。