Leetcode 582. Kill Process

Leetcode 582. Kill Process

　　好久没刷题，今天来一道比较简单的题目，如果此题作为一道面试题，可以延伸出树的遍历，栈和队列，hashmap，treemap等，还是比较能考验基础的面试题。 再解释下，贴英文原文不是为了凑字数，而是希望有人搜原文的时候我博客能被索引到，也算是一种简单的SEO。 Given n processes, each process has a unique PID (process id) and its PPID (parent process id).

Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.

We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.

Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.

　　大概说下题意，给出n个进程，每个进程都有一个唯一的进程号，每个进程只有一个父进程，但一个进程可能有多个子进程，我们用pid和ppid两个list来保存所有的进程和其父进程。每当杀死一个进程的时候，其全部子进程都必须被杀死，现在给出一个进程pid，让你找出杀死它时候必须杀死哪些进程？以list返回。 　　我开始尝试了一把直接递归删除子进程的方式，递归的方式简单易懂，仅仅几行。

public class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        ans.add(kill);
        for (int i = 0; i < ppid.size(); i++) {
            if (ppid.get(i) == kill) {
                ans.addAll(killProcess(pid, ppid, pid.get(i)));
            }
        }
        return ans;
    }
}

　　代码中我很暴力的通过遍历的方式来查找子进程，然后再递归删除，提交后毫无疑问TLE了。认真思考下，这个问题的关键点在于如何高效的找出每个进程的所有子进程。本来想把父子进程做成K-V对放到map里，结果发现jdk并没有提供multimap，不过这也难不到我，我把V做成子进程list放进去，再通过递归的方式实现kill，最终代码见文末。 　　本题最重要的其实是构建一个高效的查找数据结构，剩下的就简单，我代码最终执行耗时83ms，超越了70%的人。其实这里我用到了递归，比较耗时，如果改成非递归的方式，性能还能优化不少。 　　其实说白了，这到底就是遍历多叉树，所以存在深度优先遍历(DFS)和广度优先遍历(BFS)两种方式，我直接用递归写其实是深度优先遍历，有兴趣可以尝试下非递归的DFS和BFS，其实很简单。

    public List<Integer> killall(HashMap<Integer, ArrayList<Integer>> map, int kill) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        ans.add(kill);
        ArrayList<Integer> list = map.get(kill);
        if (null == list)
            return ans;
        for (int i = 0; i < list.size(); i++) {
            ans.addAll(killall(map, list.get(i)));
        }
        return ans;
    }
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        ans.add(kill);
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        for (int i = 0; i < ppid.size(); i++) {
            if (!map.containsKey(ppid.get(i))) {
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(pid.get(i));
                map.put(ppid.get(i), list);
            }
            else {
                map.get(ppid.get(i)).add(pid.get(i));
            }
        }
        return killall(map, kill);
    }
}