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 çarpın. Ağırlıkları aynıysa ikisi de yok edilir. 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ı ya da hiç taş kalmadığında 0 değerini döndüren lastStoneWeight adlı bir fonksiyon 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, ardından 3 ve 2 geriye bir 1 daha bırakır. Ağırlığı 1 olan iki taş birbirini yok eder, bu yüzden geriye hiçbir şey kalmaz ve 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. Geriye, ağırlığı 5 olan bir taş kalır.

Girdi: stones = [8]
Çıktı: 8
Açıklama: Tek bir taşı parçalayacak başka bir taş yoktur, bu nedenle ağırlığı olan 8 cevaptır.

Gönderirken +13 gizli test

Ek soru

Ağırlıklar en fazla 1000. Yığın kullanmadan O(n + W) süresinde tamamlamak için bu sınırdan yararlanabilir 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

Kurallar bir simülasyondur: ileriyi atlamak için bir formül yoktur, bu yüzden her turu oynarsın. Her turda, parçalanan bir taş daha hafif hâlde geri dönebileceği için sürekli değişen bir yığındaki en ağır iki taşa ihtiyaç vardır. Her turda yeniden sıralama onları bulur ama tur başına O(n log n) maliyeti vardır. Bir maksimum yığın, en ağır taşı verir ve O(log n) içinde yeni bir taşı geri alır.

Her turda yığını sırala

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

Sezgi

Kuralları olduğu gibi uygulayın. En ağır iki taş en sonda olacak şekilde yığını sıralayın, bu taşları çıkarın ve ağırlıkları farklıysa aradaki farkı tekrar yığına koyun. Yığında bir taş kalana veya hiç taş kalmayana kadar tekrarlayın.

Aradaki fark sıralamada herhangi bir yere gelebilir. İlk örnekte 9 ve 6 çıkarılınca geriye 3 kalır; bu taş 4'ün altında yer almalıdır. Bu nedenle, sonraki turda en ağır iki taşı bulmak için yeniden sıralama yaparsınız.

Her turda en az bir taş çıkarılır; dolayısıyla en fazla n-1 tur yapılır ve her turda en fazla n taş sıralanır: O(n² log n). n = 10^4 için bu, sıralama listesinin neredeyse sıralı olduğunu fark ettiğinde bile en az 5 × 10^7 adım gerektiren, en fazla 10^4 sayı içeren yaklaşık 10^4 sıralama demektir; bunu fark etmediğinde ise adım sayısı bunun birkaç katına çıkar. Bu, en büyük testler için çok yavaştır; aşağıdaki yığın ise yalnızca birkaç yüz bin adım gerektirir.

Algoritma

Taşları pile adlı bir listeye kopyala.
Yığında birden fazla taş olduğu sürece, listeyi artan sırada sırala.
Son iki taşı, heaviest ve second değerlerini çıkar.
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

Her turda yalnızca en büyük taşlara ihtiyacın olur; tüm sıralamaya asla gerek yoktur. Bunun için bir max-heap oluşturulur: en büyük değeri en üstte tutar ve en üsttekini kaldırmanın ya da bir değer eklemenin maliyeti O(log n) olur.

Her taşı heap'e koy. Her turda en ağır iki taşı almak için iki kez pop yap. Farklılarsa farkı geri ekle; heap onu kendi kendine doğru yerine taşır. [10, 4, 1] için 10 ve 4 değerlerini pop edip 6 değerini eklersin, ardından 6 ve 1 değerlerini pop edip 5 değerini eklersin; heap'te yalnızca 5 kalır.

En fazla n-1 tur vardır; her turda iki pop ve en fazla bir push yapılır. Bu nedenle zaman karmaşıklığı O(n log n), heap'in kullandığı alan ise O(n) olur. Bazı dillerde hazır bir heap bulunur: Python'daki heapq bir min-heap'tir, bu yüzden negatif ağırlıkları saklar; Java'da PriorityQueue, C++'ta priority_queue, Go'da container/heap, Rust'ta BinaryHeap ve PHP'de SplMaxHeap bulunur. Diğer dillerde çözüm, bir dizi üzerinde kendi heap'ini yazar: i indeksinin ebeveyni (i-1)/2 konumundadır ve yeni bir değer, ebeveynini geçtiği sürece yukarı çıkar.

Algoritma

Her taşı bir maksimum yığına koy.
Yığında birden fazla taş olduğu sürece en ağır taşı, ardından ikinci en ağır taşı çıkar.
Ağırlıkları farklıysa heaviest - second değerini yığına 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

Simülasyon kısa olduğundan hatalar, uç durumlarda ve yığının kendisinde gizlidir.

Boş yığının tepesindeki değeri döndürmek. 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'ın heapq modülü ve Java'nın varsayılan PriorityQueue sınıfı en küçük değeri verir; ağırlıkları negatif yapın veya ters sıralayıcı kullanın.
İşareti tekrar pozitife çevirmeyi unutmak. heapq ile çıkarılan iki değer de negatiftir, bu yüzden yığına eklediğiniz fark -(heaviest - second) olur.
Başta bir kez sıralayıp liste üzerinde ilerlemek. İki taşın farkı, henüz dokunmadığınız taşlardan daha hafif olabilir; dolayısıyla sabit bir sıralama ilk turdan sonra geçerliliğini yitirir.

Sıkça sorulan sorular4

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

Bir max-heap kullanıldığında, heap'i oluşturmak ve en fazla n-1 tur boyunca iki pop ve bir push işlemi yapmak O(n log n) zaman ve O(n) alan alır. Bunun yerine her turda tüm yığını sıralamak O(n² log n) zaman alır.

LastStoneWeight için neden yığın kullanılır?

Her turda, her turdan sonra değişen bir koleksiyondaki en büyük iki değer istenir. Bir yığın, koleksiyonun tamamını sıralı tutmadan “en büyük değer hangisi?” sorusunu yanıtlar ve yeni bir değeri O(log n) sürede kabul eder. Simülasyonun tekrarladığı işlem tam olarak budur.

Son Taşın Ağırlığı problemi yığın kullanılmadan çözülebilir mi?

Evet, çünkü ağırlıklar küçüktür. 1'den 1000'e kadar her ağırlığa sahip taşların sayısını sayın ve en ağır ağırlıktan başlayarak aşağı doğru ilerleyin. Eşit ağırlıktaki taşlar çiftler hâlinde birbirini yok eder ve yeni bir taş, onu oluşturmak için kullanılan en ağır taştan her zaman daha hafiftir; bu nedenle ilerleyiş yalnızca aşağı doğrudur. Bu işlem, en büyük ağırlık W için O(n + W) zamanda çalışır.

Eşit ağırlıkları parçalama sırası cevabı değiştirir mi?

Hayır. Birkaç taş en yüksek ağırlığı paylaştığında, hangisini seçersen seç seçeceğin iki taş aynı ağırlıktadır; bu nedenle turdan sonra yığındaki ağırlıklar aynı kalır. Yanıt yalnızca ağırlıklara bağlıdır; bu yüzden her doğru çözüm aynı sayıyı döndürür.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen