Asteroid Toqquşması LeetCode Həlli

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

Asteroid Toqquşması LeetCode Həlli – Bizə massiv verilir asteroids bir sıra asteroidləri təmsil edən tam ədədlər.

Hər bir asteroid üçün mütləq qiymət onun ölçüsünü, işarəsi isə istiqamətini (müsbət məna sağ, mənfi məna sol) ifadə edir. Hər bir asteroid eyni sürətlə hərəkət edir.

Bütün toqquşmalardan sonra asteroidlərin vəziyyətini öyrənin. İki asteroid qarşılaşarsa, kiçik olanı partlayacaq. Hər ikisi eyni ölçüdədirsə, hər ikisi partlayacaq. Eyni istiqamətdə hərəkət edən iki asteroid heç vaxt qarşılaşmayacaq.

misal

Test işi 1:

Input:

asteroidlər = [5, 10, -5]

Çıxış:

[5, 10]

Explanation:

10 və -5 toqquşur və nəticədə 10 olur. 5 və 10 heç vaxt toqquşmur.

Yanaşma:

Intuisiya

Suala görə müsbət dəyərlər sağa, mənfi dəyərlər isə sola doğru hərəkət edir. Nisbi sürət anlayışını tətbiq edə bilərik və indi mənfi istiqamətdə ikiqat sürətlə hərəkət edən sabit və mənfi qiymətlər kimi müsbət dəyərlər edə bilərik. Ancaq sürətin böyüklüyü təkcə istiqamətin əhəmiyyəti deyil.

Fikir

Məsələni nəzərdən keçirək: -

[8, 9, 6, -7, -9, 12, 50, -34]

Əvvəldən təkrarlamağa başlayın. Nə vaxt müsbət dəyərlə qarşılaşırıqsa, heç nə etmək məcburiyyətində deyilik. Sabit olduqları üçün heç kimə hücum etməyəcəklər. Ancaq mənfi bir dəyər gördüyümüz anda onun müsbət dəyərlərə hücum edəcəyinə əminik.

təsəvvür etmək [8, 9, 6] massivin içində xoşbəxt otururlar. Bu an -7 daxil olarsa, müsbət dəyərləri sıradan çıxarmağa başlayacaq. Bu, bu problemi həll etmək üçün yığından istifadə edə biləcəyimiz bir fikir verir.

Gəlin bu ideyanı kodlaşdırmaq üçün necə istifadə edəcəyimizi görək.

Eyni misalı nəzərdən keçirək [8, 9, 6, -7, -9, 12, 50, -34]
Başlanğıcda i = 0.

1. Nə vaxt müsbət dəyərlə qarşılaşsaq, onu sadəcə yığına itələyirik.
2. Mənfi bir dəyərlə qarşılaşdığımız an, bəzi və ya hamısının və ya sıfır müsbət dəyərlərin yığından çıxarılacağını bilirik. Mənfi dəyər özü sökülə bilər və ya yığına daxil ola bilər.
   Biz elementləri yığından çıxarmağa davam edəcəyik asteroids[i] > s.top(). Ancaq unutmayın ki, mənfi asteroidlər heç vaxt başqa bir mənfi asteroidi vura bilməzlər, çünki onlarla heç vaxt qarşılaşmayacaqlar. Beləliklə, son şərt while(!s.empty() and s.top() > 0 and s.top() < abs(ast[i])), biz elementləri açacağıq.
3. Dava ilə məşğul olmalıyıq s.top() == asteroids[i]. Bu halda, bir müsbət element çıxacaq və mənfi asteroid yığına daxil olmayacaq.
4. Əgər elementləri sökdükdən sonra yığın boşalırsa() və ya s.top() mənfi olarsa, bu o deməkdir ki, cari asteroidlər[i] yığına daxil olacaq.

İkili Ağacın Serializasiyası və Seriyadan çıxarılması üçün kod

C ++ Proqramı

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& a) {
        vector<int> s; // use vector to simulate stack.
        for (int i = 0; i < a.size(); i++) {
            if (a[i] > 0 || s.empty() || s.back() < 0) // a[i] is positive star or a[i] is negative star and there is no positive on stack
                s.push_back(a[i]);
            else if (s.back() <= -a[i]) { // a[i] is negative star and stack top is positive star
                if(s.back() < -a[i]) i--; // only positive star on stack top get destroyed, stay on i to check more on stack.
                s.pop_back(); // destroy positive star on the frontier;
            } // else : positive on stack bigger, negative star destroyed.
        }
        return s;
    }
};

Java Proqramı

class Solution {
    public int[] asteroidCollision(int[] a) {
        LinkedList<Integer> s = new LinkedList<>(); // use LinkedList to simulate stack so that we don't need to reverse at end.
        for (int i = 0; i < a.length; i++) {
            if (a[i] > 0 || s.isEmpty() || s.getLast() < 0)
                s.add(a[i]);
            else if (s.getLast() <= -a[i])
                if (s.pollLast() < -a[i]) i--;
        }
        return s.stream().mapToInt(i->i).toArray();
    }
}

Asteroid Toqquşması üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi: O(n). Getdi n. Sonra geri n keçdi və bütün yığını atdı.

Kosmik Mürəkkəblik: O(n). Yığın ölçüsü. Bütün asteroidlər üzərindədir qalaq.