网站开发组,网站背景图片素材,wordpress价格表单,西柏坡旅游网站建设规划书#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ BFS 求解思路 实现代码 运行结果 共勉 题目链接
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 8 end.length 8 0 bank.length 10 bank[i].length 8 start、end 和 bank[i] 仅由字符 [‘A’, ‘C’, ‘G’, ‘T’] 组成 求解思路实现代码运行结果 ⚡ BFS 求解思路
题目要求我们将一个基因序列 A 变化至另一个基因序列 B在变化的过程中需要满足以下条件
序列 A 与 序列 B 之间只有一个字符不同变化字符只能从 ‘A’, ‘C’, ‘G’, ‘T‘中进行选择变换后的序列 B 一定要在字符串数组 bank中。
然后我们通过bfs来尝试所有的可能具体来说就是先从A开始然后判断A中的每一个字符尝试是否可以替换为 ‘A’, ‘C’, ‘G’, ‘T‘也就是替换一次后bank中是否存在如果存在加入到队列中如果不存在继续向后判断。有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
class Solution {public int minMutation(String start, String end, String[] bank) {SetString cnt new HashSetString();SetString visited new HashSetString();char[] keys { A, C, G, T };for (String w : bank) {cnt.add(w);}if (start.equals(end)) {return 0;}if (!cnt.contains(end)) {return -1;}QueueString queue new ArrayDequeString();queue.offer(start);visited.add(start);int step 1;while (!queue.isEmpty()) {int sz queue.size();for (int i 0; i sz; i) {String curr queue.poll();for (int j 0; j curr.length(); j) {for (int k 0; k 4; k) {if (keys[k] ! curr.charAt(j)) {StringBuffer sb new StringBuffer(curr);sb.setCharAt(j, keys[k]);String next sb.toString();if (!visited.contains(next) cnt.contains(next)) {if (next.equals(end)) {return step;}queue.offer(next);visited.add(next);}}}}}step;}return -1;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
