Yeməklərin azaldılması LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur American Express
OT SonyBaxılıb 81

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

Yeməklərin Azaldılması LeetCode Həlli – Bir aşpaz bu barədə məlumat toplayıb satisfaction onun səviyyəsi n qablar. Aşpaz 1 vahid vaxtda istənilən yeməyi bişirə bilər.

Bənzər zaman əmsalı yeməyin bişirilməsi əvvəlki yeməklər də daxil olmaqla həmin yeməyi bişirmək üçün sərf olunan vaxtın məmnunluq səviyyəsinə vurulması kimi müəyyən edilir, yəni. time[i] * satisfaction[i].

Qayıtmaq bu maksimum cəmi Bu oxşar vaxt əmsalı aşpazın yeməkləri hazırladıqdan sonra əldə edə biləcəyi.

Yeməklər hazırlana bilər hər sifariş edin və aşpaz bunu əldə etmək üçün bəzi yeməkləri atıb ata bilər maksimum dəyər.

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

Izahat

Intuisiya

Bəzi yeməkləri bişirsək, onlar bütün seçimlər arasında ən qənaətbəxş olmalıdır.

Başqa bir vacib müşahidə odur ki, yeməyi kiçik məmnuniyyətlə bişirəcəyik və sonunda ən doyurucu yeməyi tərk edəcəyik.

Biz yeməkləri ən razı olanlardan seçirik.
Menyu siyahısına hər dəfə yeni yemək əlavə etdikdə,
menyu siyahısındakı bütün yeməklər daha sonra birdəfəlik bişiriləcək,
belə result += total satisfaction on the list.
Nə qədər ki, bunu etməyə davam edəcəyik A[i] + total > 0.

Yanaşma:

Problemi həll etmək üçün tələb olunan əsas müşahidə odur ki, nə qədər çox yemək əlavə etsəniz, ümumi vaxt bir o qədər çox olar T digər yeməklərə sərf edirik ki, bu da bizim istədiyimiz şeydir, çünki bunun məbləğini maksimuma çatdırmaq lazımdır T * satisfaction[i] bəzi dəyərlər üçün 0 <= i < satisfaction.length. Çünki məmnuniyyət dəyəri ola bilər -ve bütün məmnuniyyət dəyəri də belədirsə -ve onda bir yeməyə nə qədər vaxt sərf etsək də, nəticə həmişə 0 olacaq, yəni yemək hazırladıqdan sonra aşpazın əldə edə biləcəyi Bəyənmə əmsalının maksimum məbləği 0 olmalıdır. Həmçinin, yeməkləri istənilən formada hazırlamaq olar. sifariş etsəniz, yeməkləri məmnuniyyət dəyərlərinə görə çeşidləmək istərdik.

Nəzərə alın ki, hamısını atlaya bilmərik -ve dəyərləri daxil edin və ilk mənfi olmayan dəyərlə başlayın, çünki nə qədər çox yemək daxil edirik, məmnunluq əmsalının dəyəri bir o qədər çox olacaq. Çünki bəzilərini seçməli ola bilərik -ve dəyərlər də rekursiv yanaşma aşağıdakı kimi ola bilər:

  1. məmnuniyyət massivini sıralayın.
  2. sayğac saxla, de cnt 0-dan başlayır. cnt artıq nə qədər vaxt sərf edildiyini və ya artıq neçə yeməyin nəzərdən keçirildiyini göstərəcək. 1 yeməklə eyni şey 1 vahid vaxt aparır.
  3. hər bir indeks üçün i biz ya yeməyi seçə bilərik, bu halda dəyər olacaq (cnt+1)*satisfaction[i] , ya da növbəti yeməyə keçirik və bu nöqtədə qeyd olunan eyni fikrə əməl edirik.

Bu, rekursiv yanaşmaya gətirib çıxarır, DP həlli aşağıdakı kimidir:

Kodu

Qabları Azaltmaq üçün C++ Kodu

class Solution {
public:
    int maxSatisfaction(vector<int>& A) {
        sort(A.begin(), A.end());
        int res = 0, total = 0, n = A.size();
        for (int i = n - 1; i >= 0 && A[i] > -total; --i) {
            total += A[i];
            res += total;
        }
        return res;
    }
};

Qabları Azaltmaq üçün Java Kodu

class Solution {
    public int maxSatisfaction(int[] A) {
        Arrays.sort(A);
        int res = 0, total = 0, n = A.length;
        for (int i = n - 1; i >= 0 && A[i] > -total; --i) {
            total += A[i];
            res += total;
        }
        return res;
    }
}

Qabları Azaltmaq üçün Python Kodu

class Solution:
    def maxSatisfaction(self, A):
        res = total = 0
        A.sort()
        while A and A[-1] + total > 0:
            total += A.pop()
            res += total
        return res

Yeməklərin Azaldılması üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi

Çeşidləmə baş verdiyi üçün O(NlogN).

Kosmik Mürəkkəblik

O(1) çünki biz heç bir əlavə yerdən istifadə etmirik.

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

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