En ağır taşları parçala
Görev tanımı
Problem
Bir taş yığını ağırlıklarıyla tarif ediliyor. Tekrar tekrar en ağır iki taşı al ve birbirine çarparak parçala: eşit taşlar birbirini tamamen yok eder, eşit olmayanlar ise farkı ağırlığında tek bir taş bırakır ve o da yığına geri döner. Kalan son taşın ağırlığını döndür; yığın boşalırsa 0 döndür.
Örnekler
Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1
Neden: 7 ile 8 1 bırakır, sonra 2 ile 4 2 bırakır, sonra 1 ile 2 1 bırakır, sonra 1 ile 1 yok olur
Input: stones = [1, 1]
Output: 0
Neden: eşit iki taş birbirini yok eder, hiçbir şey kalmaz
Input: stones = [3]
Output: 3
Neden: edge case: yalnız bir taşın çarpışacağı bir şey yok
İpuçları
0 / 3
Her parçalamadan sonra bütün yığını yeniden sıralamak doğrudur ama sorunun gerektirdiğinden çok daha fazla iş yapar, çünkü her turda yalnız iki taş değişir.
Yığına sorulan tek şey bana şu anki en ağırı ver, geri eklenen tek şey de tek bir yeni taş. Bu iki işlem yapının adını koyar.
Her ağırlığı her zaman en büyük öğeyi geri veren ve yeni öğeleri ucuza kabul eden bir yapıya yükle. Her turda iki öğe al ve farklarını yalnız sıfır değilse geri koy. İkiden az öğe kalınca dur.
- Hedef zaman
- O(n log n)
- Hedef alan
- O(n)
Çözüm
Taşlara yalnız iki soru sorulur, bana en ağırı ver ve bu yeni taşı al; bir heap'in logaritmik zamanda cevapladığı da tam olarak bu. Onu bir kez kurup sonra tekrar tekrar parçalamak her turdan sonra yeniden sıralamaktan kaçınır. Sıfır fark basitçe geri push edilmez; bu yüzden taş sayısı o durumda iki, aksi halde bir azalır ve döngü ya bir taşla ya da hiç taşsız biter. Zaman O(n log n), heap için alan O(n).
import heapq
def last_stone_weight(stones):
heap = [-w for w in stones] # negated, because the library heap is a min-heap
heapq.heapify(heap)
while len(heap) > 1:
heaviest = -heapq.heappop(heap)
second = -heapq.heappop(heap)
if heaviest != second: # equal stones vanish, so nothing goes back
heapq.heappush(heap, -(heaviest - second))
return -heap[0] if heap else 0
print(last_stone_weight([2, 7, 4, 1, 8, 1])) # -> 1
print(last_stone_weight([1, 1])) # -> 0
print(last_stone_weight([3])) # -> 3Kodda değil de fikirde mi takıldın? Heap temelleri bunu anlatıyor.