广州网站制作培训,关键词推广价格,超大型网站建设,做国际网站有用吗Leetcode - 433:最小基因变化
题目#xff1a;
基因序列可以表示为一条由 8 个字符组成的字符串#xff0c;其中每个字符都是 A、C、G 和 T 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化…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
笔记
这道题是真抽象对字符串进行bfs这里的思路是直接对字符串去处理不要讲单个字符单独处理。首先建立一个处理队列将start加入其中此时队列中的元素表示未处理的元素接下来记录当前层的大小遍历当前层的元素只有start一个接着对字符串进行处理这里我们创建一个数组来存储字符可变化的样子也就是方向数组从当前处理的字符串的头开始向后遍历一一替换当前遍历到的位置如果替换后的字符串可以在bank中找到并且没有被访问过我们就将其加入que的第二层在遍历完当前层元素后step代表变换元素的次数。
注意
1当我们向队列加入一个元素后立即将其标记为已访问。
2将vector类型的bank数组改为set数组更好处理
在一个set数组中查找元素是否存在set.count(目标
class Solution {
public:int minMutation(string startGene, string endGene, vectorstring bank) {unordered_setstring visited;unordered_setstring bank_set(bank.begin(), bank.end());char keys[4] {A, C, G, T};int step 0;queuestring que;que.push(startGene);visited.insert(startGene);while(!que.empty()){int size que.size();for(int i 0; i size; i){string cur que.front();que.pop();if(cur endGene){return step;}for(int j 0; j cur.size(); j){for(int k 0; k 4; k){string next cur;next[j] keys[k];if(bank_set.count(next) !visited.count(next)){que.push(next);visited.insert(next);}}}}step;}return -1;}
};
