JAVA solution with explanation


  • 0
    T
    public class Solution {
        //Use a hashMap to store <PPID, PID>. But this is not One to One pair because One parent could has a lot successors.
        /*In order to eliminate the collision, we use ArrayList to store a sequence of PIDs.
        * Then use DFS to find all the processes which should be killed.
        * Use an Stack to implement DFS.
        */
        public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
            //create our map.
            for(int i = 0; i < pid.size(); i++){
                if (map.containsKey(ppid.get(i) ) ){
                    ArrayList<Integer> temp = map.get(ppid.get(i) );
                    temp.add(pid.get(i) );
                }
                else{
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(pid.get(i));
                    map.put(ppid.get(i), temp);
                }
            }
            //This stack contains the pids which are going to be killed.
            Stack<Integer> willKill = new Stack<Integer>();
            willKill.push(kill);
            List<Integer> output = new ArrayList<Integer>();
            while(!willKill.isEmpty() ){
                int j = willKill.pop();
                if(map.containsKey(j) ){
                    ArrayList<Integer> temp = map.get(j);//find this process' children.
                    for(int i : temp){
                        willKill.push(i);
                    }
                }
                output.add(j);
            }
            return output;
            
        }
    }
    

Log in to reply
 

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