Last Stone Weight

Q: Berapa kompleksitas waktu Last Stone Weight?

Dengan max-heap, paling banyak n-1 putaran yang masing-masing melakukan dua pop dan satu push membutuhkan waktu O(n log n) dan ruang O(n) . Mengurutkan seluruh tumpukan pada setiap putaran membutuhkan waktu O(n² log n) .

MudahHeap

+10

Kamu memiliki tumpukan batu, dan stones[i] adalah berat batu i. Di setiap ronde, ambil dua batu terberat dan benturkan keduanya. Jika beratnya sama, keduanya hancur. Jika tidak, batu yang lebih ringan hancur dan berat batu yang lebih berat berkurang sebesar selisih kedua berat tersebut.

Tulis lastStoneWeight, yang menjalankan ronde hingga tersisa paling banyak satu batu dan mengembalikan beratnya, atau 0 jika tidak ada batu yang tersisa.

Fungsi

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: berat batu-batu di tumpukan
Mengembalikaninteger: berat batu terakhir, atau 0 jika tidak ada yang tersisa

Batasan

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

Contoh

Input: stones = [3, 9, 4, 6, 2]
Output: 0
Penjelasan: 9 dan 6 menyisakan 3, lalu 4 dan 3 menyisakan 1, lalu 3 dan 2 menyisakan 1 lagi. Kedua batu 1 saling menghancurkan, jadi jawabannya adalah 0.

Input: stones = [10, 4, 1]
Output: 5
Penjelasan: 10 dan 4 menyisakan 6, lalu 6 dan 1 menyisakan 5. Satu batu tersisa dengan berat 5.

Input: stones = [8]
Output: 8
Penjelasan: Satu batu tidak memiliki apa pun untuk menghancurkannya, jadi beratnya 8 adalah jawabannya.

Pertanyaan lanjutan

Bobotnya paling besar 1000. Bisakah kamu memanfaatkan batas tersebut untuk menyelesaikannya dalam waktu O(n + W), dengan W sebagai bobot terbesar, tanpa heap?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Tidak ada rumus untuk melewati giliran: kamu memainkan setiap ronde. Setiap ronde membutuhkan dua batu terberat dari tumpukan yang terus berubah, karena batu yang dihancurkan bisa kembali dengan bobot lebih ringan. Max-heap memberikan batu terberat dan menerima batu baru dalam O(log n).

Urutkan tumpukan setiap putaran

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Ikuti aturan secara harfiah: urutkan tumpukan, ambil dua batu terberat dari ujung, lalu masukkan selisihnya kembali jika tidak nol. Urutkan lagi pada setiap putaran, karena selisihnya bisa berada di mana saja. Pada contoh pertama, 9 dan 6 menghasilkan 3, yang harus diletakkan di bawah 4.

Setiap putaran menghilangkan setidaknya satu batu, jadi ada hingga n-1 putaran, masing-masing mengurutkan hingga n batu: O(n² log n). Untuk n = 10^4, jumlahnya sekitar 10^4 kali pengurutan hingga 10^4 angka.

Algoritma

Salin batu-batu ke dalam list bernama pile.
Selama pile berisi lebih dari satu batu, urutkan dari yang terkecil ke terbesar.
Ambil dua batu terakhir, heaviest dan second.
Jika keduanya berbeda, tambahkan kembali heaviest - second ke pile.
Kembalikan batu yang tersisa, atau 0 jika pile kosong.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

Max-heap

Intuisi

Max-heap menyimpan nilai terbesar di posisi teratas, dan menghapus nilai teratas atau menambahkan nilai membutuhkan biaya O(log n). Masukkan setiap batu ke dalamnya. Pada setiap putaran, keluarkan dua nilai untuk mendapatkan dua batu terberat, lalu masukkan kembali selisihnya jika tidak nol; heap akan menempatkannya. Untuk [10, 4, 1], kamu mengeluarkan 10 dan 4, lalu memasukkan 6, kemudian mengeluarkan 6 dan 1, lalu memasukkan 5.

Ada paling banyak n-1 putaran, masing-masing dengan dua kali pengeluaran dan satu kali pemasukan, sehingga waktu yang dibutuhkan adalah O(n log n) dan ruang yang dibutuhkan adalah O(n). Dalam bahasa yang tidak memiliki heap bawaan, solusi ini menyimpan heap dalam array, dengan parent dari indeks i berada di (i-1)/2.

Algoritma

Masukkan setiap batu ke dalam max-heap.
Selama heap berisi lebih dari satu batu, keluarkan batu terberat, lalu batu terberat kedua.
Jika beratnya berbeda, masukkan heaviest - second.
Kembalikan elemen teratas heap, atau 0 jika heap kosong.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

Jebakan dan kasus tepi

Mengembalikan bagian atas tumpukan yang kosong. Jika berat dua batu terakhir sama, seperti pada contoh pertama, tidak ada batu tersisa dan jawabannya adalah 0.
Tidak sengaja menggunakan min-heap. heapq di Python dan PriorityQueue bawaan Java memberikan nilai terkecil, negasikan beratnya atau berikan pembanding terbalik.
Lupa membalik tanda saat menggunakan berat yang dinegasikan. Kedua nilai yang diambil bernilai negatif, jadi nilai yang perlu dimasukkan adalah -(heaviest - second).
Mengurutkan sekali di awal lalu menelusuri list. Hasil selisihnya bisa lebih ringan daripada batu yang belum kamu sentuh, jadi urutannya tidak lagi berlaku setelah putaran pertama.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Last Stone Weight?

Dengan max-heap, paling banyak n-1 putaran yang masing-masing melakukan dua pop dan satu push membutuhkan waktu O(n log n) dan ruang O(n). Mengurutkan seluruh tumpukan pada setiap putaran membutuhkan waktu O(n² log n).

Mengapa menggunakan heap untuk Last Stone Weight, bukan list yang diurutkan?

list yang terurut memberikan dua batu terberat sekaligus, tetapi mengembalikan selisihnya ke urutan yang benar menggeser hingga n entri, O(n²) untuk semua putaran. Heap hanya menjawab "mana yang terbesar" dan menerima nilai baru, keduanya dalam O(log n), yang memang dibutuhkan simulasi.

Apakah urutan menghancurkan batu dengan bobot yang sama mengubah jawabannya?

Tidak. Jika beberapa batu memiliki berat paling tinggi yang sama, dua batu yang kamu pilih memiliki berat yang sama, apa pun pilihannya, sehingga tumpukan setelah ronde memiliki berat yang sama. Jawabannya hanya bergantung pada berat batu.

def lastStoneWeight(stones):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

stones = [3, 9, 4, 6, 2]

Output yang diharapkan