Baseball Game

Q: هل يمكن حل مسألة لعبة البيسبول باستخدام مساحة إضافية مقدارها O(1)؟

ليس بشكل عام. سلسلة من الأرقام تتبعها سلسلة من القيم "C" تلغيها بترتيب عكسي، لذا يجب أن تحتفظ بكل رقم إلى أن تعرف ما إذا كان سيُلغى. وهذا يتطلب ذاكرة O(n) في أسوأ الحالات. المجموع التراكمي يوفّر المرور النهائي، لا المكدس.

Q: كيف تميّز بين الرقم والعملية في لعبة البيسبول؟

قارن الإدخال بالرموز الثلاثة "+" و "D" و "C" أولًا، واعتبر أي شيء آخر عددًا صحيحًا. يتعامل المحلّل الخاص باللغة مع إشارة السالب في البداية عند التحويل، لذا تصبح "-30000" القيمة -30000 .

سهلالمكدس

+10

أنت تحسب النقاط في لعبة غير مألوفة. تُقرأ القائمة operations من اليسار إلى اليمين، وتغيّر كل خانة فيها سجلّ النقاط. يضيف عدد صحيح مثل "7" أو "-2" هذه النقاط إلى السجل. تضيف "+" نقاطًا تساوي مجموع أحدث نقطتين، وتضيف "D" نقاطًا تساوي ضعف أحدث نقطة، وتحذف "C" أحدث نقطة من السجل نهائيًا.

اكتب دالة باسم calPoints تُرجع مجموع النقاط المتبقية في السجل بعد آخر عملية. مجموع السجل الفارغ هو 0.

الدالة

calPoints(operations: string-array) → integer

operationsstring-array: العمليات بالترتيب: أعداد صحيحة كنص، أو "+"، أو "D"، أو "C"
تُرجعinteger: مجموع النقاط التي لا تزال مسجّلة في النهاية

القيود

1 ≤ operations.length ≤ 5000
كل إدخال هو "+" أو "D" أو "C" أو عدد صحيح مكتوب بالنظام العشري بحيث -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
كل عملية صالحة: لا تأتي "+" إلا عندما يحتوي السجل على درجتين على الأقل، ولا يأتي "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.

+13 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك إرجاع المجموع دون جمع السجل في النهاية، بحيث تستغرق كل عملية، بما فيها الإلغاء، زمنًا O(1)؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

تنظر كل عملية إلى أحدث النتائج، ويمكن لـ "C" إزالة النتائج واحدةً تلو الأخرى، لذا تصبح النتائج التي سبقت النتيجة الملغاة هي الأحدث مجددًا. هذا النمط، الذي يدخل فيه الأخير أولًا ويخرج أولًا، هو بالضبط المكدّس. أضف كل نتيجة جديدة إلى المكدّس، وأزل النتيجة الأخيرة عند "C"، واقرأ أحد المدخلين العلويين أو كليهما من أجل "D" و"+".

أنشئ السجل على مكدس، واجمعه في النهاية

الفكرة

احتفظ بالسجل على هيئة قائمة، بحيث تكون أحدث نتيجة في نهايتها. عندئذٍ، لا تلمس كل عملية إلا نهاية القائمة: يُضاف عدد صحيح، وتضيف "D" ضعف آخر عنصر، وتضيف "+" مجموع آخر عنصرين، وتحذف "C" آخر عنصر.

لماذا تكفي المكدسة: بعد "C"، تصبح النتيجة التي كانت ثاني أحدث نتيجة هي الأحدث، وهي التي يجب أن تقرأها عملية "D" أو "+" التالية. يوفّر لك الحذف ذلك تلقائيًا. في المثال الأول، تحذف "C" القيمة -6 وتُبقي [4, -2, -4]، لذا فإن أي عملية "+" لاحقة ستجمع -2 + -4 مرة أخرى.

عند نفاد العمليات، تحتوي القائمة على النتائج التي تُحتسب بالضبط. اجمعها. تستغرق كل عملية O(1)، ويستغرق المجموع النهائي O(n)، لذا يستغرق التنفيذ بأكمله 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 يساوي دائمًا مجموع المكدس. كل عملية دفع تضيف النتيجة الجديدة إلى total، وكل "C" تطرح النتيجة التي تسحبها.

