亚洲av免费在线,夜夜爽综合,音影先锋男人资源站,熟女‖熟女色网精品站,色婷婷五月天国产,先锋在线资源福利,国内毛片毛片毛片毛片,人妻无码精品

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?最小基因變化，我們先來看題面：

https://leetcode-cn.com/problems/minimum-genetic-mutation/

一條基因序列由一個帶有8個字符的字符串表示，其中每個字符都屬于 "A", "C", "G", "T"中的任意一個。

假設(shè)我們要調(diào)查一個基因序列的變化。一次基因變化意味著這個基因序列中的一個字符發(fā)生了變化。

例如，基因序列由"AACCGGTT" 變化至 "AACCGGTA" 即發(fā)生了一次基因變化。

與此同時，每一次基因變化的結(jié)果，都需要是一個合法的基因串，即該結(jié)果屬于一個基因庫。

現(xiàn)在給定3個參數(shù) — start, end, bank，分別代表起始基因序列，目標(biāo)基因序列及基因庫，請找出能夠使起始基因序列變化為目標(biāo)基因序列所需的最少變化次數(shù)。如果無法實(shí)現(xiàn)目標(biāo)變化，請返回 -1。

注意：

起始基因序列默認(rèn)是合法的，但是它并不一定會出現(xiàn)在基因庫中。

如果一個起始基因序列需要多次變化，那么它每一次變化之后的基因序列都必須是合法的。

假定起始基因序列與目標(biāo)基因序列是不一樣的。

示例

示例 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

將每個單詞用hash表存起來作為一個字典

判斷end在不在里面，不在則直接返回-1

將start入隊

對每一層的每一個單詞，將它的每一位改成ATCG四個字母，改變之后如果單詞為end就返回bfs樹的層數(shù)，如果不為end就判斷是否在字典里，在字典里就入隊。

class?Solution?{
private:
????unordered_set<string> st;

????bool?find_end(string& str, string& end, queue<string>& que)?{
????????vector<char> next({'A', 'C', 'T', 'G'});

????????for?(int?m = 0; m < str.size(); m++) {
????????????string?new_str = str;
????????????for?(int?n = 0; n < 4; n++) {
????????????????new_str[m] = next[n];
????????????????if?(new_str == end) {
????????????????????return?true;
????????????????}
????????????????if?(st.count(new_str)) {
????????????????????que.push(new_str);
????????????????????st.erase(new_str);
????????????????}
????????????} 
????????}

????????return?false;
????}
public:
????int?minMutation(string?start, string?end, vector<string>& bank)?{
????????st = unordered_set<string>(bank.begin(), bank.end());

????????if?(st.count(end) == 0) {
????????????return?-1;
????????}

????????queue<string> que;
????????que.push(start);
????????int?res = 0;

????????while?(!que.empty()) {
????????????res++;
????????????int?size = que.size();
????????????for?(int?i = 0; i < size; i++) {
????????????????string?str = que.front();
????????????????que.pop();

????????????????if?(find_end(str, end, que)) {
????????????????????return?res;
????????????????} 
????????????}
????????}

????????return?-1;
????}
};