Asteroid Collision
يتحرك صف من الكويكبات على خط مستقيم، وكلها بالسرعة نفسها. تصف كل قيمة في asteroids كويكبًا واحدًا: فقيمتها المطلقة تمثل حجمه، وإشارتها تمثل اتجاهه؛ فالقيمة الموجبة تعني الاتجاه إلى اليمين، والسالبة تعني الاتجاه إلى اليسار.
عندما يلتقي كويكب متحرك إلى اليمين بآخر متحرك إلى اليسار، يتصادمان. ينفجر الأصغر؛ وإذا كانا بالحجم نفسه، ينفجر كلاهما. الكويكبات التي تتحرك في الاتجاه نفسه لا تلتقي أبدًا. أعد الكويكبات المتبقية بعد كل التصادمات، بترتيبها الأصلي. قد تكون النتيجة فارغة.
الدالة
- asteroidsinteger-array
- الكويكبات من اليسار إلى اليمين، وإشارة للاتجاه، والقيمة المطلقة للحجم
- تُرجعinteger-array
- الكويكبات المتبقية من اليسار إلى اليمين، وربما لا يتبقى أيٌّ منها
القيود
1 ≤ asteroids.length ≤ 104-1000 ≤ asteroids[i] ≤ 1000asteroids[i] ≠ 0
أمثلة
- المدخلات
- asteroids = [4, 9, -6, 2, -3]
- المخرجات
- [4, 9]
- الشرح
- يلتقي 9 بـ -6 ويفوز. يلتقي 2 بـ -3 وينفجر، ثم يطير -3 نحو 9 وينفجر أيضًا. لا يتحرك أي شيء آخر نحو أي شيء، لذا يتبقى 4 و9.
- المدخلات
- asteroids = [6, -6]
- المخرجات
- []
- الشرح
- يتطابق حجما 6 و-6، لذا ينفجر كلاهما وتكون النتيجة فارغة.
- المدخلات
- asteroids = [-2, -7, 3, 8]
- المخرجات
- [-2, -7, 3, 8]
- الشرح
- يطير -2 و-7 إلى اليسار، ويطير 3 و8 إلى اليمين، لذا تبتعد المجموعتان عن بعضهما. لا يحدث أي تصادم على الإطلاق، وتنجو الكويكبات الأربعة كلها.
سؤال إضافي
يُحدّد المكدّس الكويكبات التي تنجو. كيف يمكنك أيضًا الإبلاغ، لكل كويكب ينفجر، عن فهرس الكويكب الذي دمّره؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يتطلب الاصطدام جسماً متحركاً إلى اليمين على اليسار، وجسماً متحركاً إلى اليسار على اليمين. الكويكب المتحرك إلى اليسار، الذي لا يسبقه أي جسم متحرك إلى اليمين، يظل آمناً إلى الأبد. امشِ على الصف من اليسار إلى اليمين: أيّ الكويكبات السابقة لا يزال بإمكان جسم جديد متحرك إلى اليسار الاصطدام بها؟
يصطدم المتحرك الجديد نحو اليسار بأقرب متحرك باقٍ نحو اليمين أولًا، ثم بالذي يليه، وهكذا، حتى ينفجر أو تنفد المتحركات نحو اليمين. يتصرف الناجون حتى الآن مثل المكدس: لا يمكن أن يُصاب بعد ذلك إلا الأحدث.
احتفظ بالناجين في مكدّس. أضف كل جسم متحرك نحو اليمين إلى المكدّس. بالنسبة إلى الجسم المتحرك نحو اليسار، أزل العناصر من المكدّس ما دام العنصر في القمة جسمًا أصغر متحركًا نحو اليمين. إذا كان العنصر في القمة جسمًا متحركًا نحو اليمين بالحجم نفسه، فأزله وتخلّص من الجسم الجديد. إذا كان العنصر في القمة أكبر، فتخلّص من الجسم الجديد. وإلا فأضِفه إلى المكدّس.
الحل
يمكن لجسم متحرك نحو اليسار أن يدمّر سلسلة طويلة من الأجسام المتحركة نحو اليمين، وقد يكشف كل تصادم عن زوج جديد يتصادم بعد ذلك. يلتقي جسم كويكبي جديد دائمًا بأحدث جسم ناجٍ أولًا، لذا يحسم مكدّس الأجسام الناجية كل تصادم في مرور واحد.
عالج عطلاً واحدًا في كل مرة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
يتصادم كويكبان بالضبط عندما يكون كويكب متحرك إلى اليمين مباشرةً على يسار كويكب متحرك إلى اليسار. اعثر على أول زوج من هذا النوع، وعالج تصادمه، ثم امسح الصف مجددًا بدءًا من اليسار. عندما لا يتبقى أي زوج، لن يحدث أي تصادم بعد ذلك، ويكون الصف هو الإجابة.
لا يهم ترتيب معالجة التصادمات: فكل كويكبين متجاورين ومتقابلين سيتصادمان قبل أن يتمكن أي منهما من الاصطدام بأي شيء آخر.
كل تصادم يتطلب مسحًا جديدًا وإزالة عنصر من وسط الصف. مع وجود 9,999 كويكبًا صغيرًا متحركًا إلى اليمين، يتبعها -1000، يمر كل مسح على الصف لتدمير كويكب واحد متحرك إلى اليمين: حوالي 5 × 10^7 خطوة.
الخوارزمية
- انسخ الصف حتى تتمكن من إزالة الكويكبات منه.
- امسح من اليسار بحثًا عن أول فهرس
iحيثrow[i] > 0وrow[i+1] < 0. - إذا لم يوجد أيٌّ منها، فأعِد الصف.
- وإلا فأزل الأصغر من الاثنين، أو كليهما إذا كان حجماهما متساويين، ثم امسح مجددًا.
def asteroidCollision(asteroids):
row = list(asteroids)
while True:
# A crash happens where a right-mover is directly followed by a left-mover.
hit = -1
for i in range(len(row) - 1):
if row[i] > 0 and row[i + 1] < 0:
hit = i
break
if hit == -1:
return row
right, left = row[hit], -row[hit + 1]
if right > left:
del row[hit + 1]
elif right < left:
del row[hit]
else:
del row[hit:hit + 2]كومة الناجين
الفكرة
احتفظ بالناجين حتى الآن في مكدس. لا يمكن أن يحتوي أبدًا على جسم متحرك إلى اليمين يتبعه جسم متحرك إلى اليسار، لأن هذا الزوج يكون قد اصطدم بالفعل؛ لذا فهو يتكوّن من أجسام متحركة إلى اليسار نجت، تليها أجسام متحركة إلى اليمين.
يبتعد جسم جديد متحرك إلى اليمين عن كل ما في المكدس، لذا تضيفه إليه. أما الجسم الجديد المتحرك إلى اليسار فيتجه نحو الأجسام المتحركة إلى اليمين في الأعلى، ويقابل الأحدث منها أولًا، لذا فإن العنصر الأعلى هو الجسم الفلكي الوحيد الذي يمكن أن يصطدم به بعد ذلك. في المثال الأول، يزيل -3 العنصر 2 من المكدس، ثم ينفجر عند اصطدامه بـ 9، وتكون إجابة المكدس [4, 9] بترتيبها الأصلي.
يُضاف كل جسم فلكي إلى المكدس مرة واحدة على الأكثر ويُزال منه مرة واحدة على الأكثر، لذا فإن المرور يستغرق O(n) حتى عندما يزيل جسم متحرك إلى اليسار سلسلة طويلة.
الخوارزمية
- ابدأ بمكدس فارغ للنجاة.
- لكل كويكب، إذا كان يتحرك إلى اليمين، فأضِفه إلى المكدس وتابع.
- إذا كان يتحرك إلى اليسار، فأزِل من الأعلى الكويكبات المتحركة إلى اليمين ما دامت أصغر منه.
- إذا كان العنصر في الأعلى الآن يتحرك إلى اليمين وبالحجم نفسه، فأزِله وتخلّص من الكويكب الجديد. إذا كان العنصر في الأعلى كويكبًا أكبر يتحرك إلى اليمين، فتخلّص من الكويكب الجديد. وإلا فأضِفه إلى المكدس.
- أعِد المكدس من الأسفل إلى الأعلى.
def asteroidCollision(asteroids):
survivors = [] # the row so far, after every crash it caused
for rock in asteroids:
alive = True
# Only a left-mover can hit something: a right-mover on top of the stack.
while alive and rock < 0 and survivors and survivors[-1] > 0:
top = survivors[-1]
if top < -rock:
survivors.pop() # the right-mover is smaller and explodes
elif top == -rock:
survivors.pop() # same size: both explode
alive = False
else:
alive = False # the right-mover is bigger: the new one explodes
if alive:
survivors.append(rock)
return survivors
أخطاء شائعة وحالات حدّية
- اعتبار جسم متحرك إلى اليسار يتبعه جسم متحرك إلى اليمين تصادمًا. في
[-2, -7, 3, 8]تبتعد المجموعتان عن بعضهما وينجو الأربعة جميعًا. - استخدام
ifبدلًا منwhileلعمليات الإزالة. في[1, 2, 3, 4, 5, -15]يدمّر الجسم المتحرك إلى اليسار الأجسام الخمسة المتحركة إلى اليمين وينجو. - إغفال حالة التساوي. يجب أن تُزيل
[6, -6]القيمة 6 وتتخلّص من القيمة -6، لتكون النتيجة فارغة. - إضافة جسم متحرك إلى اليسار خسر إلى المكدس. في
[9, -6]ينفجر -6، ويجب ألا يُضاف إلى المكدس؛ احتفظ بمتغيّر يبيّن ما إذا كان لا يزال حيًا.
أسئلة شائعة3
ما التعقيد الزمني لتصادم الكويكبات؟
زمن O(n) ومساحة O(n) باستخدام مكدس للناجين، لأن كل كويكب يُضاف إلى المكدس ويُزال منه مرة واحدة على الأكثر. إعادة فحص الصف بعد كل تصادم تكلّف O(n²).
لماذا تُعدّ المكدّسة بنية البيانات المناسبة لمسألة تصادم الكويكبات؟
لا يمكن لكويكب جديد أن يصل إلا إلى الناجين الأقرب إليه، ويصادفهم من الأحدث إلى الأقدم. وهذا يعني أن آخر ما يدخل هو أول ما يخرج. وما يبقى على المكدس في النهاية لا يمكن أن يصطدم بعد ذلك، لذا فهو الصف النهائي.
هل يمكن حلّ تصادم الكويكبات بمساحة إضافية قدرها O(1)؟
نعم، إذا كان بإمكانك الكتابة فوق المدخلات. استخدم مقدمة المصفوفة كمكدس: احتفظ بمؤشر كتابة top، وقارن مع asteroids[top-1]، وأعِد أول top عناصر.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def asteroidCollision(asteroids):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
asteroids = [4, 9, -6, 2, -3]
الإخراج المتوقع
[4, 9]