Plus One
يُخزَّن عدد صحيح غير سالب على هيئة مصفوفة من أرقامه العشرية، digits، بدءًا بالرقم الأكثر أهمية: 472 هو [4, 7, 2]. أضف واحدًا إلى العدد وأعِد أرقام الناتج بالصيغة نفسها. يمكن أن يتكوّن العدد من 100 رقم، وهو أكثر بكثير مما يتسع له عدد صحيح من 64 بت.
الدالة
- digitsinteger-array
- أرقام العدد، بدءًا من الأكثر أهمية
- تُرجعinteger-array
- أرقام العدد زائد واحد، بدءًا من الرقم الأكثر أهمية
القيود
1 ≤ digits.length ≤ 1000 ≤ digits[i] ≤ 9digitsلا يحتوي على أصفار بادئة، باستثناء العدد 0 نفسه، والذي يكون[0].
أمثلة
- المدخلات
- digits = [4, 3, 9]
- المخرجات
- [4, 4, 0]
- الشرح
- العدد هو 439، و439 + 1 = 440. يتحول الرقم الأخير 9 إلى 0 وينقل واحدًا إلى الرقم 3، فيصبح 4.
- المدخلات
- digits = [9, 9]
- المخرجات
- [1, 0, 0]
- الشرح
- 99 + 1 = 100. يتحول الرقمان 9 إلى 0، ويصبح الحمل المتبقي رقمًا جديدًا في المقدمة، لذا تكون الإجابة أطول برقم واحد من المدخل.
- المدخلات
- digits = [0]
- المخرجات
- [1]
- الشرح
- يُكتب العدد 0 على النحو
[0]، و0 + 1 = 1.
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
كيف يمكنك طرح واحد بدلًا من ذلك، لعدد لا يقل عن 1؟ أيّ الأرقام تتغير، ومتى تفقد النتيجة رقمها الأول، كما في [1, 0, 0]؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
قد يتكوّن العدد من 100 رقم، وهو عدد كبير جدًا بحيث لا يمكن لأي عدد صحيح مضمّن استيعابه. أجرِ عملية الجمع على الأرقام، كما تفعل عند الجمع على الورق. أين تضع الرقم 1 أولًا؟
إضافة 1 إلى رقم أقل من 9 لا تُحدث أي حمل، لذا لا يتغير شيء على يساره. الرقم 9 وحده يتحول إلى 0 وينقل الحمل إلى الرقم التالي.
ابدأ من الرقم الأخير واتجه إلى اليسار. حوّل كل 9 إلى 0؛ وعند أول رقم أقل من 9، أضف إليه واحدًا ثم أعد النتيجة. إذا لم تجد أي رقم، فهذا يعني أن جميع الأرقام كانت 9: الإجابة هي 1 متبوعًا بأصفار.
الحل
يفشل هنا تحويل الأرقام إلى عدد، ثم إضافة واحد إليه وتحويله مرة أخرى: فالأعداد المكوّنة من 100 رقم تتجاوز سعة كل عدد صحيح من 64 بت، التي تقف عند نحو 1.8 × 10^19. لذا أجرِ عملية الجمع كما تفعل على الورق، بدءًا من الرقم الأخير مع الاحتفاظ بواحد. والملاحظة الوحيدة التي تختصر العمل: إضافة 1 تغيّر التسعات المتتالية في النهاية فقط، فتحوّلها إلى أصفار، وتغيّر أول رقم يقع إلى يسارها. أما كل رقم آخر فيبقى كما هو.
الجمع مع الحمل، رقمًا رقمًا
الفكرة
اكتب العدد وأضف 1 تحت آخر رقم فيه، كما تفعل في المدرسة. ابدأ بحمل مقداره 1، وهو الواحد الذي تضيفه. عند كل رقم بدءًا من اليمين، يكون مجموع العمود هو الرقم مضافًا إليه الحمل. يوضع رقمه الأخير، total % 10، في الناتج، ويكون رقم العشرات فيه، total / 10، هو الحمل للعمود التالي.
مع حمل مقداره 1، لا يتجاوز مجموع العمود 9 + 1 = 10، لذا يكون الحمل دائمًا 0 أو 1. إذا بقي حمل بعد الرقم الأول، يُضاف إلى الناتج رقم جديد في بدايته: يحتاج 999 + 1 إلى خانة رابعة للرقم 1 في 1000.
يظهر الناتج بدءًا من الرقم الأخير، لأن هذا هو ترتيب حسابك له. اجمع الأرقام بهذا الترتيب ثم اعكسها في النهاية. يستغرق هذا O(n) من الوقت، ويتطلب مصفوفة جديدة تحتوي على ما يصل إلى n + 1 رقمًا.
الخوارزمية
- اجعل قيمة
carryتساوي 1 وابدأ قائمة فارغة للإجابة. - لكل رقم، من الأخير إلى الأول، احسب
total = digit + carry. - أضف
total % 10إلى الإجابة، واجعل قيمةcarryتساويtotal / 10، مع التقريب إلى الأسفل. - بعد الحلقة، إذا كانت قيمة
carryتساوي 1، فأضِفها. - اعكس الإجابة وأعِدها.
def plusOne(digits):
result = [] # the answer, last digit first
carry = 1 # the one you are adding
for i in range(len(digits) - 1, -1, -1):
total = digits[i] + carry
result.append(total % 10)
carry = total // 10
if carry > 0:
result.append(carry)
result.reverse()
return resultتوقّف عند أول رقم أقل من 9
الفكرة
لاحظ ما يحدث للحمل عندما تضيف 1 بالضبط. يستوعب الرقم الأقل من 9 الحمل: يصبح 3 هو 4، ويصبح الحمل 0، وتحتفظ كل الأرقام الواقعة إلى يساره بقيمتها. أما الرقم 9 وحده فيمرر الحمل، إذ يتحول إلى 0. لذا فإن إضافة 1 تعني: حوّل أرقام 9 المتتالية في النهاية إلى 0، ثم أضف 1 إلى الرقم الذي يسبقها مباشرةً.
تحرّك من الرقم الأخير نحو اليسار. عند الوصول إلى 9، اكتب 0 وتابع. عند الوصول إلى أي رقم آخر، زد قيمته بمقدار واحد وأعِد المصفوفة فورًا، إذ لا يمكن لأي رقم يقع إلى يساره أن يتغير. في [2, 9, 0, 9] يصبح الـ9 الأخير 0، ويصبح الـ0 هو 1، وتتوقف عند [2, 9, 1, 0] من دون النظر إلى أول رقمين.
إذا لم تعثر الحلقة على أي رقم أقل من 9، فهذا يعني أن كل الأرقام كانت 9 وأصبحت الآن 0. كان العدد 10^n - 1، لذا تكون الإجابة 1 يتبعه n من الأصفار. هذه هي الحالة الوحيدة التي تحتاج إلى مصفوفة جديدة. في جميع الحالات الأخرى، تغيّر المُدخل في مكانه، لذا تكون المساحة الإضافية O(1)، وتعمل الحلقة مرة واحدة لكل 9 متتالية في النهاية، بالإضافة إلى خطوة أخرى.
الخوارزمية
- انتقل عبر الفهارس من الأخير إلى الأول.
- إذا كان الرقم أقل من 9، فزِده بمقدار واحد وأعِد المصفوفة.
- وإلا، فالرقم هو 9: اجعله 0 وانتقل خانة واحدة إلى اليسار.
- إذا انتهت الحلقة، فهذا يعني أن كل الأرقام كانت 9: أعِد 1 متبوعًا بـ
nمن الأصفار.
def plusOne(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1 # no carry leaves this digit, so the rest stays as it is
return digits
digits[i] = 0 # 9 + 1 = 10: write 0 and carry one to the left
# Every digit was 9: the answer is 1 followed by zeros.
return [1] + digits
أخطاء شائعة وحالات حدّية
من المزالق تجاوز سعة الأعداد الصحيحة وحالة كون جميع الأرقام 9.
- تحويل المصفوفة إلى عدد صحيح ثم إعادتها إلى مصفوفة. ينجح هذا مع الاختبارات الصغيرة، ثم يفشل مع الأعداد المكوّنة من 100 رقم: فالعدد الصحيح ذي 64 بتًا يتسع لـ 19 أو 20 رقمًا على الأكثر، كما أن أعداد الفاصلة العائمة تفقد الأرقام الأخيرة قبل ذلك.
- نسيان الرقم الإضافي. يجب أن تصبح
[9, 9, 9][1, 0, 0, 0]، أي أربعة أرقام. أما الشيفرة التي تعيد كتابة الخانات الموجودة فقط فتعيد[0, 0, 0]. - إضافة 1 إلى الرقم الأول بدلًا من الأخير. المصفوفة مرتبة من الرقم الأكثر أهمية إلى الأقل أهمية، لذا يقع رقم الآحاد في النهاية.
- نسيان الإرجاع بعد أن يمتص رقم أقل من 9 الحمل. في النسخة التي تنهي التنفيذ مبكرًا، تستمر الحلقة وتغيّر أرقامًا يجب أن تبقى كما هي. في
[1, 9, 3]لا يجوز تغيير سوى الرقم 3؛ والإجابة هي[1, 9, 4]. - الخلط بين ترتيب الفهارس في Lua وR، حيث تبدأ فهارس المصفوفات من 1: يقع الرقم الأخير عند الفهرس
n، ويوضع الرقم 1 الجديد في المقدمة، قبل الفهرس 1.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة الزيادة بمقدار واحد؟
تعمل الطريقتان في زمن O(n) بالنسبة إلى n من الخانات، لأن الحالة الأسوأ، وهي أن تكون جميع الخانات 9، تمر على كل خانة. تتوقف النسخة ذات الخروج المبكر بعد الخانات 9 المتتالية من اليمين، لذا فهي تنفّذ خطوة واحدة إذا كان العدد ينتهي بخانة أقل من 9. وتستخدم مساحة إضافية O(1)، إلا إذا كانت الإجابة تتطلب خانة بادئة جديدة.
لماذا لا تحوّل الأرقام إلى عدد صحيح؟
لأن العدد قد يتكوّن من 100 رقم، بينما يتوقف العدد الصحيح ذو 64 بتًا عند نحو 1.8 × 10^19، أي 20 رقمًا. لدى Python وRuby أعداد صحيحة غير محدودة، لذا ينجح التحويل فيهما، لكنه يحجب الغرض من التمرين ولا ينطبق على لغات أخرى. أمّا معالجة الأرقام رقمًا رقمًا فلا تؤدي أبدًا إلى تجاوز السعة.
متى تكون النتيجة ذات أرقام أكثر من المُدخل؟
فقط عندما يكون كل رقم هو 9. عندها يكون العدد 10^n - 1، وإضافة واحد تعطي 10^n: الرقم 1 متبوعًا بـ n أصفار. إذا كان أي رقم أقل من 9، فإنه يستوعب الحمل، لذا يبقى الطول كما هو.
كيف تجمع عددين مخزّنين على هيئة مصفوفتين من الأرقام؟
استخدم طريقة الأعمدة من النهج الأول مع مؤشرين، أحدهما عند نهاية كل مصفوفة. اجمع الرقمين في كل عمود، مع اعتبار الرقم المفقود 0، بالإضافة إلى الحمل. واصل حتى تنفد المصفوفتان ويصبح الحمل 0، ثم اعكس ترتيب الأرقام التي جمعتها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def plusOne(digits):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
digits = [4, 3, 9]
المتوقع
[4, 4, 0]