Restoranları Vegan Dostu, Qiymət və Məsafə Leetcode Həllinə görə süzün

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon VəngiltiBaxılıb 60

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Restoranları Vegan Dostu, Qiymət və Məsafə Leetcode Həllinə görə süzün – Massiv nəzərə alınmaqla restaurants hara  restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]. Siz üç filtrdən istifadə edərək restoranları süzməlisiniz.

The veganFriendly filter də olacaq doğru (yalnız restoranları daxil etməlisiniz veganFriendlyi doğru olaraq təyin edin) və ya saxta (istənilən restoran daxil edə bilərsiniz deməkdir). Bundan əlavə, sizdə filtrlər var maxPrice və maxDistance müvafiq olaraq nəzərə almalı olduğunuz restoranların qiyməti və məsafəsi üçün maksimum dəyərdir.

Qayıt array restoranın ID'ler süzgəcdən sonra sifarişlə reytinq ən yüksəkdən aşağıya. Eyni reytinqə malik restoranlar üçün onları sifariş edin id ən yüksəkdən aşağıya. Sadəlik üçün veganFriendlyi və veganFriendly dəyər götür 1 olanda doğruvə 0 olanda saxta.

misal

Input:

 restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10

Çıxış:

 [3,1,5] 

Explanation:

The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] 
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest).

 

Input:

 restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10

Çıxış:

 [4,3,2,1,5]

Explanation:

 The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.

Yanaşma

Idea:

Əsas fikir ilk növbədə restoranların siyahısını reytinqlərə görə sıralamaqdır, əgər reytinqlər eynidirsə, id-yə görə. Bunun üçün biz öz fərdi müqayisə funksiyamızı qura bilərik.

İndi restoranları çeşidlədikdən sonra etibarlı restoranların id-lərini başqa vektora daxil edib onu qaytara bilərik.

Kodu

Restoranları Veqan Dostu, Qiymət və Məsafə ilə Filtr etmək üçün C++ Kodu

class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        int n = restaurants.size();
        
        //Firstly sort on the basis of the condition given.
        sort(restaurants.begin(),restaurants.end(),[](vector<int> &a,vector<int> &b){
            if(a[1] == b[1]){
                return a[0] > b[0];
            } 
            return a[1] > b[1];
        });
        
        vector<int> id;
        //Then, insert the ids of valid restaurants in the result vector.
        for(auto vc : restaurants){
            if(veganFriendly==1 && vc[2]!=1){continue;}
            if(vc[3]>maxPrice){continue;}
            if(vc[4]>maxDistance){continue;}
            
            id.push_back(vc[0]);
        }
        
        return id;
    }
};

Restoranları Veqan Dostu, Qiymət və Məsafə ilə Filtr etmək üçün Java Kodu

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
          Arrays.sort(restaurants, (a,b) -> 
            (a[1]==b[1] ? b[0]-a[0] : b[1]-a[1])
        );
        
        List<Integer> result = new ArrayList<>();
        for(int[] arr: restaurants) {
            if((veganFriendly == arr[2] || veganFriendly == 0) 
              && maxPrice >= arr[3] && maxDistance >= arr[4]) {
                result.add(arr[0]);
            }
        }
        
        return result;
    }
}

 

Vegan dostu, qiymət və məsafə Leetcode Həlli ilə Filtr Restoranları üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Bütün siyahının çeşidlənməsi O(nlogn) vaxtını alır və çeşidlənmiş siyahıdan etibarlı identifikatorun seçilməsi başqa O(n) vaxtı alır. Ümumi Mürəkkəblik O(n + nlogn), yəni O(nlogn).

Kosmik Mürəkkəblik

Biz yalnız O(k) boşluğundan istifadə edirik, burada k etibarlı restoranların sayını göstərir, çünki ən pis halda k n-ə meyl edə bilər. Beləliklə, ümumi Kosmik Mürəkkəblik O(n)-dir.

Crack Sistemi Dizayn Müsahibələri
Translate »