凹凸69堂国产成人精品,免费黄色国产视频,中文字幕AⅤ在线,国产精品igao网网址不卡,在线最新精品激情,亚洲欧美秘无码一区二区小黄鸭天天综合天天添夜夜添狠狠添 ,青娱乐在线播放,久久加勒比

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

今天和大家聊的問(wèn)題叫做?最小基因變化，我們先來(lái)看題面：

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

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

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

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

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

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

注意：

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

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

假定起始基因序列與目標(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

將每個(gè)單詞用hash表存起來(lái)作為一個(gè)字典

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

將start入隊(duì)

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

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;
????}
};