Mündəricat
Problem bəyanat
Kill Process LeetCode Solution - Sizdə var n köklü ağac quruluşunu meydana gətirən proseslər. Sizə iki tam massiv verilir pid və ppid, Harada pid[i] nin identifikatorudur ith prosesi və ppid[i] nin identifikatorudur ith prosesin ana prosesi.
Hər bir proses yalnız var bir valideyn prosesi lakin birdən çox uşaq prosesləri ola bilər. Yalnız bir proses var ppid[i] = 0, yəni bu proses var heç bir valideyn prosesi (ağacın kökü).
Bir proses olduqda həlak, onun bütün uşaq prosesləri də öldürüləcək.
Bir tam verilir kill öldürmək, qayıtmaq istədiyiniz prosesin şəxsiyyətini təmsil edir öldürüləcək proseslərin şəxsiyyət vəsiqələrinin siyahısı. Cavabı geri qaytara bilərsiniz hər hansı bir sifariş.
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.
Izahat
biz müəyyən bir proses dəyərini və onun birbaşa uşaqlarının siyahısını saxlayan heşməpdən istifadə edə bilərik.
Və sonra bir kimi müalicə edin ağac traversal problem. (BFS/DFS)
or
Bu proseslə əlaqəli uşaq prosesini saxlayan qonşuluq siyahısı yaradın. Öldürüləcək prosesdən başlayaraq BFS-ni işə salın. Öldürülmüş bütün prosesləri saxlayın
Kodu
Öldürmə prosesi üçün C++ kodu
class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
vector<int> killed;
map<int, set<int>> children;
for (int i = 0; i < pid.size(); i++) {
children[ppid[i]].insert(pid[i]);
}
killAll(kill, children, killed);
return killed;
}
private:
void killAll(int pid, map<int, set<int>>& children, vector<int>& killed) {
killed.push_back(pid);
for (int child : children[pid]) {
killAll(child, children, killed);
}
}
};
Öldürmə prosesi üçün Java kodu
public class Solution {
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
if (kill == 0) return pid;
int n = pid.size();
Map<Integer, Set<Integer>> tree = new HashMap<>();
for (int i = 0; i < n; i++) {
tree.put(pid.get(i), new HashSet<Integer>());
}
for (int i = 0; i < n; i++) {
if (tree.containsKey(ppid.get(i))) {
Set<Integer> children = tree.get(ppid.get(i));
children.add(pid.get(i));
tree.put(ppid.get(i), children);
}
}
List<Integer> result = new ArrayList<>();
traverse(tree, result, kill);
return result;
}
private void traverse(Map<Integer, Set<Integer>> tree, List<Integer> result, int pid) {
result.add(pid);
Set<Integer> children = tree.get(pid);
for (Integer child : children) {
traverse(tree, result, child);
}
}
}
Öldürmə Prosesi üçün Python Kodu
class Solution(object):
def killProcess(self, pid, ppid, kill):
"""
:type pid: List[int]
:type ppid: List[int]
:type kill: int
:rtype: List[int]
"""
myTree = dict()
for i, parent in enumerate(ppid):
myTree[parent] = myTree.get(parent,[])
myTree[parent].append(pid[i])
res = []
stack = [kill]
while stack:
cur = stack.pop()
res.append(cur)
stack.extend(myTree.get(cur,[]))
return res
Öldürmə Prosesi üçün Mürəkkəblik Təhlili LeetCode Həlli
Zamanın mürəkkəbliyi
O(n+e) çünki biz a bfs keçid.
Kosmik Mürəkkəblik
O(n) çünki biz qovşaqları yığın/massivdə saxlayırıq.
