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