LeetCode 433. 最小基因变化

思路

1、差异比较bank中的序列和start序列的差距，将每一位的差距记录到二进制数的位上，表示一个序列，统计这个数1的个数，就是差异程度，数字越大差异越大。
2、计算start和end的差异，将start这样0差异的序列加到上面的差异序列数组中。
3、bfs，如果差异程度之差等于1并且差异数位差异位1时，就入队等待bfs。
4、细节，入队的数标记入队，不再能入队；记录每一层的入队数量，一层遍历完，res（结果）加1，如果当前的差异为0，说明bfs到start。

start = “AACCGGTT”, end = “AACCGGTA”, bank = [“AACCGGTA”]

start:AACCGGTT
end: AACCGGTA
bit: 00000001
转化为二进制数为1，差异程度为1（因为只有一个1）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
public:
    struct Gap{
        int num; //差距序列
        int n; //差距程度，越大差越多
    };
    int getBits_one(int x){
        int res=0;
        while(x){
            if(x&1)
                res++;
            x>>=1;
        }
        return res;
    }
    int calGap(string origin,string after){
        int n=origin.length();
        int gap=0;
        for(int i=0;i<n;i++)
            if(origin[i]!=after[i])
                gap |= 1<<(n-i-1);
        return gap;
    }
    int bfs(Gap gap,const vector<Gap>& banks){
        vector<bool> isPush(512);
        bool flag=false;
        int n=banks.size();
        queue<Gap> p;
        p.push(gap);
        isPush[gap.num]=true;
        
        int res=-1;
        int thePush=1;
        int thePop=0;
        int cnt=0;
        while(!p.empty()&&!flag){
            Gap k=p.front();
            p.pop();
            thePop++;
            for(int i=0;i<n;i++){
                Gap t=banks[i];
                if(!isPush[t.num]&&abs(k.n-t.n)==1&&getBits_one((k.num|t.num)-(k.num&t.num))==1){
                    isPush[t.num]=true;
                    p.push(t);
                    cnt++;
                }
            }
            if(thePop==thePush){
                thePush=cnt;
                cnt=0;
                thePop=0;
                res++;
            }
            if(k.num==0) break;
        }
        return res;
    }
    int minMutation(string start, string end, vector<string>& bank) {
        int n=bank.size();
        vector<Gap> banks(n+1);
        for(int i=0;i<n;i++){
            string s=bank[i];
            banks[i].num=calGap(start,s);
            banks[i].n=getBits_one(banks[i].num);
        }
        banks[n]=Gap{0,0};
        Gap p;
        p.num=calGap(start,end);
        p.n=getBits_one(p.num);
        bool isInBank=false;
        for(int i=0;i<n+1;i++){
            if(p.num==banks[i].num){
                isInBank=true;
                break;
            }
        }
        if(!isInBank) return -1;
        int step=bfs(p,banks);
        return step==0?-1:step;
    }
};

参考

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