[crampon programming] lintcode decoding Encyclopedia - 872 termination process

【 Crampon programming 】LintCode Decoding Encyclopedia —— 872 Terminate the process

author ：BZIClaw

---

872 Terminate the process

Python：

class Solution:
    """ @param pid: the process id @param ppid: the parent process id @param kill: a PID you want to kill @return: a list of PIDs of processes that will be killed in the end """
    def killProcess(self, pid, ppid, kill):
        m={
    }
        for i,parent in enumerate(ppid):
            if parent not in m:
               m[parent] = []
            m[parent].append(pid[i])
        ans=[]
        que=[kill]
        while que:
            cur = que.pop(0)
            ans.append(cur)
            if cur in m:
                que +=m[cur]
        return ans
        # Write your code here

Java:

public class Solution {
    
    /** * @param pid: the process id * @param ppid: the parent process id * @param kill: a PID you want to kill * @return: a list of PIDs of processes that will be killed in the end */
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
    
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < pid.size(); i++) {
    
            List<Integer> list = map.getOrDefault(ppid.get(i), new ArrayList<>());
            list.add(pid.get(i));
            map.put(ppid.get(i), list);
        }
        List<Integer> list = new ArrayList<>();
        list.add(kill);
        killChildProcess(map, list, kill);
        return list;
    }

    private void killChildProcess(Map<Integer, List<Integer>> map, List<Integer> list, int kill) {
    
        if (map.containsKey(kill)) {
    
            for (Integer i : map.get(kill)) {
    
                list.add(i);
                killChildProcess(map, list, i);
            }
        }
    }
}

C++:

class Solution {
    
public:
    /** * @param pid: the process id * @param ppid: the parent process id * @param kill: a PID you want to kill * @return: a list of PIDs of processes that will be killed in the end */
    void dfs(unordered_map<int,vector<int>>& tree,int cur,vector<int>& ret){
    
        for(auto& pid:tree[cur]){
    
            dfs(tree,pid,ret);
        }
        ret.emplace_back(cur);
    }

    vector<int> killProcess(vector<int> &pid, vector<int> &ppid, int kill) {
    
        // Write your code here
        int n=pid.size();
        vector<int> ret;
        unordered_map<int,vector<int>> tree;
        for(int i=0;i<n;++i){
    
            tree[ppid[i]].emplace_back(pid[i]);
        }
        dfs(tree,kill,ret);
        return ret;
    }
};

JavaScript:

export class Solution {
    

  /** * killProcess * * @param pid: the process id * @param ppid: the parent process id * @param kill: a PID you want to kill * @return: a list of PIDs of processes that will be killed in the end */
  killProcess(pid, ppid, kill) {
    
    // Write your code here
    const cid = {
    };

    for(let i = 0 ; i < ppid.length ; ++i) {
    
        const p = ppid[i];
        const c = pid[i];
        if(cid[p] === void 0) {
    
            cid[p] = [c];
        }else{
    
            cid[p].push(c);
        }
    }

    const ans = [];

    const dfs = (id) => {
    
        ans.push(id);
        if(cid[id] === void 0) return;
        if(cid[id]) {
    
            for(const c of cid[id]) {
    
                dfs(c);
            }
        }

    }

    dfs(kill);

    return ans;

  }

}

Go:

/** * @param pid: the process id * @param ppid: the parent process id * @param kill: a PID you want to kill * @return: a list of PIDs of processes that will be killed in the end */
 import (
   "sort"
 )
type Arr []int

func (l Arr) Len() int           {
     return len(l) }
func (l Arr) Swap(i, j int)      {
     l[i], l[j] = l[j], l[i] }
func (l Arr) Less(i, j int) bool {
     return l[i] < l[j] }
func killProcess(pid []int, ppid []int, kill int) []int {
    
	mapParent := make(map[int][]int)
	for index, value := range pid {
    
		if ppid[index] == 0 {
    
			continue
		}
		if _, ok := mapParent[ppid[index]]; !ok {
    
			mapParent[ppid[index]] = make([]int, 0)
		}
		mapParent[ppid[index]] = append(mapParent[ppid[index]], value)
	}
	queue := make([]int, 0)
	queue = append(queue, kill)
	end := 0
	for end < len(queue) {
    
		for ; end < len(queue); end++ {
    
			if _, ok := mapParent[queue[end]]; !ok {
    
				continue
			}
			for _, next := range mapParent[queue[end]] {
    
				queue = append(queue, next)
			}
		}
	}
	sort.Sort(Arr(queue))
	return queue
}

---

Pay attention to me , Learn more about programming