Asteroid Collision

Q: Berapa kompleksitas waktu dari Asteroid Collision?

Waktu O(n) dan ruang O(n) dengan stack asteroid yang bertahan, karena setiap asteroid didorong dan dikeluarkan paling banyak satu kali. Memindai ulang barisan setelah setiap tabrakan membutuhkan O(n²) .

Q: Mengapa stack menjadi struktur data yang tepat untuk Asteroid Collision?

Asteroid baru hanya dapat mencapai para penyintas yang paling dekat dengannya, dan asteroid itu menemui mereka dari yang terbaru hingga yang terlama. Artinya, yang terakhir masuk, keluar lebih dulu. Apa pun yang berada di tumpukan pada akhirnya tidak dapat lagi tertabrak, jadi itulah baris terakhir.

Q: Bisakah Asteroid Collision diselesaikan dengan ruang tambahan O(1)?

Ya, jika kamu boleh menimpa input. Gunakan bagian depan array sebagai stack: simpan indeks penulisan top , bandingkan dengan asteroids[top-1] , lalu kembalikan top entri pertama.

SedangStack

+10

Sederet asteroid melaju di sepanjang garis dengan kecepatan yang sama. Setiap nilai dalam asteroids menjelaskan satu asteroid: nilai absolutnya adalah ukurannya, dan tandanya menunjukkan arahnya, positif untuk ke kanan dan negatif untuk ke kiri.

Ketika asteroid yang bergerak ke kanan bertemu dengan asteroid yang bergerak ke kiri, keduanya bertabrakan. Asteroid yang lebih kecil meledak. Jika ukurannya sama, keduanya meledak. Asteroid yang bergerak ke arah yang sama tidak pernah bertemu. Kembalikan asteroid yang tersisa setelah semua tabrakan, dalam urutan semula. Hasilnya bisa kosong.

Fungsi

asteroidCollision(asteroids: integer-array) → integer-array

asteroidsinteger-array: asteroid-asteroid dari kiri ke kanan, tanda untuk arah, nilai absolut untuk ukuran
Mengembalikaninteger-array: asteroid yang masih tersisa dari kiri ke kanan, mungkin tidak ada

Batasan

1 ≤ asteroids.length ≤ 10⁴
-1000 ≤ asteroids[i] ≤ 1000
asteroids[i] ≠ 0

Contoh

Input: asteroids = [4, 9, -6, 2, -3]
Output: [4, 9]
Penjelasan: 9 bertemu -6 dan menang. 2 bertemu -3 dan meledak, lalu -3 terus melaju menuju 9 dan ikut meledak. Tidak ada yang bergerak menuju apa pun, jadi tersisa 4 dan 9.

Pertanyaan lanjutan

Tumpukan menentukan asteroid mana yang bertahan. Bagaimana kamu juga melaporkan, untuk setiap asteroid yang meledak, indeks asteroid yang menghancurkannya?

Solusi

Satu asteroid yang bergerak ke kiri dapat menghancurkan rangkaian panjang asteroid yang bergerak ke kanan, dan setiap tabrakan dapat mempertemukan pasangan baru yang kemudian bertabrakan. Asteroid baru selalu bertemu dengan asteroid yang paling baru bertahan terlebih dahulu, jadi tumpukan asteroid yang bertahan dapat menyelesaikan setiap tabrakan dalam satu kali lintasan.

Selesaikan satu crash setiap kali

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Dua asteroid bertabrakan tepat saat asteroid yang bergerak ke kanan berada tepat di sebelah kiri asteroid yang bergerak ke kiri. Temukan pasangan pertama seperti itu, selesaikan tabrakannya, lalu pindai lagi dari kiri. Jika tidak ada pasangan yang tersisa, tidak akan ada tabrakan lagi dan barisan itu menjadi jawabannya.

Urutan penyelesaian tidak berpengaruh: dua asteroid berdekatan yang saling berhadapan akan bertemu sebelum salah satunya dapat bertemu dengan asteroid lain.

Setiap tabrakan membutuhkan pemindaian baru dan penghapusan dari tengah barisan. Dengan 9,999 asteroid kecil yang bergerak ke kanan diikuti -1000, setiap pemindaian menelusuri barisan untuk menghancurkan satu asteroid yang bergerak ke kanan: sekitar 5 × 10^7 langkah.

Algoritma

Salin baris agar kamu bisa menghapus asteroid darinya.
Telusuri dari kiri untuk menemukan indeks pertama i dengan row[i] > 0 dan row[i+1] < 0.
Jika tidak ada, kembalikan baris tersebut.
Jika ada, hapus yang lebih kecil dari keduanya, atau hapus keduanya jika ukurannya sama, lalu telusuri lagi.

