14. BFS

应用为层序遍历树、最短路径

14.1 752. 打开转盘锁

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deads;//记录死亡密码
        //初始化死亡密码
        for(string s:deadends){
            deads.insert(s);
        }
        if(deads.count("0000")){
            return -1;//锁死
        }
        int step=0;  //需要的步数
        queue<string> q;
        q.push("0000");
        unordered_set<string> visited;  //记录已经穷举过的密码
        visited.insert("0000");
        while(!q.empty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                string cur=q.front();
                q.pop();
                //死亡密码，跳过
                if(deads.count(cur)){
                    continue;
                }
                //判断是否到达终点
                if(cur==target){
                    return step;
                }
                for(int j=0;j<4;j++){
                    //向上转
                    string up=plusOne(cur,j);
                    if(!visited.count(up)){
                        q.push(up);
                        visited.insert(up);
                    }                    
                    //向下转                    
                    string down=minusOne(cur,j);
                    if(!visited.count(down)){
                        q.push(down);
                        visited.insert(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    string plusOne(string s,int i){
        if(s[i]=='9'){
            s[i]='0';
        }else{
            s[i]+=1;
        }
        return s;
    }
    string minusOne(string s,int i){
        if(s[i]=='0'){
            s[i]='9';
        }else{
            s[i]-=1;
        }
        return s;
    }
};

//双向BFS
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deads;//记录死亡密码
        //初始化死亡密码
        for(string s:deadends){
            deads.insert(s);
        }
        if(deads.count("0000")){
            return -1;//锁死
        }
        int step=0;  //需要的步数
        unordered_set<string> q1,q2;
        q1.insert("0000");
        q2.insert(target);
        unordered_set<string> visited;  //记录已经穷举过的密码
        visited.insert("0000");
        while(!q1.empty()&&!q2.empty()){
            //哈希表在遍历过程中不能修改，用temp存储
            unordered_set<string> temp;
            for(string cur:q1){
                //判断是否为死亡密码
                if(deads.count(cur)){
                    continue;
                }
                //判断是否到达终点
                if(q2.count(cur)){
                    return step;
                }
                visited.insert(cur);
                //将一个节点的未遍历相邻节点加入集合
                for(int i=0;i<4;i++){
                    string up=plusOne(cur,i);
                    if(!visited.count(up)){
                        temp.insert(up);
                    }
                    string down=minusOne(cur,i);
                    if(!visited.count(down)){
                        temp.insert(down);
                    }
                }
            }
            step++;
            //temp相当于q1
            q1=q2;
            //交换q1，q2，下一轮while就是扩散q2
            q2=temp;
        }
        return -1;
    }
    string plusOne(string s,int i){
        if(s[i]=='9'){
            s[i]='0';
        }else{
            s[i]+=1;
        }
        return s;
    }
    string minusOne(string s,int i){
        if(s[i]=='0'){
            s[i]='9';
        }else{
            s[i]-=1;
        }
        return s;
    }
};

14.2 210. 课程表 II

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indgree(numCourses);
        //统计入度
        for(auto p:prerequisites){
            int from=p[1],to=p[0];
            graph[from].push_back(to);
            indgree[to]++;
        }
        //根据入度将节点加入队列，入度为0加入
        queue<int> q;
        for(int i=0;i<numCourses;i++){
            if(indgree[i]==0){
                q.push(i);
            }
        }
        int count=0;   //记录遍历节点的索引
        vector<int> result(numCourses);  //记录排序结果
        while(!q.empty()){
            int cur=q.front();
            q.pop();
            //弹出节点的顺序就是拓扑排序顺序
            result[count]=cur;
            count++;
            for(int g:graph[cur]){
                //入度-1，为0加入队列
                indgree[g]--;
                if(indgree[g]==0){
                    q.push(g);
                }
            }
        }
        if(count!=numCourses){
            return {};
        }
        return result;
    }
};