Last Stone Weight

+10

Bir taş yığınınız var ve stones[i], i taşının ağırlığıdır. Her turda en ağır iki taşı alıp birbirine vurun. Ağırlıkları eşitse ikisi de yok edilir. Eşit değilse, hafif olan yok edilir ve ağır olanın ağırlığı iki ağırlık arasındaki fark kadar azalır.

En fazla bir taş kalana kadar turları sürdüren ve kalan taşın ağırlığını döndüren ya da hiç taş kalmadığında 0 döndüren lastStoneWeight fonksiyonunu yazın.

Fonksiyon

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: yığındaki taşların ağırlıkları
Döndürürinteger: son taşın ağırlığı veya hiç taş kalmadıysa 0

Kısıtlar

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

Örnekler

Girdi: stones = [3, 9, 4, 6, 2]
Çıktı: 0
Açıklama: 9 ve 6, geriye 3 bırakır; ardından 4 ve 3, geriye 1 bırakır; sonra 3 ve 2, geriye bir 1 daha bırakır. İki 1 taşı birbirini yok eder, bu nedenle cevap 0 olur.

Girdi: stones = [10, 4, 1]
Çıktı: 5
Açıklama: 10 ve 4, geriye 6 bırakır; 6 ve 1 ise geriye 5 bırakır. Bir taş kalır ve ağırlığı 5'tir.

Girdi: stones = [8]
Çıktı: 8
Açıklama: Tek bir taşı parçalamak için başka bir taş yoktur, bu yüzden ağırlığı olan 8 cevaptır.

Ek soru

Ağırlıklar en fazla 1000. Bu üst sınırı kullanarak, bir yığın olmadan O(n + W) sürede tamamlayabilir misin? Burada W en büyük ağırlıktır.

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

İleri atlamak için bir formül yok: her turu oynarsın. Ezilen bir taş daha hafif olarak geri gelebileceğinden, her tur sürekli değişen bir yığındaki en ağır iki taşı gerektirir. Bir max-heap en ağır taşı verir ve O(log n) süresinde yeni bir taşı geri alır.

Her turda yığını sırala

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Kuralları harfiyen uygulayın: yığını sıralayın, en ağır iki taşı sondan alın ve fark sıfır değilse geri koyun. Fark herhangi bir yere gelebileceğinden her turda yeniden sıralayın. İlk örnekte 9 ve 6 geriye bir 3 bırakır; bu taş 4'ün altına yerleştirilmelidir.

Her turda en az bir taş kaldırılır; dolayısıyla en fazla n-1 tur vardır ve her turda en fazla n taş sıralanır: O(n² log n). n = 10^4 için bu, en fazla 10^4 sayının yaklaşık 10^4 kez sıralanması demektir.

Algoritma

Taşları pile adlı bir listeye kopyala.
Yığında birden fazla taş olduğu sürece, artan sırada sırala.
Son iki taşı, heaviest ve second değişkenlerini al.
Farklılarsa, heaviest - second değerini yığına geri ekle.
Kalan taşı döndür veya yığın boşsa 0 döndür.

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

Maksimum yığın

Sezgi

Bir maksimum yığın, en büyük değeri en üstte tutar; en üstteki değeri çıkarmak veya bir değer eklemek O(log n) maliyetlidir. Bütün taşları yığına koy. Her turda, en ağır iki taş için iki kez çıkar ve fark sıfır değilse tekrar ekle; yığın onu doğru yere taşır. [10, 4, 1] için 10 ve 4 değerlerini çıkarıp 6 eklersin; ardından 6 ve 1 değerlerini çıkarıp 5 eklersin.

En fazla n-1 tur boyunca ikişer çıkarma ve bir ekleme yapılır; bu nedenle zaman karmaşıklığı O(n log n), alan karmaşıklığı ise O(n) olur. Yerleşik bir yığını olmayan dillerde çözüm, yığını bir dizide tutar; i indeksinin ebeveyni (i-1)/2 indeksindedir.

Algoritma

Her taşı bir maksimum yığına koy.
Yığında birden fazla taş olduğu sürece en ağırını, ardından ikinci en ağırını çıkar.
Farklılarsa heaviest - second değerini ekle.
Yığının tepesindeki değeri döndür veya yığın boşsa 0 döndür.

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

Tuzaklar ve uç durumlar

Boş bir yığının tepesindeki öğeyi döndürmek. İlk örnekte olduğu gibi son iki taşın ağırlığı aynı olduğunda geriye hiçbir şey kalmaz ve yanıt 0 olur.
Yanlışlıkla bir min-yığın kullanmak. Python'daki heapq ve Java'nın varsayılan PriorityQueue'su en küçük değeri verir; ağırlıkları negatif yapın veya ters sıralama karşılaştırıcısı geçirin.
Negatif ağırlıklarla işaret kuralını unutmak. Pop edilen iki değer de negatiftir, bu nedenle yığına eklenecek değer -(heaviest - second) olur.
Listenin başında bir kez sıralama yapıp listede ilerlemek. Fark, henüz ele almadığınız taşlardan daha hafif olabilir; bu nedenle ilk turdan sonra sıralama geçerliliğini yitirir.

Sıkça sorulan sorular3

Last Stone Weight'ın zaman karmaşıklığı nedir?

Bir maksimum yığınla, iki çıkarma ve bir eklemeden oluşan en fazla n-1 tur O(n log n) zaman ve O(n) alan alır. Her turda tüm yığını sıralamak O(n² log n) zaman alır.

Last Stone Weight için sıralı bir liste yerine neden yığın kullanılır?

Sıralı bir liste en ağır iki taşı aynı anda verir, ancak farkı yeniden sıralı hâle getirmek en fazla n girdiyi kaydırır; tüm turlar boyunca bu işlem O(n²) sürer. Bir yığın yalnızca “en büyük değer hangisi?” sorusunu yanıtlar ve yeni bir değeri O(log n) sürede kabul eder; simülasyonun istediği de budur.

Eşit ağırlıktaki taşları parçalama sırası sonucu değiştirir mi?

Hayır. Birkaç taş en ağır ağırlığı paylaşıyorsa, hangisini seçersen seç seçtiğin iki taşın ağırlığı aynı olur; bu nedenle turdan sonra yığında aynı ağırlıklar kalır. Yanıt yalnızca ağırlıklara bağlıdır.

def lastStoneWeight(stones):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

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

Beklenen Çıktı