পাইথনে লাস্ট স্টোন ওয়েট (Last Stone Weight in Python)

সমস্যা বিবরণ

কিছু স্টোন দেওয়া আছে, প্রতিটির পজিটিভ ইন্টিজার ওয়েট। প্রতিটি টার্নে দুটি সবচোয়ে বড় স্টোন বেছে নিয়ে স্ম্যাশ করা হবে।

• যদি x = y: দুটি স্টোনই ধ্বস্ত।
• যদি x ≠ y: ছোটটি (x) ধ্বস্ত, বড়টির (y) নতুন ওয়েট = y - x।

শেষে 최대 ১টি স্টোন থাকবে। তার ওয়েট ফেরত দিন (না থাকলে ০)।

উদাহরণ: [2,7,4,1,8,1] → ১ (প্রক্রিয়া: 8,7→1; 4,2→2; 2,1→1; 1,1→ধ্বস্ত; বাকি ১)।

সমাধানের পদ্ধতি (ম্যাক্স হিপ / সর্টিং)

1. স্টোন লিস্ট খালি হলে ০, একটাই থাকলে সেটি ফেরত দিন।
2. যদি একাধিক থাকে:
   • লিস্ট সর্ট করুন।
   • সর্বোচ্চ দুটি (s1, s2) নিন।
   • যদি সমান হয়: দুটোই মুছে ফেলুন।
   • অন্যথায়: পার্থক্য (s1-s2) কে লিস্টে ফেরত দিন (সর্বোচ্চ ইনডেক্সে)।
3. একটি বা শূন্য স্টোন থাকার পর্যন্ত রিপিট করুন।

পাইথন উদাহরণ (সর্টিং)

class Solution(object):
    def lastStoneWeight(self, stones):
        if not stones: 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()
                stones.pop()
            else:
                stones.pop()
                stones[-1] = s1 - s2
        
        return stones[0] if stones else 0

ob1 = Solution()
print(ob1.lastStoneWeight([2,7,4,1,6,1]))

ইনপুট

[2,7,4,1,6,1]

আউটপুট

1

অপ্টিমাইজড: হিপ (Priority Queue) - O(n log n)

import heapq

def lastStoneWeight(stones):
    # Max heap: negative values ব্যবহার
    max_heap = [-s for s in stones]
    heapq.heapify(max_heap)
    
    while len(max_heap) > 1:
        s1 = -heapq.heappop(max_heap)
        s2 = -heapq.heappop(max_heap)
        if s1 != s2:
            heapq.heappush(max_heap, -(s1 - s2))
    
    return -max_heap[0] if max_heap else 0