LeetCode 582. 杀掉进程

Categories:

题目描述
思路分析
1. 解法一：构建树 + BFS（推荐）
相似题目

题目描述

✅ 582. 杀掉进程

思路分析

解法一：构建树 + BFS（推荐）

核心思路：

通过 ppid -> 子进程列表 构建邻接表。

从 kill 作为根进行 BFS/DFS，收集所有可达节点。

可达的所有进程即需要被杀掉的进程。

复杂度分析：

时间复杂度：O(n)，其中 n 表示进程数量。

空间复杂度：O(n)，用于邻接表与队列。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < pid.size(); i++) {
            graph.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
        }

        List<Integer> res = new ArrayList<>();
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(kill);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            res.add(cur);
            List<Integer> children = graph.get(cur);
            if (children == null) {
                continue;
            }
            for (int next : children) {
                queue.offer(next);
            }
        }

        return res;
    }
}

func killProcess(pid []int, ppid []int, kill int) []int {
	graph := make(map[int][]int)
	for i := 0; i < len(pid); i++ {
		graph[ppid[i]] = append(graph[ppid[i]], pid[i])
	}

	res := make([]int, 0)
	queue := make([]int, 0)
	queue = append(queue, kill)

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		res = append(res, cur)
		for _, next := range graph[cur] {
			queue = append(queue, next)
		}
	}

	return res
}

相似题目

题目	难度	考察点
690. 员工的重要性	简单	BFS/DFS
841. 钥匙和房间	中等	BFS/DFS
133. 克隆图	中等	图遍历
200. 岛屿数量	中等	DFS/BFS
797. 所有可能的路径	中等	DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/42770317