Remove K Digits
لديك عدد غير سالب مكتوب كسلسلة من الأرقام، num، وعدد صحيح k. احذف k أرقام بالضبط واحتفظ بالباقي بترتيبها الأصلي، بحيث يكون العدد المتبقي أصغر ما يمكن.
أعِده كسلسلة من دون أصفار بادئة. إذا لم يتبقَّ شيء، أو لم يتبقَّ سوى أصفار، فأعِد "0".
الدالة
- numstring
- العدد، مكتوبًا كسلسلة من الأرقام
- kinteger
- كم عدد الأرقام التي يجب حذفها
- تُرجعstring
- أصغر عدد يمكنك تركه كسلسلة نصية من دون أصفار بادئة
القيود
1 ≤ num.length ≤ 4 × 1040 ≤ k ≤ num.lengthnumيحتوي على الأرقام من0إلى9فقط.- لا يحتوي
numعلى أصفار بادئة، إلا إذا كان هو العدد صفرًا نفسه،"0".
أمثلة
- المدخلات
- num = "4325043"k = 3
- المخرجات
- "2043"
- الشرح
- يؤدي حذف الرقم 4 والرقم 3 الأول إلى وضع الرقم 2 في المقدمة. لا يمكن أن يأتي الرقم 0 في المقدمة: فهناك أربعة أرقام تسبقه، ولديك ثلاث عمليات حذف. تحذف العملية الأخيرة الرقم 5، الذي يقع قبل رقم 0 أصغر منه.
- المدخلات
- num = "30200"k = 1
- المخرجات
- "200"
- الشرح
- حذف الرقم 3 يترك
0200، ومن دون الصفر في بدايته يصبح200. أي حذف آخر يُبقي الرقم 3 في المقدمة ويترك عددًا من أربعة أرقام مثل3000.
- المدخلات
- num = "52"k = 2
- المخرجات
- "0"
- الشرح
- يُحذف الرقمان، فلا يتبقى شيء، وتكون الإجابة
"0".
سؤال إضافي
كيف ستغيّر الحل لإزالة k أرقام وترك أكبر عدد بدلاً من ذلك؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
كل طريقة لحذف
kمن الأرقام تترك العدد نفسه من الأرقام. بين عددين لهما الطول نفسه، يحدد أول موضع يختلفان فيه أيهما أصغر. ما الأرقام التي ينبغي أن تبذل قصارى جهدك لتصغيرها؟اقرأ الأرقام من اليسار. في أول مرة يكون فيها أحد الأرقام أكبر من الرقم الذي يليه مباشرةً، فإن حذفه يقلّل العدد عند أبكر موضع يمكن تقليله فيه. إذا لم تتناقص الأرقام أبدًا، فاحذف الرقم الأخير.
احتفِظ بالأرقام التي تقرر الإبقاء عليها في مكدس. قبل دفع رقم جديد إلى المكدس، أزل من أعلاه كل رقم أكبر ما دامت هناك عمليات إزالة متبقية. في النهاية، نفّذ من أعلى المكدس أي عمليات إزالة ما زالت متبقية، ثم احذف الأصفار البادئة.
الحل
الأرقام الموجودة في أقصى اليسار لها الوزن الأكبر، لذا يجب حذف أول رقم يكون أكبر من الرقم الذي يليه مباشرةً. ويُطبّق مكدس الأرقام التي تحتفظ بها هذه القاعدة على السلسلة بأكملها في تمريرة واحدة. وتُحذف عمليات الإزالة المتبقية في النهاية من الخلف، ثم تُزال الأصفار البادئة أخيرًا.
احذف رقمًا واحدًا في كل مرة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
احذف رقمًا واحدًا في كل مرة: اعثر على أول موضع i حيث num[i] > num[i+1] واحذف num[i]، أو احذف الرقم الأخير إذا لم تتناقص الأرقام أبدًا. كرر ذلك k مرة.
يحتفظ كل جواب بـ n-k أرقام، لذا فإن أول موضع يختلف فيه جوابان هو ما يحدد أيهما أصغر. حتى الموضع i، لا تتناقص الأرقام أبدًا، لذا فإن حذف رقم أسبق يُدخل رقمًا لا يقل عنه؛ أما حذف رقم لاحق فيُبقي num[i] الكبير في مكانه. حذف num[i] يخفض أول موضع يمكن خفضه.
تعيد كل عملية حذف الفحص من اليسار وتزيح الأرقام التي تليها، لذا يكون مقدار العمل O(n·k). عند التعامل مع 40,000 واحد ومع k = 25,000، تقرأ عمليات الفحص نحو 6.9 × 10^8 رقمًا.
الخوارزمية
- انسخ الأرقام إلى قائمة يمكنك الحذف منها.
- كرّر
kمرة: تحرّك من اليسار إلى أول رقم أكبر من الرقم الذي يليه، أو إلى الرقم الأخير، ثم احذفه. - أزل الأصفار البادئة، وأعِد
"0"إذا لم يتبقَّ شيء.
def removeKdigits(num, k):
digits = list(num)
for _ in range(k):
# Find the first digit that is bigger than the digit after it.
# If the digits never go down, i stops on the last digit.
i = 0
while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
i += 1
del digits[i]
result = "".join(digits).lstrip("0")
return result if result else "0"مكدّس رتيب للأرقام المُحتفَظ بها
الفكرة
بعد أن يحذف الإصدار البطيء num[i]، لا تزال الأرقام التي تسبق i لا تنخفض أبدًا، لذا لا يمكن أن يبدأ الانخفاض التالي إلا عند الرقم الذي يسبق الفجوة. يحتفظ المكدس بهذا الجزء السابق: الأرقام المُبقى عليها، مرتبة من الأسفل إلى الأعلى دون تناقص. عندما يكون الرقم الجديد أصغر من القمة، تكون القمة أكبر من جارتها على اليمين، أي الرقم الذي سيحذفه الإصدار البطيء. أزلها من المكدس، واستهلك عملية حذف، وواصل الإزالة ما دامت القمة الجديدة أكبر.
في 4325043 مع k = 3، يزيل الرقم 3 الرقم 4، ويزيل الرقم 2 الرقم 3، ويزيل الرقم 0 الرقم 5. يُضاف الرقمان 4 و3 إلى المكدس عند ورودهما، فنحصل على 2043.
يُضاف كل رقم إلى المكدس مرة واحدة، وكل إزالة تستهلك واحدة من عمليات الحذف k، لذا فإن المرور يستغرق O(n).
الخوارزمية
- أنشئ مكدسًا فارغًا من الأرقام.
- لكل رقم من
num: ما دامت هناك عمليات حذف متبقية وكان العنصر العلوي في المكدس أكبر من الرقم، أزل العنصر العلوي واستهلك عملية حذف واحدة. ثم أضف الرقم إلى المكدس. - إذا بقيت عمليات حذف بعد الحلقة، فأزل هذا العدد من الأرقام من أعلى المكدس.
- اقرأ المكدس من الأسفل إلى الأعلى، وتجاوز الأصفار البادئة، وأعِد الباقي، أو
"0"إذا لم يتبقَّ شيء.
def removeKdigits(num, k):
stack = [] # kept digits, never decreasing from bottom to top
for digit in num:
# A bigger digit right before a smaller one: dropping it makes the number smaller.
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# The kept digits never decrease, so any removals left come off the end.
stack = stack[:len(stack) - k]
result = "".join(stack).lstrip("0")
return result if result else "0"
أخطاء شائعة وحالات حدّية
- إزالة العنصر من المكدس عندما يساوي العنصر في قمته الرقم الجديد. في
112معk = 1، سيبقى12؛ والإجابة الصحيحة هي11. - نسيان عمليات الإزالة المتبقية بعد انتهاء الحلقة، أو إجراؤها من المقدمة. المكدس لا يتناقص أبدًا، لذا فإن آخر أرقامه ستكون:
123456789معk = 3يعطي123456. - احتساب الأصفار المحذوفة ضمن عمليات الإزالة. في
100200معk = 1، الرقم 1 هو العنصر الوحيد الذي يُزال؛ أما الأصفار في المقدمة فتُحذف مجانًا، وتكون الإجابة200. - إرجاع سلسلة فارغة. في
10معk = 1، لا يتبقى سوى صفر، لذا تكون الإجابة"0". - تحويل
numإلى عدد صحيح. قد يتكون من4 × 10^4رقمًا، وهو ما يتجاوز بكثير حدود أي نوع للأعداد الصحيحة، لذا قارِن الأرقام باعتبارها محارف.
أسئلة شائعة3
ما هو التعقيد الزمني لإزالة K من الأرقام؟
باستخدام مكدس رتيب، يعمل بزمن O(n) لعدد n من الأرقام: يُدفَع كل رقم مرة واحدة، وتستهلك كل عملية إزالة واحدة من عمليات الإزالة k. يحتوي المكدس على ما يصل إلى n من الأرقام، لذا فإن المساحة الإضافية هي O(n). إعادة المسح من اليسار لكل عملية إزالة تكلّف O(n·k).
كيف تتعامل مع الأصفار البادئة في مسألة إزالة K من الأرقام؟
احذف الأرقام أولًا، وأزل الأصفار في النهاية فقط. الصفر في البداية لا يغيّر القيمة، لذا لا يتطلب حذفه أي عملية حذف: يصبح 10200 مع k = 1 هو 0200 ثم 200. إذا لم يتبقَّ شيء بعد الإزالة، فأعِد "0".
هل يمكن حل مسألة إزالة K من الأرقام باستخدام مساحة إضافية قدرها O(1)؟
نعم، إذا كان بإمكانك تغيير الإدخال. لا يحتوي المكدس أبدًا على أرقام أكثر مما قرأته، لذا يمكن أن يشغل مقدمة مصفوفة الأرقام نفسها، مع فهرس واحد لقمته. تظل اللغات التي تستخدم سلاسل غير قابلة للتغيير بحاجة إلى نسخة واحدة من الأرقام، وهذا يتطلب O(n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def removeKdigits(num, k):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
num = "4325043" k = 3
الإخراج المتوقع
"2043"