Last Stone Weight
لديك كومة من الأحجار، ويمثل stones[i] وزن الحجر i. في كل جولة، خذ أثقل حجرين واصدمهما معًا. إذا كان وزنهما متساويًا، يتحطم كلاهما. وإلا، يتحطم الحجر الأخف ويصبح وزن الحجر الأثقل هو الفرق بين الوزنين.
اكتب lastStoneWeight، التي تتابع الجولات حتى يتبقى حجر واحد على الأكثر، وتُعيد وزنه، أو 0 إذا لم يتبقَّ أي حجر.
الدالة
- stonesinteger-array
- أوزان الأحجار في الكومة
- تُرجعinteger
- وزن الحجر الأخير، أو 0 إذا لم يتبقَّ أي حجر
القيود
1 ≤ stones.length ≤ 1041 ≤ stones[i] ≤ 1000
أمثلة
- المدخلات
- stones = [3, 9, 4, 6, 2]
- المخرجات
- 0
- الشرح
- يترك
9و6حجرًا وزنه3، ثم يترك4و3حجرًا وزنه1، ثم يترك3و2حجرًا آخر وزنه1. يتحطم الحجَران اللذان وزنهما1أحدهما بالآخر، لذا فالإجابة هي0.
- المدخلات
- stones = [10, 4, 1]
- المخرجات
- 5
- الشرح
- يترك
10و4حجرًا وزنه6، ويترك6و1حجرًا وزنه5. يتبقى حجر واحد وزنه5.
- المدخلات
- stones = [8]
- المخرجات
- 8
- الشرح
- لا يوجد حجر آخر ليُسحق به، لذا فإن وزنه
8هو الإجابة.
سؤال إضافي
الأوزان لا تتجاوز 1000. هل يمكنك استخدام هذا الحد لإنهاء المسألة في زمن O(n + W)، حيث W هو أكبر وزن، من دون كومة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
العب الجولات كما هو موضح. ما الذي تحتاج إلى إيجاده بسرعة في بداية كل جولة؟
تحتاج كل جولة إلى أثقل حجرين، وقد يكون الحجر الذي تعيده أخف من الأحجار الموجودة بالفعل في الكومة. إن بنية تعرف دائمًا أكبر قيمة لديها، حتى بعد وصول قيم جديدة، تجنبك إعادة الفرز.
ضع جميع الأحجار في كومة قصوى. أزل عنصرين منها، وأضف الفرق إلى الكومة إذا لم يكن صفرًا، وكرّر ذلك حتى يتبقى حجر واحد على الأكثر. أعد ذلك الحجر، أو
0.
الحل
لا توجد صيغة لتجاوز الجولات: عليك خوض كل جولة. تحتاج كل جولة إلى أثقل حجرين من كومة تتغير باستمرار، لأن الحجر المهشّم قد يعود بوزن أخف. تُخرج الكومة العظمى أثقل حجر وتُدخل حجرًا جديدًا في O(log n).
رتّب الكومة في كل جولة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اتبع القواعد حرفيًا: رتّب الكومة، وخذ أثقل حجرين من نهايتها، وأعِد الفرق بينهما إذا لم يكن صفرًا. أعد الترتيب في كل جولة، لأن الفرق قد يستقر في أي موضع. في المثال الأول، ينتج عن 9 و6 حجر وزنه 3، ويجب وضعه قبل 4.
تزيل كل جولة حجرًا واحدًا على الأقل، لذا يوجد ما يصل إلى n-1 جولة، وترتّب كل منها ما يصل إلى n حجر: O(n² log n). عندما تكون n = 10^4، فهذا يعني نحو 10^4 عمليات ترتيب لما يصل إلى 10^4 عدد.
الخوارزمية
- انسخ الأحجار إلى قائمة تُسمّى
pile. - ما دام في الكومة أكثر من حجر واحد، رتّبها بترتيب تصاعدي.
- أزل آخر حجرين،
heaviestوsecond. - إذا كانا مختلفين، فأضف
heaviest - secondإلى الكومة. - أعِد الحجر المتبقي، أو
0عندما تكون الكومة فارغة.
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كومة عظمى
الفكرة
تُبقي الكومة العظمى أكبر قيمة في الأعلى، وتكلّف إزالة العنصر الأعلى أو إضافة قيمة O(log n). ضع كل حجر فيها. في كل جولة، أزل عنصرين للحصول على أثقل حجرين، ثم أضف الفرق مرة أخرى إذا لم يكن صفرًا؛ فالكومة تنقله إلى موضعه. بالنسبة إلى [10, 4, 1]، تزيل 10 و4 وتضيف 6، ثم تزيل 6 و1 وتضيف 5.
هناك على الأكثر n-1 جولة، في كل منها عمليتا إزالة وعملية إضافة واحدة، لذا يكون الزمن O(n log n) والمساحة O(n). في اللغات التي لا تحتوي على كومة مدمجة، يحتفظ الحل بكومة في مصفوفة، ويكون الأب للفهرس i عند (i-1)/2.
الخوارزمية
- ضع كل حجر في كومة عظمى.
- ما دامت الكومة تحتوي على أكثر من حجر واحد، أخرج أثقل حجر ثم الحجر الثاني من حيث الثقل.
- إذا كانا مختلفين، فأضف
heaviest - second. - أعِد العنصر الأعلى في الكومة، أو
0إذا كانت فارغة.
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
أخطاء شائعة وحالات حدّية
- إرجاع العنصر الأعلى من كومة فارغة. عندما يكون وزن الحجرين الأخيرين متساويًا، كما في المثال الأول، لا يتبقى شيء وتكون الإجابة
0. - استخدام كومة صغرى عن طريق الخطأ. تُرجع
heapqفي Python وPriorityQueueالافتراضية في Java أصغر قيمة؛ اعكس الأوزان أو مرّر مقارنًا عكسيًا. - نسيان الإشارة مع الأوزان المعكوسة. تكون القيمتان اللتان أُزيلتا سالبتين، لذا تكون القيمة التي يجب إضافتها هي
-(heaviest - second). - الترتيب مرة واحدة في البداية ثم المرور على القائمة. قد يكون الفرق أخف من أحجار لم تتعامل معها بعد، لذا يصبح الترتيب غير صالح بعد الجولة الأولى.
أسئلة شائعة3
ما هو التعقيد الزمني لـ Last Stone Weight؟
باستخدام كومة عظمى، تستغرق بحد أقصى n-1 جولة من عمليتي إزالة وعنصر إدخال واحد زمنًا قدره O(n log n) ومساحة قدرها O(n). أما فرز الكومة بأكملها في كل جولة فيستغرق O(n² log n).
لماذا نستخدم كومةً لمسألة Last Stone Weight بدلًا من قائمة مرتبة؟
تعطيك القائمة المرتبة أثقل حجرين دفعةً واحدة، لكن إعادة ترتيب القائمة بعد إضافة الفرق تُزحزح ما يصل إلى n من العناصر، بتعقيد O(n²) على امتداد جميع الجولات. لا تجيب الكومة إلا عن سؤال «ما القيمة الأكبر؟» وتقبل قيمة جديدة، وكلا الأمرين بتعقيد O(log n)، وهذا كل ما تتطلبه المحاكاة.
هل يؤدي ترتيب تحطيم الأوزان المتساوية إلى تغيير الإجابة؟
لا. عندما تتساوى عدة أحجار في الوزن الأثقل، فإن الحجرين اللذين تختارهما لهما الوزن نفسه في كلتا الحالتين، لذا تحتوي الكومة بعد الجولة على الأوزان نفسها. تعتمد الإجابة على الأوزان فقط.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def lastStoneWeight(stones):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
stones = [3, 9, 4, 6, 2]
الإخراج المتوقع
0