Küçədəki ən parlaq mövqe LeetCode Həll

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon RobinlikBaxılıb 74

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

Küçədə Ən Parlaq Mövqe LeetCode Həlli – Bizdən küçəni təmsil edən rəqəm xəttini qəbul etməyimiz xahiş olunur. Bu küçədə lampa(lar) var. Bizə 2D tam ədəd massivi “işıqları” verilir. Hər bir işıq [i] = [mövqe_i, diapazon_i], [mövqe_i – diapazon_i, mövqe_i + diapazon_i] nöqtəsindən (hər ikisi daxil olmaqla) küçəni işıqlandıra bilən mövqe_i üzərində küçə lampası olduğunu göstərir. P mövqeyinin parlaqlığı p mövqeyini yandıran küçə lampalarının sayı kimi müəyyən edilir. Küçədəki ən parlaq mövqeyə qayıtmalıyıq. Bir neçə ən parlaq mövqe varsa, ən aşağısı cavabdır.

Nümunələr və izahat

Misal 1:

Küçədəki ən parlaq mövqe LeetCode HəllPin

Input: lights = [[-3,2],[1,2],[3,3]]
Output: -1
Explanation:
The first street lamp lights up the area from [(-3) - 2, (-3) + 2] = [-5, -1].
The second street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3].
The third street lamp lights up the area from [3 - 3, 3 + 3] = [0, 6].

Position -1 has a brightness of 2, illuminated by the first and second street light.
Positions 0, 1, 2, and 3 have a brightness of 2, illuminated by the second and third street light.
Out of all these positions, -1 is the smallest, so return it.

Misal 2:
Input: lights = [[1,0],[0,1]]
Output: 1
Explanation:
The first street lamp lights up the area from [1 - 0, 1 + 0] = [1, 1].
The second street lamp lights up the area from [0 - 1, 0 + 1] = [-1, 1].

Position 1 has a brightness of 2, illuminated by the first and second street light.
Return 1 because it is the brightest position on the street.

Misal 3:
Input: lights = [[1,2]]
Output: -1
Explanation:
The first street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3].

Positions -1, 0, 1, 2, and 3 have a brightness of 1, illuminated by the first street light.
Out of all these positions, -1 is the smallest, so return it.

Yanaşma

Bu problemi asanlıqla həll etmək olar array və ya xəritə. Lampa ilə yanan hər nöqtə üçün ona bir əlavə edəcəyik. Ən aşağı nöqtədən hərəkət etməyə başlayın və massivdə maksimum parlaq nöqtənin mövqeyini saxlayın. Kiçik mövqe dəyərləri üçün bu problemi həll etmək üçün bu yanaşmadan istifadə edə bilərik. Məhdudiyyətlərə uyğun olaraq, mövqe[i] -10^8 ilə 10^8 arasında dəyişir. Bu həll TLE-yə səbəb olacaq. Daha yaxşısını edə bilərikmi?

Əgər müşahidə etsək, əslində müəyyən bir lampanın yandırdığı bütün dəyərləri izləməyə ehtiyacımız yoxdur, çünki biz yalnız ən kiçik mövqeyə qayıtmalıyıq. Beləliklə, lampa ilə yanan bütün mövqelərə 1 əlavə etmək əvəzinə, biz yalnız ən aşağı nöqtəni artırırıq, yəni map[poisiton[i]-range[i]]++ və map[position[i] + range[ dəyərini azaldırıq. i] + 1]. Biz sadəcə olaraq ən aşağı mövqedən keçə və maksimum parlaq nöqtəni izləmək üçün say dəyişənini artırmağa davam edə bilərik. Hər hansı bir nöqtə yanmazsa, saymanın dəyəri azalacaq.

Kodu

Küçədəki ən parlaq mövqe üçün C++ kodu

class Solution {
public:
    int brightestPosition(vector<vector<int>>& lights) {
        map<int,int> brightness;
        for(auto& light: lights) {
            brightness[light[0]-light[1]]++, brightness[light[0]+light[1]+1]--;
        }
        int maxBrightness=0, maxBrightPoint=0, cntBright=0;
        
        for(auto& bright: brightness){
            cntBright+=bright.second;
            if(cntBright > maxBrightness) {
                maxBrightness = cntBright;
                maxBrightPoint = bright.first;
            }
        }
        
        return maxBrightPoint;
    }
};

Küçədəki ən parlaq mövqe üçün Java kodu

class Solution {
    public int brightestPosition(int[][] lights) {
        int length = lights.length;
        int left = 0, right = 0;
        
        TreeMap<Integer, Integer> treemap = new TreeMap<>();
        for(int[] light : lights) {
            left = (light[0] - light[1]);
            right = (light[0] + light[1] + 1);
            treemap.put(left, (treemap.getOrDefault(left, 0) + 1));
            treemap.put(right, (treemap.getOrDefault(right, 0) - 1));
        }
        
        int countBright = 0, maxBrightness = 0, maxBrightPoint = 0;
        for(Map.Entry<Integer, Integer> entry : treemap.entrySet()) {
            countBright += entry.getValue();
            if(maxBrightness < countBright) {
                maxBrightness = countBright;
                maxBrightPoint = entry.getKey();
            }
        }
        return maxBrightPoint;
    }
}

Küçədə ən parlaq mövqe üçün mürəkkəblik təhlili LeetCode Həll

  • Zaman mürəkkəbliyi: O(N*logN), N=verilmiş 2D massivinin uzunluğu
    • Biz xəritə yaratmaq üçün 2D massivini keçirik, hər işıq üçün[i] xəritəyə 2 dəyər əlavə edirik və ya yeniləyirik, xəritənin çeşidlənməsi O(logN) alır.
    • xəritədə maksimum dəyərlər 2*n ola bilər
    • başqa bir döngə çeşidlənmiş xəritədəki bütün dəyərlərdən keçir, ümumi vaxt = O(2*N*logN) O(N*logN) ilə bərabərdir
  • Kosmik mürəkkəblik: O (N)
    • Parlaq nöqtələri izləmək üçün əlavə Xəritə tələb olunur
Crack Sistemi Dizayn Müsahibələri
Translate »