関小君刷题记

题目大意：

杀死进程

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.

示例1:

输入: 
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
输出: [5,10]
解释: 
           3
         /   \
        1     5
             /
            10
Kill 5 will also kill 10.

注意:

1. The given kill id is guaranteed to be one of the given PIDs.
2. n >= 1.

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=582

解题思路分析

这是一道树形结构的题目，按照题目给出的两个数组，我们先建立出树形结构，利用一个HashMap，key为父节点id，value是该父节点下所有子节点。

结构建立好之后，dfs遍历kill节点下的所有子节点，kill与这些子节点都是会被杀死的进程。

实现代码：

List<Integer> res=new ArrayList(); // 返回结果
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
    Map<Integer, List<Integer>> map = new HashMap<>(); // 树形结构
    // 建立树形结构，key为父节点，value为父节点下所有子节点集合
    for(int i=0;i<ppid.size();i++){
        int p=ppid.get(i);
        int c=pid.get(i);
        List<Integer> list=map.getOrDefault(p,new ArrayList<>());
        list.add(c);
        map.put(p,list);
    }
    // 将kill加入返回结果
    res.add(kill);
    // dfs查找kill下所有子节点
    dfs(map, kill);
    return res;
}

void dfs(Map<Integer, List<Integer>> map, int id){
    if(!map.containsKey(id)) return;
    List<Integer> list = map.get(id);
    for(int pid : list){
        res.add(pid);
        dfs(map, pid);
    }
}

本题解法执行时间为33ms。

Runtime: 33 ms, faster than 61.66% of Java online submissions for Kill Process.

Memory Usage: 54 MB, less than 28.57% of Java online submissions for Kill Process.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-582-kill-process-解题思路分析/