Müvafiq əsrlərin dostları LeetCode Həlli

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

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 :

Müvafiq əsrlərin dostları LeetCode Həll - Var n sosial media saytında şəxslər. Sizə tam ədəd massivi verilir yaş hara yaş [i] yaşıdır ith şəxs.

Bir adam x bir şəxsə dostluq sorğusu göndərməyəcək y (x != y) aşağıdakı şərtlərdən hər hansı biri doğrudursa:

  • yaş[y] <= 0.5 * yaş[x] + 7
  • yaş[y] > yaş[x]
  • yaş[y] > 100 && yaş[x] < 100

Əks halda x dostluq sorğusu göndərəcək y.

Qeyd edək ki, əgər x ünvanına sorğu göndərir yy mütləq sorğu göndərməyəcək x. Həmçinin, bir şəxs özünə dostluq sorğusu göndərməyəcək.

Qayıtmaq edilən dostluq sorğularının ümumi sayı.

Misal:

Misal 1:

Input: ages = [16,16]
Output: 2
Explanation: 2 people friend request each other.

Misal 2:

Input: ages = [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Misal 3:

Input: ages = [20,30,100,110,120]
Output: 3
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Məhdudiyyətlər:

Müvafiq əsrlərin dostları LeetCode HəlliPin

İzahat:

  • Tam ədəd massivi verilmişdir yaş hara yaş[I] yaşıdır ith şəxs.
  • Bir insan x hamısını qane edir şərtlər verilmişdir, onda x şəxs şəxsə dostluq sorğusu göndərə bilər y.
  • Biz qayıtmalıyıq dostluq sorğularının ümumi sayı edilmişdi.

Yanaşma:

  • Verilmiş məhdudiyyətdə, yaş[i]>=1 && yaş[i] <=120 so, massivini düzəldəcəyik size 121 insanın yaş tezliyini saxlamaq üçün.

                                                                            int[]freqAges=new int[121];  

  • Təkrar edin verilmiş massiv üzərində və şəxsin yaş tezliyini saxlamaq.

Müvafiq əsrlərin dostları LeetCode Həlli

  • Bundan sonra, biz keçəcəyik 1 yaşdan 120 yaşa qədər və kiminləsə dostluq xahişi etməyə çalışın yaş x-dən kiçikdir, verildiyi kimi şərt 2.
  • Hesablamaq üçün ümumi dostluq istəkləri, güman 2 nəfərin 16, 3 nəfərin isə 15 yaşı var, o zaman 16 yaşında olan insanların 15 yaşındakı insanlara etdiyi dostluq sorğularının cəmi 6 (2*3 = 6). Əgər 16 yaşında olan bütün insanlar qalan şərtə əməl edin.

Müvafiq əsrlərin dostları LeetCode HəlliPin

Müvafiq yaşda olan dostlar üçün kod:

Java Kodu:

class Solution {
    public int numFriendRequests(int[] ages) {
        int totalFriendRequest=0;
        int[]freqAges=new int[121];
        
        for(int age:ages){
            freqAges[age]++;
        }
        for(int x=1;x<=120;x++){ 
           for (int y = 0; y < x; ++y) {
                if (y <= 0.5 * x + 7 || (y > 100 && x < 100)) { continue; }
                totalFriendRequest += freqAges[x] * freqAges[y];
            }
            if (x > 0.5 * x + 7) {
            totalFriendRequest+=freqAges[x]*(freqAges[x]-1);
            }
        }
        return totalFriendRequest;
    }

}

C++ Kodu:

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {

       vector<int>freqAges(121,0);
         int totalFriendRequest=0;
        for(int age:ages){
            freqAges[age]++;
        }
        for(int x=1;x<=120;x++){ 
           for (int y = 0; y < x; ++y) {
                if (y <= 0.5 * x + 7 || (y > 100 && x < 100)) { continue; }
                totalFriendRequest += freqAges[x] * freqAges[y];
            }
            if (x > 0.5 * x + 7) {
            totalFriendRequest+=freqAges[x]*(freqAges[x]-1);
            }
        }
        return totalFriendRequest;
    }
};

Müvafiq Yaşların Dostları üçün Mürəkkəblik Təhlili Leetcode Həlli:

Zamanın mürəkkəbliyi

 O(n), ilk döngədə olduğu kimi biz üzərində səyahət edirik yaş massivinin uzunluğu, ikinci döngədə isə səyahət edirik maksimum 120*120. Beləliklə, ən pis vəziyyət O(n) olacaq

Kosmik Mürəkkəblik 

 O(1) yalnız istifadə etdiyimiz üçün 121 ölçüləri tezlik massivinin.

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