Baseball Game
تحتفظ بنتيجة لعبة غير مألوفة. اقرأ operations من اليسار إلى اليمين؛ فكل إدخال يغيّر سجلًّا للنتائج. يضيف عدد صحيح مثل "7" أو "-2" تلك النتيجة. يضيف "+" مجموع أحدث نتيجتين، ويضيف "D" ضعف أحدث نتيجة، بينما يحذف "C" أحدث نتيجة نهائيًا.
اكتب دالة باسم calPoints تُعيد مجموع النتائج المتبقية في السجل بعد آخر عملية. مجموع السجل الفارغ هو 0.
الدالة
- operationsstring-array
- العمليات بالترتيب: أعداد صحيحة كنص، أو «+» أو «D» أو «C»
- تُرجعinteger
- مجموع النقاط التي لا تزال مسجلة في النهاية
القيود
1 ≤ operations.length ≤ 5000- كل مُدخل هو
"+"أو"D"أو"C"أو عدد صحيح مكتوب بالنظام العشري بحيث-3 × 104 ≤ value ≤ 3 × 104. - كل عملية صالحة: لا تأتي
"+"إلا عندما يحتوي السجل على درجتين على الأقل، ولا يأتي"D"و"C"إلا عندما يحتوي على درجة واحدة على الأقل. - كل نتيجة في السجل والمجموع النهائي يقعان ضمن نطاق عدد صحيح موقّع ذي 32 بت.
أمثلة
- المدخلات
- operations = ["4", "-2", "D", "+", "C", "7"]
- المخرجات
- 5
- الشرح
- يزداد السجل إلى
[4, -2]، وتضيف"D"القيمة-4، وتضيف"+"القيمة-2 + -4 = -6، وتحذف"C"تلك القيمة-6، ويأتي7أخيرًا. مجموع السجل[4, -2, -4, 7]هو5.
- المدخلات
- operations = ["6", "D", "C", "C"]
- المخرجات
- 0
- الشرح
- تضيف
"D"القيمة12بعد6، ثم يحذف الإدخالان"C"القيمتين12و6. لا يتبقى شيء، لذا تكون الإجابة0.
- المدخلات
- operations = ["1", "2", "+", "+", "D"]
- المخرجات
- 21
- الشرح
- تجمع الإدخالان
"+"القيمتين1 + 2 = 3ثم2 + 3 = 5، ويضيف"D"القيمة10. مجموع السجل[1, 2, 3, 5, 10]هو21.
سؤال إضافي
كيف ستضيف عمليةً تتراجع عن أحدث "C"، فتعيد النتيجة الملغاة، بزمن O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تتحدث كل قاعدة عن أحدث نتيجة أو أحدث نتيجتين. ماذا ينبغي أن يحدث لأحدث نتيجة عندما تحذفها
"C"؟بعد الإلغاء، تصبح الدرجة التي سبقت الدرجة المحذوفة هي الأحدث مجددًا. تُزال الدرجات بترتيب عكسي لترتيب إضافتها، وهذا هو سلوك المكدس.
أضِف كل نتيجة جديدة إلى مكدس: العدد نفسه، أو ضعف العنصر الأعلى في المكدس عند
"D"، أو مجموع أعلى عنصرين عند"+". أزِل عنصرًا من المكدس عند"C". في النهاية، أعد مجموع العناصر المتبقية، أو حافظ على تحديث هذا المجموع أثناء الإضافة والإزالة من المكدس.
الحل
تقرأ كل عملية أحدث الدرجات، ويمكن لـ "C" إزالتها واحدة تلو الأخرى، فتعود الدرجات الأقدم لتصبح الأحدث. هذا هو مبدأ «الأخير دخولًا، الأول خروجًا»: أضف كل درجة جديدة، وأزل درجة عند "C"، واقرأ الدرجة العليا أو الدرجتين العلويتين عند "D" و"+".
أنشئ السجل على مكدس، واجمعه في النهاية
الفكرة
احتفظ بالسجل في قائمة، مع وضع أحدث نتيجة في النهاية، بحيث تتعامل كل عملية مع النهاية فقط. بعد "C" تصبح النتيجة الأحدث الثانية هي الأحدث، ويجب أن تقرأها عملية لاحقة "D" أو "+"؛ إذ يكشفها حذف العنصر الأخير. في المثال الأول، تحذف "C" القيمة -6 وتُبقي على [4, -2, -4].
عند انتهاء العمليات، تحتوي القائمة على النتائج التي تُحتسب بالضبط، لذا اجمعها: زمن O(n) ومساحة O(n).
الخوارزمية
- ابدأ بمكدس فارغ
record. - بالنسبة إلى
"+"، ادفع مجموع العنصرين العلويين. وبالنسبة إلى"D"، ادفع ضعف العنصر العلوي. - بالنسبة إلى
"C"، أزل العنصر العلوي. - وإلا، فالعنصر عدد: حوّل النص إلى عدد صحيح وادفعه.
- أعِد مجموع كل ما تبقى في المكدس.
def calPoints(operations):
record = [] # the scores that still count, newest last
for op in operations:
if op == "+":
record.append(record[-1] + record[-2])
elif op == "D":
record.append(2 * record[-1])
elif op == "C":
record.pop()
else:
record.append(int(op))
return sum(record)مكدس مع إجمالي جارٍ
الفكرة
أبقِ total مساويًا لمجموع المكدّس: كل عملية دفع تضيف الدرجة الجديدة، وكل "C" تطرح الدرجة التي تُخرجها. يجب أن يبقى المكدّس، لأن الإلغاء يحتاج إلى معرفة الدرجة التي يجب إخراجها. في المثال الأول، يتغير المجموع إلى 4, 2, -2, -8، وتُخرج عملية الإلغاء -6 ليعود المجموع إلى -2، ثم ترفعه 7 إلى 5.
تُنفَّذ هذه العملية بمرور واحد في زمن O(n)، وتكون الإجابة جاهزة بعد أي بادئة من العمليات. المساحة هي O(n)، إذ يمكن أن تكون كل عملية رقمًا يبقى في المكدّس.
الخوارزمية
- ابدأ بمكدس فارغ
recordوtotal = 0. - عند
"C"، أخرج الدرجة العليا واطرحها منtotal. - وإلا، احسب الدرجة الجديدة: مجموع الدرجتين العلويتين عند
"+"، أو ضعف الدرجة العليا عند"D"، أو العدد الصحيح نفسه. - أضف الدرجة الجديدة إلى المكدس وأضفها إلى
total. - أعِد
total.
def calPoints(operations):
record = [] # the scores that still count, newest last
total = 0 # always the sum of record
for op in operations:
if op == "C":
total -= record.pop() # the cancelled score leaves the total too
continue
if op == "+":
score = record[-1] + record[-2]
elif op == "D":
score = 2 * record[-1]
else:
score = int(op)
record.append(score)
total += score
return total
أخطاء شائعة وحالات حدّية
- الاحتفاظ بالمجموع الجاري وآخر نتيجتين فقط. في
["1", "2", "3", "C", "+"]، تحتاج"+"إلى1و2، وقد أُسقطت1من نافذة النتائج الاثنتين. - عدم طرح النتيجة الملغاة من المجموع الجاري. في المثال الثاني، يؤدي ذلك إلى بقاء
18بدلًا من0. - تحديد أن الإدخال عدد من خلال التحقق من وجود رقم فيه. تبدأ
"-2"بعلامة ناقص؛ قارن بين الرموز الثلاثة وحلّل كل ما عداها باستخدام محلّل الأعداد الصحيحة في اللغة. - افتراض أن الإجابة موجبة. مجموع
["-3", "D"]هو-9.
أسئلة شائعة3
ما التعقيد الزمني للعبة البيسبول؟
تنفّذ كل عملية عملاً ثابتًا على قمة المكدّس، لذا تستغرق n عملية زمنًا قدره O(n). ويستهلك المكدّس مساحة قدرها O(n) عندما تضيف معظم العمليات درجات.
لماذا تُعدّ المكدسة بنية البيانات المناسبة للعبة البيسبول؟
تقرأ كل قاعدة أحدث النقاط أو تزيلها، ويُظهر الإلغاء النقطة التي قبلها. وهذا يعني أن آخر ما يدخل هو أول ما يخرج، وهو ما تتيحه المكدّسة عبر عمليتي الدفع والإزالة ومعاينة القمة بزمن O(1). ويمكن استخدام مصفوفة كمكدّسة إذا اقتصر استخدامها على نهايتها.
هل يمكن حل لعبة البيسبول بمساحة إضافية O(1)؟
ليس بشكل عام. فمجموعة من الأعداد تتبعها مجموعة من إدخالات "C" تلغيها بترتيب عكسي، لذا يجب أن تحتفظ بكل عدد حتى تعرف ما إذا كان سيُلغى. وهذا يتطلب ذاكرة O(n) في أسوأ الحالات.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def calPoints(operations):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
operations = ["4", "-2", "D", "+", "C", "7"]
الإخراج المتوقع
5