Proses LeetCode Həllini öldürün

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg google microsoft SalesforceBaxılıb 22

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ş.

Proses LeetCode Həllini öldürünPin

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.

Referans: https://en.wikipedia.org/wiki/Tree_traversal

Şərh yaz

Translate »