LeetCode Kill Process

LeetCode Kill Process

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.

Example 1:

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:

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

给定一个父子进程的对应关系,现在要kill掉某个进程id,那么id的子进程,孙进程也会被kill掉,问最终被kill掉的进程有哪些。

简单题。先使用map把父子进程的对应关系存起来,因为是一个父亲可能有多个孩子进程,所以要用multimap。然后用bfs类似于树的层次遍历,把所有孩子进程遍历一遍并存到结果数组中。

代码如下,刚好看了C++ primer的unordered_multimap的范围查找,用equal_range很方便。

class Solution {
public:
	vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
		unordered_multimap<int, int> umm;
		for (int i = 0; i < pid.size(); ++i) {
			umm.insert(pair<int, int>(ppid[i], pid[i]));
		}
		vector<int> ans;
		queue<int> q;
		q.push(kill);
		while (!q.empty()) {
			int id = q.front();
			q.pop();
			ans.push_back(id);
			auto r = umm.equal_range(id);
			for (auto i = r.first; i != r.second; ++i)q.push(i->second);
		}
		return ans;
	}
};

本代码提交AC,用时166MS。

Leave a Reply

Your email address will not be published. Required fields are marked *