当前位置：首页 > article >正文

【优选算法】（第四十二篇）

article 2025/1/22 13:01:58

最⼩基因变化（medium）

题目解析

讲解算法原理

编写代码

单词接⻰（hard）

题目解析

讲解算法原理

编写代码

最⼩基因变化（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

基因序列可以表⽰为⼀条由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的最短路问题」。
因此，从起始的字符串开始，来⼀次 bfs 即可。

编写代码

c++算法代码：

class Solution
{
public:
 int minMutation(string startGene, string endGene, vector<string>& bank) 
 {
 unordered_set<string> vis; // ⽤来标记已经搜索过的状态
 unordered_set<string> hash(bank.begin(), bank.end()); // 存储基因库⾥⾯的字符串
 string change = "ACGT";
 if(startGene == endGene) return 0;
 if(!hash.count(endGene)) return -1;
 queue<string> q;
 q.push(startGene);
 vis.insert(startGene);
 int ret = 0;
 while(q.size())
 {
 ret++;
 int sz = q.size();
 while(sz--)
 {
 string t = q.front();
 q.pop();
 for(int i = 0; i < 8; i++)
 {
 string tmp = t; // 细节问题
 for(int j = 0; j < 4; j++)
 {
 tmp[i] = change[j];
 if(hash.count(tmp) && !vis.count(tmp))
 {
 if(tmp == endGene) return ret;
 q.push(tmp);
 vis.insert(tmp);
 }
 }
 }
 }
 }
 return -1;
 }
};

java算法代码：

class Solution
{
 public int minMutation(String startGene, String endGene, String[] bank) 
 {
 Set<String> vis = new HashSet<>(); // ⽤来标记已经搜索过的状态
 Set<String> hash = new HashSet<>(); // ⽤来统计基因库⾥⾯的字符串
 for(String s : bank) hash.add(s);
 char[] change = {'A', 'C', 'G', 'T'};
 if(startGene.equals(endGene)) return 0;
 if(!hash.contains(endGene)) return -1;
 Queue<String> q = new LinkedList<>();
 q.add(startGene);
 vis.add(startGene);
 int step = 0;
 while(!q.isEmpty())
 {
 step++;
 int sz = q.size();
 while(sz-- != 0)
 {
 String t = q.poll();
 for(int i = 0; i < 8; i++)
 {
 char[] tmp = t.toCharArray();
 for(int j = 0; j < 4; j++)
 {
 tmp[i] = change[j];
 String next = new String(tmp);
 if(hash.contains(next) && !vis.contains(next))
 {
 if(next.equals(endGene)) return step;
 q.add(next);
 vis.add(next);
 }
 }
 }
 }
 }
 return -1;
 }
}

单词接⻰（hard）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

字典 wordList 中从单词 beginWord 和 endWord 的转换序列是⼀个按下述规格形成的序列 beginWord -> s(1) -> s(2) -> ... -> s(k) ：
• 每⼀对相邻的单词只差⼀个字⺟。
• 对于 1 <= i <= k 时，每个 s(i) 都在 wordList 中。注意， beginWord 不需要
在 wordList 中。
• s(k) == endWord
给你两个单词 beginWord 和 endWord 和⼀个字典 wordList ，返回从 beginWord 到endWord 的最短转换序列中的单词数⽬。如果不存在这样的转换序列，返回 0 。

⽰例1：
输⼊：beginWord="hit",endWord="cog",wordList=["hot","dot","dog","lot","log","cog"]输出：5
解释：⼀个最短转换序列是"hit"->"hot"->"dot"->"dog"->"cog",返回它的⻓度5。⽰例2：
输⼊：beginWord="hit",endWord="cog",wordList=["hot","dot","dog","lot","log"]输出：0
解释：endWord"cog"不在字典中，所以⽆法进⾏转换。

提⽰：
◦ 1 <= beginWord.length <= 10
◦ endWord.length == beginWord.length
◦ 1 <= wordList.length <= 5000
◦ wordList[i].length == beginWord.length
◦ beginWord 、 endWord 和 wordList[i] 由⼩写英⽂字⺟组成
◦ beginWord != endWord
◦ wordList 中的所有字符串互不相同

讲解算法原理

解法：
算法思路：
跟上题⼀样~

编写代码

c++算法代码：

class Solution
{
public:
 int ladderLength(string beginWord, string endWord, vector<string>& 
wordList) 
 {
 unordered_set<string> hash(wordList.begin(), wordList.end());
 unordered_set<string> vis; // 标记已经搜索过的单词
 if(!hash.count(endWord)) return 0;
 queue<string> q;
 q.push(beginWord);
 vis.insert(beginWord);
 int ret = 1;
 while(q.size())
 {
 ret++;
 int sz = q.size();
 while(sz--)
 {
 string t = q.front();
 q.pop();
 for(int i = 0; i < t.size(); i++)
 {
 string tmp = t;
 for(char ch = 'a'; ch <= 'z'; ch++)
 {
 tmp[i] = ch;
 if( hash.count(tmp) && !vis.count(tmp))
 {
 if(tmp == endWord) return ret;
 q.push(tmp);
 vis.insert(tmp);
 }
 }
 }
 }
 }
 return 0;
 }
};

java算法代码：

class Solution
{
 public int ladderLength(String beginWord, String endWord, List<String> 
wordList) 
 {
 Set<String> hash = new HashSet<>();
 for(String s : wordList) hash.add(s);
 Set<String> vis = new HashSet<>(); // 标记已经搜索过的单词
 if(!hash.contains(endWord)) return 0;
 Queue<String> q = new LinkedList<>();
 q.add(beginWord);
 vis.add(beginWord);
 int ret = 1;
 while(!q.isEmpty())
 {
 ret++;
 int sz = q.size();
 while(sz-- != 0)
 {
 String t = q.poll();
 for(int i = 0; i < t.length(); i++)
 {
 char[] tmp = t.toCharArray();
 for(char ch = 'a'; ch <= 'z'; ch++)
 {
 tmp[i] = ch;
 String next = new String(tmp);
 if(hash.contains(next) && !vis.contains(next))
 {
 if(next.equals(endWord)) return ret;
 q.add(next);
 vis.add(next);
 }
 }
 }
 }
 }
 return 0;
 }
}

查看全文

http://www.kler.cn/a/350344.html