def asteroidCollision(asteroids):
    row = list(asteroids)
    while True:
        # A crash happens where a right-mover is directly followed by a left-mover.
        hit = -1
        for i in range(len(row) - 1):
            if row[i] > 0 and row[i + 1] < 0:
                hit = i
                break
        if hit == -1:
            return row
        right, left = row[hit], -row[hit + 1]
        if right > left:
            del row[hit + 1]
        elif right < left:
            del row[hit]
        else:
            del row[hit:hit + 2]

Susunan para penyintas

Intuisi

Simpan para penyintas sejauh ini di dalam tumpukan. Tumpukan itu tidak pernah berisi asteroid yang bergerak ke kanan diikuti asteroid yang bergerak ke kiri, karena pasangan itu pasti sudah bertabrakan. Jadi, isinya adalah asteroid yang bergerak ke kiri dan berhasil lolos, diikuti asteroid yang bergerak ke kanan.

Asteroid baru yang bergerak ke kanan menjauh dari semua asteroid di tumpukan, jadi kamu menambahkannya ke tumpukan. Asteroid baru yang bergerak ke kiri melaju menuju asteroid yang bergerak ke kanan di bagian atas dan bertemu asteroid yang paling baru terlebih dahulu, jadi asteroid paling atas adalah satu-satunya asteroid yang bisa ditabraknya berikutnya. Pada contoh pertama, -3 mengeluarkan 2, lalu meledak saat bertabrakan dengan 9, dan tumpukan [4, 9] adalah jawabannya dalam urutan aslinya.

Setiap asteroid ditambahkan ke tumpukan paling banyak sekali dan dikeluarkan paling banyak sekali, jadi proses ini berjalan dalam O(n), bahkan ketika satu asteroid yang bergerak ke kiri membersihkan rangkaian yang panjang.

Algoritma

Mulai dengan stack penyintas yang kosong.
Untuk setiap asteroid, jika bergerak ke kanan, masukkan ke stack lalu lanjutkan.
Jika bergerak ke kiri, keluarkan asteroid yang bergerak ke kanan dari bagian atas selama ukurannya lebih kecil darinya.
Jika bagian atas kini berisi asteroid yang bergerak ke kanan dengan ukuran yang sama, keluarkan asteroid itu dan buang asteroid baru. Jika bagian atas berisi asteroid yang bergerak ke kanan dengan ukuran lebih besar, buang asteroid baru. Jika tidak, masukkan asteroid baru ke stack.
Kembalikan stack dari bawah ke atas.

def asteroidCollision(asteroids):
    survivors = []  # the row so far, after every crash it caused
    for rock in asteroids:
        alive = True
        # Only a left-mover can hit something: a right-mover on top of the stack.
        while alive and rock < 0 and survivors and survivors[-1] > 0:
            top = survivors[-1]
            if top < -rock:
                survivors.pop()        # the right-mover is smaller and explodes
            elif top == -rock:
                survivors.pop()        # same size: both explode
                alive = False
            else:
                alive = False          # the right-mover is bigger: the new one explodes
        if alive:
            survivors.append(rock)
    return survivors

Jebakan dan kasus tepi

Menganggap benda yang bergerak ke kiri lalu diikuti benda yang bergerak ke kanan sebagai tabrakan. Dalam [-2, -7, 3, 8], kelompok-kelompok itu bergerak menjauh dan keempatnya selamat.
Menggunakan if, bukan while, untuk operasi pop. Dalam [1, 2, 3, 4, 5, -15], benda yang bergerak ke kiri menghancurkan kelima benda yang bergerak ke kanan dan tetap selamat.
Melewatkan kasus nilai yang sama. [6, -6] harus mengeluarkan 6 dari stack dan membuang -6, sehingga hasilnya kosong.
Memasukkan benda yang bergerak ke kiri padahal sudah kalah. Dalam [9, -6], -6 meledak dan tidak boleh masuk ke stack. Gunakan penanda untuk mengetahui apakah benda itu masih hidup.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Asteroid Collision?

Waktu O(n) dan ruang O(n) dengan stack asteroid yang bertahan, karena setiap asteroid didorong dan dikeluarkan paling banyak satu kali. Memindai ulang barisan setelah setiap tabrakan membutuhkan O(n²).

Mengapa stack menjadi struktur data yang tepat untuk Asteroid Collision?

Asteroid baru hanya dapat mencapai para penyintas yang paling dekat dengannya, dan asteroid itu menemui mereka dari yang terbaru hingga yang terlama. Artinya, yang terakhir masuk, keluar lebih dulu. Apa pun yang berada di tumpukan pada akhirnya tidak dapat lagi tertabrak, jadi itulah baris terakhir.

Bisakah Asteroid Collision diselesaikan dengan ruang tambahan O(1)?

Ya, jika kamu boleh menimpa input. Gunakan bagian depan array sebagai stack: simpan indeks penulisan top, bandingkan dengan asteroids[top-1], lalu kembalikan top entri pertama.

def asteroidCollision(asteroids):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

asteroids = [4, 9, -6, 2, -3]

Output yang diharapkan

[4, 9]