Son daş çəki

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon
Görməmiş YığınBaxılıb 89

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.

Son daş çəki bəzi müsbət ağırlıqlara sahib bir sıra daşlarımızın olduğu bir problemdir. İndi 1 daş qoyana və ya heç bir daş qoyana qədər bunun üzərində bir vəzifə yerinə yetiririk. Həmişə ən yüksək çəki_dəyəri olan və iki daş seçirik uçurmaq onları birlikdə. Daşların ağırlığının a, b və a <= b olduğunu fərz edək. The şut nəticəsində edir:

  • A == b olarsa, hər iki daş tamamilə məhv olur.
  • A! = B olduqda, ağırlığı = a olan daş tamamilə məhv olur və ağırlığı = b olan daş yeni ağırlığa malikdir.

Sonda ən çox 1 daş qalıb. Bu daşın ağırlığını çap edin və ya 0-ı çap etmək üçün heç bir daş qalmayıbsa.

Giriş Formatı

Birinci sətir tam daş sayını izah edən N dəyəri.

Bu daşların ağırlığını ehtiva edən ikinci sətir, w [i], i-ci daşın ağırlığını ifadə edir.

Çıxış formatı

Sol daşın ağırlığını bir sətirdə çap edin. Heç bir daş qalmırsa, 0 yazdırın.

Məhdudiyyətlər

  • 1 <= N <= 10 ^ 5
  • 1 <= çəki [i] <= 10 ^ 9
6
2 7 4 1 8 1
1

Izahat

Əvvəlcə 7,8 olan ən ağır iki daş seçirik. İndi ikisini də vururuq və vurduqdan sonra ağırlığı = 1 olan daş qalır. İndi yenidən {2, 4, 1, 1, 1} dəstindəki iki ən ağır daşları seçirik. Budur 2,4. İndi onları parçaladıqdan sonra ağırlığı = 2 olan daş qoyduq. Yenidən {1, 1, 1, 2} dəstindən iki ən ağır daş seçin. Budur 1,2. İndi onları çırpın və çəkisi = 1 olan son daşı əldə etdik. Yenə də hər biri ağırlıqda yalnız 3 daş qalırıq = 1. Onlardan iki daş seçin və parçalayın. Sonra hər iki daş tamamilə məhv edildi. İndi yalnız 1 daş qoyduq, sonra həmin daşın ağırlığını çap etdik. Bizim çəkimiz = 1 olan daşımız belədir çap 1.

Alqoritm

Step:1 Push all the stones into priority_queue such that top of queue contain heaviest weight.
Step:2 While size of priority_queue is greater than 1 then:
             a) pop value from top of priority_queue and store in variable b.
             b) pop one more value and store in variable a.
             c) perform smash such that:
                    if a!=b then:
                      priority_queue.push_back(b-a).
Step:3 If size of priority queue is 0 then:
          Print 0.
       Else:
          Print size of the stone which is left in the priority_queue.

Həyata keçirilməsi

/*C++ Implementation of Last Stone Weight.*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{ 
    /*input values.*/ 
    int n; 
    cin>>n;
    int weight[n];
    priority_queue<int> q;
    /*store elements in priority_queue*/
    for(int i=0;i<n;i++)
    {
        cin>>weight[i];
        q.push(weight[i]);
    }
    /*smash two heaviest stones till we reach the condition atmost 1 element present.*/
    while(q.size()>1)
    {
        /*heaviest stone.*/
        int a=q.top();
        q.pop();
        /*second heaviest stone.*/
        int b=q.top();
        q.pop();
        /*smash result*/
        if(a!=b)
        {
            q.push(a-b);
        }
    }
    /*print result*/
    if(q.empty())
    {
        cout<<0<<endl;
    }
    else
    {
        cout<<q.top()<<endl;
    }
    return 0; 
}
7
321 5 253 2 7 9 1045
448

Zamanın mürəkkəbliyi

O (N * logN) burada N bizə verilən daşların sayıdır. Daşları elementin tam yerinə yerləşdirmək üçün logN vaxtı tələb edən növbə növbəsində saxlayırıq. Artan qaydada prioritet növbədəki elementlər. Yığımın üst hissəsi maksimum, sonra ikinci maksimum ikinci element yuxarıdan və s. Deməkdir ...

Kosmik Mürəkkəblik

O (N) burada N bizə verilən daşların sayıdır. Elementi artan qaydada saxlayan prioritet növbədən istifadə edirik.

References

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