[C++] Clean Code - 2 Solution - DFS & BFS


  • 6

    DFS

    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
            vector<int> killed;
            map<int, set<int>> children;
            for (int i = 0; i < pid.size(); i++) {
                children[ppid[i]].insert(pid[i]);
            }
            killAll(kill, children, killed);
            return killed;
        }
    
    private:
        void killAll(int pid, map<int, set<int>>& children, vector<int>& killed) {
            killed.push_back(pid);
            for (int child : children[pid]) {
                killAll(child, children, killed);
            }
        }
    };
    

    BFS

    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
            vector<int> killed;
            map<int, set<int>> children;
            for (int i = 0; i < pid.size(); i++) {
                children[ppid[i]].insert(pid[i]);
            }
    
            queue<int> q;
            q.push(kill);
            while (!q.empty()) {
                int p = q.front(); q.pop();
                killed.push_back(p);
                for (int child : children[p]) {
                    q.push(child);
                }
            }
    
            return killed;
        }
    };
    

  • 0
    Z

    Here is my C++ code. Same idea, but using unordered_map and vector to improve performance.

    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
            unordered_map<int, vector<int>> pros;
            for (int i = 0; i < pid.size(); ++i) 
                pros[ppid[i]].push_back(pid[i]);
            vector<int> ans;
            queue<int> q;
            q.push(kill);
            while (!q.empty()) {
                ans.push_back(q.front());
                q.pop();
                for (int m:pros[ans.back()])
                    q.push(m);
            }
            return ans;
        }
    

  • 0
    S

    Same idea here (162ms). I think use vector to perform queue can improve the solution. Because vector can insert another vector in one time. Therefore, we don't have to go through the every child process to push them into the queue.

    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
            unordered_map<int, vector<int>> hm;
            for ( int i = 0; i < pid.size(); i++ ) {
                hm[ppid[i]].push_back(pid[i]);
            }
            
            if ( hm[0].back() == kill ) return pid;
            vector<int> ret(1,kill);
            
            vector<int> Q; // perform as queue
            Q.push_back(kill);
            while( !Q.empty() ) {
                int key = Q.front();
                Q.erase(Q.begin());
                if ( hm.find(key) != hm.end() ) {
                    Q.insert(Q.end(), hm[key].begin(), hm[key].end());
                    ret.insert(ret.end(), hm[key].begin(), hm[key].end());
                }
            }
            return ret;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.