wordpress木马乐主题,五行seo博客,如何修改WordPress备份中的网址,药店网站模板基因序列可以表示为一条由 8 个字符组成的字符串#xff0c;其中每个字符都是 A、C、G 和 T 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
例如#xff0c;AACCGGTT --…基因序列可以表示为一条由 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 8end.length 80 bank.length 10bank[i].length 8start、end 和 bank[i] 仅由字符 [A, C, G, T] 组成
解题思路
整体思想是广度优先搜索由于原序列变化一个字符不一定是针对endGene精确修改的可能把对的字符暂时修改为了符合基因库里面的序列再修改成符合endGene的序列所以每个出队的序列要接受24次修改为什么不是32次因为相同字符保持不变即可用到map集合记录每种序列的变化次数在修改序列时要不断判断该序列是否为endGene最先到达endGene为最少步骤的序列 是则直接返回map中的值加一若map为空则返回1否则继续从队列取若出队完还没修改出最终序列说明基因库不存在某个序列导致某一步截止了则返回-1existBank用于判断当前序列是否存在于基因库isPoll用于判断是否已经出队过一次
public int minMutation(String startGene, String endGene, String[] bank) {SetString existBanknew HashSetString();SetString isPollnew HashSetString();MapString,IntegerminStepnew HashMapString, Integer();for (int i 0; i bank.length ; i)existBank.add(bank[i]);Queuechar[]queuenew LinkedListchar[]();char[] start startGene.toCharArray();char[] end endGene.toCharArray();queue.offer(start);char cs[]new char[]{A,C,G,T};while (!queue.isEmpty()){char[] current queue.poll();String currentStrString.valueOf(current);if(!isPoll.contains(currentStr)){isPoll.add(currentStr);}else{continue;}if(currentStr.equals(String.valueOf(end))){return minStep.get(currentStr);}for (int i 0; i startGene.length();i)for(int j0;j4;j) {char[] tempChar Arrays.copyOf(current, current.length);if(tempChar[i]cs[j])continue;tempChar[i] cs[j];String tempStrString.valueOf(tempChar);if(tempStr.equals(currentStr))continue;if(existBank.contains(tempStr)){queue.offer(tempChar);Integer minStepValueminStep.get(currentStr);if(minStepValue!null){minStep.put(tempStr,minStep.get(currentStr)1);if(tempStr.equals(String.valueOf(end))){return minStep.get(currentStr)1;}}else{minStep.put(tempStr,1);if(tempStr.equals(String.valueOf(end))){return 1;}}}}}return -1;}