Ən Kiçik Ümumi Region Leetcode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur AirbnbBaxılıb 33

Problem bəyanat

Ən Kiçik Ümumi Region Leetcode Həlli – Sizə bəzi siyahılar verilir regions burada hər bir siyahının birinci bölgəsi həmin siyahıdakı bütün digər bölgələri əhatə edir.

Təbii ki, bir bölgə x başqa bir bölgəni ehtiva edir y sonra x daha böyükdür y. Həm də tərifinə görə, bir bölgə x özünü ehtiva edir.

İki bölgəni nəzərə alaraq: region1 və region2, qayıt hər ikisini ehtiva edən ən kiçik bölgə.

Əgər rayonlar verilirsə r1r2və r3 belə r1 daxildir r3, olmadığına zəmanət verilir r2 belə r2 daxildir r3.

Ən kiçik bölgəyə zəmanət verilir.

misal

Input:

regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"

Çıxış:

 "North America"

Explanation:

“Şimali Amerika” regionu həm “Kvebek” həm də “Nyu York”u ehtiva edən ən kiçik bölgə olduğundan, biz “Şimali Amerika”nı qaytarırıq.

Input:

 regions = [["Earth", "North America", "South America"],["North America", "United States", "Canada"],["United States", "New York", "Boston"],["Canada", "Ontario", "Quebec"],["South America", "Brazil"]], region1 = "Canada", region2 = "South America"

Çıxış:

 "Earth"

İzahat:

“Yer” bölgəsi həm “Kanada”, həm də “Cənubi Amerika”nı ehtiva edən ən kiçik bölgə olduğundan, biz “Yer”i qaytarırıq.

Yanaşma

Idea:

Biz bu problem kimi düşünün graph problem, regionların hər siyahısında birinci bölgə bütün digər kiçik elementləri ehtiva edən ən böyüyüdür, o, müəyyən siyahıdakı bütün bölgələr üçün ana qovşaq kimi çıxış edəcəkdir.

Bu qrafikə diqqətlə baxsaq, bunun aydın olduğunu görə bilərik qrafik ağacdır çünki daha böyük bölgə yalnız kiçik elementi ehtiva edə bilər, əksinə deyil. Belə ki, orada iki istiqamətli kənarlar olmayacaq.  Həmçinin, orada heç bir dublikat region olmayacaq sualda verildiyi kimi.

Verilmiş hər iki bölgəni ehtiva edən ən kiçik bölgəni tapmalı olduğumuz üçün problem iki qovşağın LCA-sını tapmaqdan qaynaqlanır.

Alqoritm:

Addım -1 Hər bir uşağın valideynini saxlamaq üçün Hashmap yaradın.

Addım-2 Bölgənin əcdad tarixini saxlamaq üçün Hashmap-dən istifadə edin1.

Addım-3 Bölgənin2 əcdad tarixindən keçin və bunun da region1 yolunda olduğu aşkar edilərsə, bu, region1 və region2 arasındakı ən kiçik ümumi bölgəmizdir.

Ən Kiçik Ümumi Region üçün Kod

C ++ kodu

class Solution {
public:
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        
        unordered_map<string,string> parent;
        // To store the parent of every node.
        
        for(auto vc : regions){
            for(int i=1;i<vc.size();i++){
                parent[vc[i]] = vc[0];
                // Since first index is parent of all other nodes in the list.
            }
        }
        
        unordered_map<string,int> vis;
        //To keep track of all the nodes in the path from region1 to root.
        
        while(region1.size()!=0){
            vis[region1] = 1;
            region1 = parent[region1];
            // Making all the nodes visited.
        }
        
        while(!vis.count(region2)){
            region2 = parent[region2];
        }
        //while the node in the path is not visited previosly keep moving up, towards root.
        
        
        return region2;
        //We have found a common region.
    }
};

Java kodu

class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2){
        
        Map<String, String> parents = new HashMap<>();
        // To store the parent of every node.
        
        Set<String> ancestryHistory = new HashSet<>();
        //To keep track of all the nodes in the path from region1 to root.
        
        for (List<String> region : regions)
            for (int i = 1; i < region.size(); ++i){
                // Since first index is parent of all other nodes in the list.   
                parents.put(region.get(i), region.get(0));
            }
        
        
        while (region1 != null) {
            ancestryHistory.add(region1);
            region1 = parents.get(region1);
            // Making all the nodes visited.
        }
        
        //while the node in the path is not visited previosly keep moving up, towards root.
        while (!ancestryHistory.contains(region2))
            region2 = parents.get(region2);
        
        return region2;
        //We have found a common region.
    }
}

Ən Kiçik Ümumi Region Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Biz valideyni izləmək üçün bütün bölgələri gəzirik və sonra ağacda yuxarıya doğru hərəkət edirik, Beləliklə, ümumi zaman mürəkkəbliyi O(N), burada N bölgələrin ümumi sayıdır.

Kosmik Mürəkkəblik

Biz hər bir qovşağın valideynini saxlamaq üçün əlavə yerdən və ziyarət edilən xəritə üçün əlavə yerdən istifadə edirik. Beləliklə, ümumi Kosmik mürəkkəblik həm də O(N),  burada N regionların ümumi sayıdır.

Translate »