Skip to content

Latest commit

 

History

History
147 lines (118 loc) · 4.07 KB

README_EN.md

File metadata and controls

147 lines (118 loc) · 4.07 KB
Raw

582. Kill Process

中文文档

Description

You have n processes forming a rooted tree structure. You are given two integer arrays pid and ppid, where pid[i] is the ID of the ith process and ppid[i] is the ID of the ith process's parent process.

Each process has only one parent process but may have multiple children processes. Only one process has ppid[i] = 0, which means this process has no parent process (the root of the tree).

When a process is killed, all of its children processes will also be killed.

Given an integer kill representing the ID of a process you want to kill, return a list of the IDs of the processes that will be killed. You may return the answer in any order.

 

Example 1:

Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
Output: [5,10]
Explanation: The processes colored in red are the processes that should be killed.

Example 2:

Input: pid = [1], ppid = [0], kill = 1
Output: [1]

 

Constraints:

  • n == pid.length
  • n == ppid.length
  • 1 <= n <= 5 * 104
  • 1 <= pid[i] <= 5 * 104
  • 0 <= ppid[i] <= 5 * 104
  • Only one process has no parent.
  • All the values of pid are unique.
  • kill is guaranteed to be in pid.

Solutions

Python3

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        def dfs(u):
            ans.append(u)
            for v in g[u]:
                dfs(v)

        g = defaultdict(list)
        n = len(pid)
        for c, p in zip(pid, ppid):
            g[p].append(c)
        ans = []
        dfs(kill)
        return ans

Java

class Solution {
    private Map<Integer, List<Integer>> g;
    private List<Integer> ans;

    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        g = new HashMap<>();
        for (int i = 0, n = pid.size(); i < n; ++i) {
            int c = pid.get(i), p = ppid.get(i);
            g.computeIfAbsent(p, k -> new ArrayList<>()).add(c);
        }
        ans = new ArrayList<>();
        dfs(kill);
        return ans;
    }

    private void dfs(int u) {
        ans.add(u);
        for (int v : g.getOrDefault(u, new ArrayList<>())) {
            dfs(v);
        }
    }
}

C++

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> g;
        vector<int> ans;
        int n = pid.size();
        for (int i = 0; i < n; ++i) {
            int c = pid[i], p = ppid[i];
            g[p].push_back(c);
        }
        dfs(kill, g, ans);
        return ans;
    }

    void dfs(int u, unordered_map<int, vector<int>>& g, vector<int>& ans) {
        ans.push_back(u);
        for (int v : g[u]) dfs(v, g, ans);
    }
};

Go

func killProcess(pid []int, ppid []int, kill int) []int {
	g := make(map[int][]int)
	for i, c := range pid {
		p := ppid[i]
		g[p] = append(g[p], c)
	}
	var ans []int
	var dfs func(u int)
	dfs = func(u int) {
		ans = append(ans, u)
		for _, v := range g[u] {
			dfs(v)
		}
	}
	dfs(kill)
	return ans
}

...