มีก้อนหินหลายก้อน น้ำหนักเป็นจำนวนเต็มบวก ทุกรอบเลือก 2 ก้อนที่หนักที่สุด โดนกัน:
- ถ้าน้ำหนักเท่ากัน (x=y) ทั้งคู่พัง
- ถ้าไม่เท่า (x<y) ก้อนเบาพัง ก้อนหนักเหลือ y-x
ทำซ้ำจนเหลือสูงสุด 1 ก้อน หาค่าน้ำหนักสุดท้าย (0 ถ้าไม่เหลือ)
ตัวอย่าง: [2,7,4,1,8,1] → เลือก 8,7 เหลือ 1 → [2,4,1,1,1] → เลือก 4,2 เหลือ 2 → [2,1,1,1] → เลือก 2,1 เหลือ 1 → [1,1,1] → เลือก 1,1 พัง → [1] คำตอบ = 1
ขั้นตอนการแก้ปัญหา
- ถ้าไม่มีหิน คืน 0; ถ้า 1 ก้อน คืนค่านั้น
- วนลูปจนเหลือ ≤ 1 ก้อน:
- เรียงลำดับหิน
- เลือก 2 ก้อนสุดท้าย (หนักที่สุด)
- ถ้าเท่ากัน pop ทั้งคู่
- ถ้าไม่เท่า pop ก้อนหนัก แล้วอัปเดตค่าใหม่ = ความต่าง
- คืนค่าที่เหลือ (หรือ 0)
ตัวอย่างโค้ด
class Solution(object):
def lastStoneWeight(self, stones):
if len(stones) == 0:
return 0
if len(stones) == 1:
return stones[0]
while len(stones) > 1:
stones.sort()
s1, s2 = stones[-1], stones[-2]
if s1 == s2:
stones.pop(-1)
stones.pop(-1)
else:
s1 = abs(s1 - s2)
stones.pop(-1)
stones[-1] = s1
if len(stones):
return stones[-1]
return 0
ob1 = Solution()
print(ob1.lastStoneWeight([2,7,4,1,6,1]))
อินพุต
[2,7,4,1,6,1]
เอาต์พุต
1
วิธีแก้แบบ Heap (Max Heap) - ประสิทธิภาพดีกว่า O(n log n)
import heapq
def lastStoneWeight(stones):
# Python มี min-heap ใช้ค่าลบเพื่อทำ max-heap
stones = [-s for s in stones]
heapq.heapify(stones)
while len(stones) > 1:
s1 = -heapq.heappop(stones)
s2 = -heapq.heappop(stones)
if s1 != s2:
heapq.heappush(stones, -(s1 - s2))
return -stones[0] if stones else 0