ما زلت بحاجة إلى المكدس. يجب أن تعرف عملية الإلغاء أي نتيجة تزيلها من المجموع، كما يجب أن تعرف "+" و"D" أحدث النتائج بعد أي عمليات إلغاء. في المثال الأول، ينتقل المجموع إلى 4, 2, -2, -8، ثم تعيد عملية الإلغاء إضافة -6 إلى المجموع، فيصبح -2، وتوصله النتيجة النهائية 7 إلى 5.

التعقيد الزمني هو O(n) بتمريرة واحدة، وتكون الإجابة جاهزة بعد أي بادئة من العمليات، وهذا مهم عندما تصل النتائج مباشرةً. التعقيد المكاني هو O(n): فقد تكون العمليات الـ 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

أخطاء شائعة وحالات حدّية

القواعد قصيرة، لذا فإن معظم الأخطاء تنتج عن قراءة الدرجة الخاطئة أو تحليل النص.

الاحتفاظ بمجموع جارٍ وبآخر درجتين فقط. بعد "C"، تحتاج إلى الدرجة التي تسبق هاتين الدرجتين، لذا فإن الإلغاء الذي يتبعه "+" يقرأ قيماً قديمة. احتفظ بالمكدس بأكمله.
نسيان أن الدرجات الملغاة تُحذف من المجموع. عند استخدام مجموع جارٍ، يجب أن تطرح "C" الدرجة التي أُزيلت من المكدس، لا أن تتجاهلها.
تحليل الدرجات السالبة يدوياً وإسقاط الإشارة. استخدم محلل الأعداد الصحيحة الخاص باللغة، الذي يقرأ "-2" على أنها -2.
التحقق من وجود رقم لتحديد ما إذا كان الإدخال عدداً. تبدأ "-5" بإشارة ناقص؛ اختبر الرموز الثلاثة، واعتبر كل ما عداها عدداً.
افتراض أن الإجابة موجبة. قد تؤدي الدرجات السالبة والإلغاءات إلى مجموع سالب، أو 0 عندما تكون كل الدرجات قد أُلغيت.

أسئلة شائعة4

ما هو التعقيد الزمني للعبة البيسبول؟

تنفّذ كل عملية مقدارًا ثابتًا من العمل على قمة المكدس، لذا فإن معالجة n عملية تستغرق زمنًا قدره O(n). ويستغرق جمع قيم المكدس في النهاية O(n) على الأكثر، كما أن الاحتفاظ بمجموع جارٍ يلغي حتى ذلك. ويستخدم المكدس مساحة O(n) عندما تضيف معظم العمليات درجات.

لماذا تُعدّ المكدسة بنية البيانات المناسبة للعبة البيسبول؟

تقرأ كل قاعدة أحدث النقاط أو تزيلها، ويُظهر الإلغاء النقاط التي سبقتها. هذا هو ترتيب «الأخير يدخل، الأول يخرج»، وهو ما توفره المكدّسة باستخدام عمليات الإضافة والإزالة والاطلاع بزمن O(1). ويمكن استخدام مصفوفة أو قائمة عادية من طرفها فقط كمكدّسة في أي لغة.

هل يمكن حل مسألة لعبة البيسبول باستخدام مساحة إضافية مقدارها O(1)؟

ليس بشكل عام. سلسلة من الأرقام تتبعها سلسلة من القيم "C" تلغيها بترتيب عكسي، لذا يجب أن تحتفظ بكل رقم إلى أن تعرف ما إذا كان سيُلغى. وهذا يتطلب ذاكرة O(n) في أسوأ الحالات. المجموع التراكمي يوفّر المرور النهائي، لا المكدس.

كيف تميّز بين الرقم والعملية في لعبة البيسبول؟

قارن الإدخال بالرموز الثلاثة "+" و"D" و"C" أولًا، واعتبر أي شيء آخر عددًا صحيحًا. يتعامل المحلّل الخاص باللغة مع إشارة السالب في البداية عند التحويل، لذا تصبح "-30000" القيمة -30000.

Python

def calPoints(operations):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

operations = ["4", "-2", "D", "+", "C", "7"]

المتوقع