dw静态个人简历网站模板下载,做金融平台网站需要多少钱,网站建设协议书 印花税,深圳企业网站建设制作设计公司今日份题目#xff1a;
基因序列可以表示为一条由 8 个字符组成的字符串#xff0c;其中每个字符都是 A、C、G 和 T 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如#xff0c;
基因序列可以表示为一条由 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 8 end.length 8 0 bank.length 10 bank[i].length 8 start、end 和 bank[i] 仅由字符 [A, C, G, T] 组成
题目思路
这道题广度优先的思路有点暴力搜索的意思就是遍历所有的可能组合然后找到最后的结果组合找不到就返回-1找得到就返回步数。具体来说我们需要遍历所有8个位置的所有4个字母的组合如果某个组合未被遍历过并且能在字典中找到那么就放入bfs队列中否则跳过每层bfs结束step加一直到找到最后结果。
注意unodered_set插入使用emplace使用visited集合标记遍历过的组合第一个找到的就是最小的step因为一起加加所以第一个满足时就是结果了。
代码
class Solution
{
public: int minMutation(string start, string end, vectorstring bank) {unordered_setstring dict; //存放字典信息unordered_setstring visited;char chara[4]{A,C,G,T}; for(auto b:bank) {dict.emplace(b);}if(startend) //剪枝未变化{return 0;}if(!dict.count(end)) //如果变换后的组合不在字典中那么无法实现变化返回-1{return -1;}queuestring p;p.push(start);visited.emplace(start);int step1;//bfswhile(!p.empty()) {int np.size();for(int i0;in;i) {string currp.front();p.pop();//遍历每位的所有可能的字母情况for(int j0;j8;j) //遍历序列的8个位置{for(int k0;k4;k) //遍历4种字母{if(chara[k]!curr[j]) //当前不是这个字母{string nextcurr;next[j]chara[k];//在当前组合的基础上将这个位置的字母改为当前字母if(!visited.count(next)dict.count(next)) {//可以加入的条件在字典中能找到并且没有被遍历过if(nextend) //找到最后的了返回步数{return step;}//还未找到最后p.push(next);visited.emplace(next);}}}}}step;//每完成一层就加一与上个题一样}return -1;}
};提交结果 欢迎大家在评论区讨论如有不懂的部分欢迎在评论区留言
更新不易宝子们点个赞支持下谢谢 每天一道leetcode大家一起在评论区打卡呀
