HelloKenLee

Leetcode 582. Kill Process 解题报告

Posted on By KenLee

题目信息

题目: 582. Kill Process
难度: Medium
正确率: 46.4%
问题描述:

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.

Input: 
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation: 
           3
         /   \
        1     5
             /
            10
Kill 5 will also kill 10.

Note:

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

问题分析

  该问题的意思给你一堆进程的进程编号pid以及他们的父进程的进程编号ppid。而且每一个进程只有一个父进程。在这道题目中,如果一个进程的ppid是0,假装这个进程没有父进程。我们要做的是模拟操作系统kill指令的部分过程。即它给出一个需要被kill掉的pid,我们需要找出这个进程以及其所有子孙进程的pid,用数组返回。

解题思路

  一道模仿操作系统原理的题目,最近非常喜欢做这样子的题目。在Linux中,内核进程idle的pid是0, 我们当然不能把内核kill掉,所以这道题目设计的合情合理。题目不难,一个进程及他的子孙进程组成了一颗进程树(在Linux中可以使用pstree命令查看),我们需要从儿子-父亲关系重构这颗树。

  因此当然可以使用多叉树来存储。我的没有另外写数据结构,我直接采用了一个key-value为pid-childrenPids的哈希表来存储。通过遍历pid和ppid数组,把一个进程对应的所以儿子进程存储到一个数组中,然后用一个队列进行BFS找出所有的子孙进程。因为每一个进程只有一个父进程,所以不用担心有重复和循环搜索,因此无需设置visited标志。

结果分析

  • 时间复杂度: $ O(N) $ 遍历复杂度为2次 O(N) $, BFS的复杂度小于$ O(N) $
  • 空间复杂度: $ O(N) $ 每个PID存储了2次且最多进对列一次
  • 通过时间: 172 ms
  • 击败: 89.68%的提交

源代码

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        vector<int> res;
        unordered_map<int, vector<int>> childPid;
        for(int i = 0; i < ppid.size(); ++i){
            auto it = childPid.find(ppid[i]);
            if(it == childPid.end()){
                childPid.insert(make_pair(ppid[i], vector<int>(1, pid[i])));
            }else{
                it->second.push_back(pid[i]);
            }
        }
        queue<int> killQueue;
        killQueue.push(kill);
        while(!killQueue.empty()){
            int nowPid = killQueue.front();
            killQueue.pop();
            res.push_back(nowPid);

            auto it = childPid.find(nowPid);
            if(it != childPid.end()){
                // 有子进程
                for(auto p : it->second){
                    killQueue.push(p);
                }
            }
            
        }
        return res;
    }
};