Java Solution, HashMap


  • 5
    public class Solution {
        public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            if (kill == 0) return pid;
            
            int n = pid.size();
            Map<Integer, Set<Integer>> tree = new HashMap<>();
            for (int i = 0; i < n; i++) {
                tree.put(pid.get(i), new HashSet<Integer>());
            }
            for (int i = 0; i < n; i++) {
                if (tree.containsKey(ppid.get(i))) {
                    Set<Integer> children = tree.get(ppid.get(i));
                    children.add(pid.get(i));
                    tree.put(ppid.get(i), children);
                }
            }
            
            List<Integer> result = new ArrayList<>();
            traverse(tree, result, kill);
            
            return result;
        }
        
        private void traverse(Map<Integer, Set<Integer>> tree, List<Integer> result, int pid) {
            result.add(pid);
            
            Set<Integer> children = tree.get(pid);
            for (Integer child : children) {
                traverse(tree, result, child);
            }
        }
    }
    

  • 0
    G

    Slightly different but same idea

    public class Solution {
        
        Map<Integer, List<Integer>> lookup = new HashMap<>();
        
        public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            for(int i=0; i<ppid.size(); i++) {
                Integer p = ppid.get(i);
                List<Integer> children = lookup.get(p);
                if(children == null) {
                    children = new ArrayList<>();
                    lookup.put(p, children);
                }
                children.add(pid.get(i));
            }
            List<Integer> tbk = addChild(kill);
            tbk.add(kill);
            return tbk;
        }
        
        private List<Integer> addChild(int process) {
            List<Integer> child = new ArrayList<>();
            List<Integer> tbk = lookup.get(process); //to be killed
            
            if(tbk == null) return child;
            
            child.addAll(tbk);
            for(Integer i : tbk) child.addAll(addChild(i)); 
           
            return child;
            
        }
    }
    

  • 0
    N
    This post is deleted!

Log in to reply
 

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