leetcode_582. 杀掉进程

系统中存在 n 个进程，形成一个有根树结构。给你两个整数数组 pid 和 ppid ，其中 pid[i] 是第 i 个进程的 ID ，ppid[i] 是第 i 个进程的父进程 ID 。

每一个进程只有一个父进程，但是可能会有一个或者多个子进程。只有一个进程的 ppid[i] = 0 ，意味着这个进程没有父进程。

当一个进程被杀掉的时候，它所有的子进程和后代进程都要被杀掉。

给你一个整数 kill 表示要杀掉??进程的 ID ，返回杀掉该进程后的所有进程 ID 的列表。可以按任意顺序返回答案。

示例 1：

输入：pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
输出：[5,10]
解释：涂为红色的进程是应该被杀掉的进程。

示例 2：

输入：pid = [1], ppid = [0], kill = 1
输出：[1]

提示：

n == pid.length
n == ppid.length
1 <= n <= 5 * 104
1 <= pid[i] <= 5 * 104
0 <= ppid[i] <= 5 * 104
仅有一个进程没有父进程
pid 中的所有值互不相同
题目数据保证 kill 在 pid 中

方法1 ： HASH + DFS

HASH 存储父亲和儿子（一个父亲可以有多个儿子，儿子只有一个父亲）

kill 作为父亲起点， dfs找到所有的儿子

#define N 50000
typedef struct{
    int father;
    int son[N];
    int index;
    UT_hash_handle hh;
}Hash;
int g_index;
Hash *hash = NULL;

void Dfs(int father, int *res) {
    res[g_index++] = father;
    Hash *p = NULL;
    HASH_FIND_INT(hash, &father, p);
    if(p == NULL) {
        return ;
    } 
    for (int i = 0; i < p->index; i++) {
        Dfs(p->son[i], res);
    }
}
int* killProcess(int* pid, int pidSize, int* ppid, int ppidSize, int kill, int* returnSize){
    hash = NULL;
    for(int i = 0; i < pidSize; i++) {
        Hash *tmp =NULL;
        HASH_FIND_INT(hash, &(ppid[i]), tmp);
        if(tmp == NULL) {
            tmp = (Hash *)malloc(sizeof(Hash));
            memset(tmp, 0, sizeof(Hash));
            tmp->son[tmp->index++] = pid[i];
            tmp->father = ppid[i];
            HASH_ADD_INT(hash, father, tmp);
        } else {
            tmp->son[tmp->index++] = pid[i];
        }
    }
    int *res = (int *)malloc(sizeof(int) * N);
    if(res == NULL) {
        return NULL;
    }
    g_index = 0;
    Dfs(kill, res);
    *returnSize = g_index;
    Hash *t, *p;
    HASH_ITER(hh, hash, p, t) {
        if (p != NULL) {
            free(p);
            p = NULL;
        }
    }
   return res;
}

方法2：并查集

关于并查集的介绍以及代码

https://blog.csdn.net/liujian20150808/article/details/50848646

16算法

leetcode_582. 杀掉进程

相关

标签