KillProcess [source code]
public class KillProcess {
static
/******************************************************************************/
public class Solution {
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
assert pid.size() == ppid.size();
int n = pid.size();
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int pp = ppid.get(i);
if (pp == 0)
continue;
List<Integer> ls = map.get(pp);
if (ls == null) {
ls = new ArrayList<Integer>();
map.put(pp, ls);
}
ls.add(pid.get(i));
}
List<Integer> res = new ArrayList<>();
if (pid.contains(kill))
add(map, kill, res);
return res;
}
public void add(Map<Integer, List<Integer>> map, int kill, List<Integer> res) {
res.add(kill);
List<Integer> ls = map.get(kill);
if (ls != null)
for (int i : ls)
add(map, i, res);
}
}
/******************************************************************************/
public static void main(String[] args) {
KillProcess.Solution tester = new KillProcess.Solution();
}
}
感觉这个题吧, 基本的方法还是建一个tree, 然后直接做. 不过好像这种方法不是效率很高? 一来是有点overkill, 这里我们只要kill一个pid, 不需要处理整个tree; 另外一点是这里没有给tree node的children的个数并不是固定的binary, 而是不确定的, 所以如果自己定义一个node, 那么每一个node里面要放一个list, 感觉会影响速度;
这个题目的难点你最后是要完成一个正序的traverse, 从bottom往上走; 但是实际上给你的条件是一个倒序的link: parent link rather than the child link;
稍微瞄了一眼editorial, 好像可以用Map来做. 想了一下确实是可以. 这个做法用人逻辑稍微理解一下, 好像还是合理的;
有了这个思路之后, 稍微想一下就写出来了; 这里其实就是用Map来完成一个adjacent list的efficient存取; 最后的速度是73ms (88%);
这个问题算法的思考主要还是用人逻辑尝试理解一下例子. kill最好用3, 因为5这个有点小; 实际完成的过程也很简单, 就是从ppid里面找到当前的node, 然后找到pid的对应的位置的就行(类似于找到child link edge的另外一头). 剩下的事情就是想办法怎样让这个查询过程更加efficient; 因为我们对于edge的查询其实全都是单向的, 也就是从上到下, 所以其实用ppid作为key, 然后pid作为value建立一个Map就行了;
这题建完Map之后刚开始以为剩下的过程一个循环就能写完, 不过后来看了一下好像并不是那么简单. 最好还是用recursion来写, 因为你脑子里visual一下这个过程的trace就知道了, 这个循环路径不是一条单纯的线型, 而是树状;
所以这个问题的本质其实是什么? 就是给你一堆parent link, 然后让你做一个DFS traversal from one particular node. 这个其实不是一个很偏门的问题, 普遍的做法当然就是build tree, 更个性化的做法就是直接找到这个node本身, 以及所有relevant的edge单独处理;
看了一下editorial里面, 他们好像其实都分析了kill 0的情况; 我觉得可能是有必要加一下, 虽然OJ没有判断这个;
这个是editorial1:
public class Solution {
public List < Integer > killProcess(List < Integer > pid, List < Integer > ppid, int kill) {
List < Integer > l = new ArrayList < > ();
if (kill == 0)
return l;
l.add(kill);
for (int i = 0; i < ppid.size(); i++)
if (ppid.get(i) == kill)
l.addAll(killProcess(pid, ppid, pid.get(i)));
return l;
}
}
这个算法本身其实并不trivial, 就是一个recursion; 但是因为每一个iteration的fanning都是N, 所以最后实际上的复杂度达到了N^N;
算法本身还是有一定的学习意义, subproblem, recursive return value等概念在这个算法当中的定义还算是都比较清晰的;
这个是editorial2, 就是build tree的做法:
public class Solution {
class Node {
int val;
List < Node > children = new ArrayList < > ();
}
public List < Integer > killProcess(List < Integer > pid, List < Integer > ppid, int kill) {
HashMap < Integer, Node > map = new HashMap < > ();
for (int id: pid) {
Node node = new Node();
node.val = id;
map.put(id, node);
}
for (int i = 0; i < ppid.size(); i++) {
if (ppid.get(i) > 0) {
Node par = map.get(ppid.get(i));
par.children.add(map.get(pid.get(i)));
}
}
List < Integer > l = new ArrayList < > ();
l.add(kill);
getAllChildren(map.get(kill), l);
return l;
}
public void getAllChildren(Node pn, List < Integer > l) {
for (Node n: pn.children) {
l.add(n.val);
getAllChildren(n, l);
}
}
}
总体的过程跟我预想的其实还是差不多的, 需要注意的是他build的过程中的这个Map的使用; 因为你先处理pid, 然后处理ppid, 在处理ppid的时候, 想要一个get node by integer的操作, 这个你不依靠Map是无法完成的.
更general的, 碰到这种有retrieve需求的, 都可以考虑建表;
这个的复杂度是N. 刚开始没有想明白, 因为这个过程其实还是分好几个阶段的, 有点复杂, 所以最好还是有一个代码/伪代码的框架才好分析复杂度. 不是所有的代码都可以跟aggregate那样脑子里比划比划就可以知道复杂度的;
editorial3就是我这个做法: HashMap + DFS.
Thus, now, by traversing just once over the ppid array, and adding the corresponding pid values to the children list at the same time, we can obtain a better structure storing the parent-children relationship.
所以他这里认为, 上面editorial2的这个tree, 其实也就是一个way of storing edge information, 而这种store的方式, 针对这个问题并不如一个HashMap更有效率;
这是他的代码:
public class Solution {
public List < Integer > killProcess(List < Integer > pid, List < Integer > ppid, int kill) {
HashMap < Integer, List < Integer >> map = new HashMap < > ();
for (int i = 0; i < ppid.size(); i++) {
if (ppid.get(i) > 0) {
List < Integer > l = map.getOrDefault(ppid.get(i), new ArrayList < Integer > ());
l.add(pid.get(i));
map.put(ppid.get(i), l);
}
}
List < Integer > l = new ArrayList < > ();
l.add(kill);
getAllChildren(map, l, kill);
return l;
}
public void getAllChildren(HashMap < Integer, List < Integer >> map, List < Integer > l, int kill) {
if (map.containsKey(kill))
for (int id: map.get(kill)) {
l.add(id);
getAllChildren(map, l, id);
}
}
}
几乎差不多, 注意getOrDefault的使用;
editorial4就是把DFS换成了BFS, 反正也差不多了, 换一个角度来实现recursion而已:
public class Solution {
public List < Integer > killProcess(List < Integer > pid, List < Integer > ppid, int kill) {
HashMap < Integer, List < Integer >> map = new HashMap < > ();
for (int i = 0; i < ppid.size(); i++) {
if (ppid.get(i) > 0) {
List < Integer > l = map.getOrDefault(ppid.get(i), new ArrayList < Integer > ());
l.add(pid.get(i));
map.put(ppid.get(i), l);
}
}
Queue < Integer > queue = new LinkedList < > ();
List < Integer > l = new ArrayList < > ();
queue.add(kill);
while (!queue.isEmpty()) {
int r = queue.remove();
l.add(r);
if (map.containsKey(r))
for (int id: map.get(r))
queue.add(id);
}
return l;
}
}
注意, 每一个被Poll出来的node的所有的child都要被kill(add), 因为这个就是题目的定义. 我上面说这个题目的要求是一个linear traveral, 其实是不对的, 其实是find the subtree rooted at a particular node.
这个是discussion最优解:
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
// Store process tree as an adjacency list
Map<Integer, List<Integer>> adjacencyLists = new HashMap<>();
for (int i=0;i<ppid.size();i++) {
adjacencyLists.putIfAbsent(ppid.get(i), new LinkedList<>());
adjacencyLists.get(ppid.get(i)).add(pid.get(i));
}
// Kill all processes in the subtree rooted at process "kill"
List<Integer> res = new LinkedList<>();
Stack<Integer> stack = new Stack<>();
stack.add(kill);
while (!stack.isEmpty()) {
int cur = stack.pop();
res.add(cur);
List<Integer> adjacencyList = adjacencyLists.get(cur);
if (adjacencyList == null) continue;
stack.addAll(adjacencyList);
}
return res;
}
这个的注释比较有意思; 所以我们之前上课说过, adjacent list本身就可以表达一个tree. 所以我们做了这个Map, 事实上就等效于做了一个tree;
另外, 这里另外一个可以学习的东西, 就是其实这个也是我第一次做adjacency list. 如果让你选择一个结构来保存adjacency list, 要想到用Map, 因为存取都可以达到最大的效率(比二维list快; 存的时候又比二维array方便);
注意这里这个putIfAbsent的使用;
他这里还很装逼的用了一个Stack, 不过感觉这里实现的其实并不是DFS(tree node都没有, 谈不上DFS with Stack), 最后这里实现的其实还是一个BFS的recursion;
这个是discussion里面另外一个版本:
public class Solution {
Map<Integer, List<Integer>> lookup = new HashMap<>();
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
for(int i=0; i<ppid.size(); i++) {
Integer p = ppid.get(i);
List<Integer> children = lookup.get(p);
if(children == null) {
children = new ArrayList<>();
lookup.put(p, children);
}
children.add(pid.get(i));
}
List<Integer> tbk = addChild(kill);
tbk.add(kill);
return tbk;
}
private List<Integer> addChild(int process) {
List<Integer> child = new ArrayList<>();
List<Integer> tbk = lookup.get(process); //to be killed
if(tbk == null) return child;
child.addAll(tbk);
for(Integer i : tbk) child.addAll(addChild(i));
return child;
}
}
并不是说这个版本更好, 只不过他避免了使用Side Effect. 代码本身我感觉并不如我的写法;
Problem Description
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:
- The given kill id is guaranteed to be one of the given PIDs.
- n >= 1.
Difficulty:Medium
Total Accepted:6.1K
Total Submissions:12.6K
Contributor: fallcreek
Companies
bloomberg
Related Topics
tree queue