Plus One
يُخزَّن عدد صحيح غير سالب على هيئة مصفوفة من أرقامه العشرية، digits، بدءًا من الرقم الأكثر أهمية: 472 هو [4, 7, 2]. أضف واحدًا إلى العدد وأعِد أرقام الناتج بالصيغة نفسها. قد يتكون العدد من 100 رقم، وهو أكثر بكثير مما يتسع له عدد صحيح من 64 بت.
الدالة
- digitsinteger-array
- أرقام العدد، بدءًا من الرقم الأكثر أهمية
- تُرجعinteger-array
- أرقام العدد مضافًا إليها واحد، بدءًا من الرقم الأكثر أهمية
القيود
1 ≤ digits.length ≤ 1000 ≤ digits[i] ≤ 9- لا تحتوي
digitsعلى أصفار بادئة، باستثناء العدد 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.
سؤال إضافي
كيف يمكنك طرح واحد بدلًا من ذلك من عدد لا يقل عن 1؟ متى تفقد النتيجة رقمها الأول، كما في [1, 0, 0]؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
قد يتكوّن العدد من 100 رقم، وهذا كثير جدًا بحيث لا يمكن لأي عدد صحيح مضمّن استيعابه. أجرِ عملية الجمع على الأرقام، بالطريقة التي تجمع بها على الورق. أين يوضع الرقم 1 أولًا؟
إضافة 1 إلى رقم أقل من 9 لا تُحدث حملًا، لذا لا يتغير شيء على يساره. الرقم 9 وحده يتحول إلى 0 ويمرر الحمل إلى الرقم التالي.
ابدأ من الرقم الأخير وتحرك إلى اليسار. حوّل كل 9 إلى 0؛ وعند أول رقم أصغر من 9، أضف إليه واحدًا ثم أعد النتيجة. إذا لم تجد أي رقم، فهذا يعني أن جميع الأرقام كانت 9: الإجابة هي 1 متبوعًا بأصفار.
الحل
عدد مكوّن من 100 رقم يتجاوز سعة كل عدد صحيح ذي 64 بت، إذ يتوقف الحد الأقصى عند نحو 1.8 × 10^19، لذا لا يمكنك تحويله ثم جمعه. اجمع بالطريقة التي تستخدمها على الورق، بدءًا من الرقم الأخير مع الاحتفاظ برقم عند الحمل. إضافة 1 تغيّر الأرقام 9 المتتالية في النهاية فقط، فتحوّلها إلى 0، وكذلك الرقم الذي يقع إلى يسارها.
أجرِ الجمع مع الحمل، رقمًا رقمًا
الفكرة
ابدأ بترحيل قيمته 1، وهو الواحد الذي تضيفه. عند كل خانة بدءًا من اليمين، يكون مجموع الخانة هو الرقم زائد قيمة الترحيل: يوضع total % 10 في الإجابة، وتكون total / 10 قيمة الترحيل التالية. لا يتجاوز المجموع 9 + 1 = 10، لذا تبقى قيمة الترحيل 0 أو 1. يصبح أي ترحيل متبقٍ بعد الخانة الأولى رقمًا جديدًا في المقدمة، كما في 999 + 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
الفكرة
يمتصّ الرقم الأقل من 9 حملًا مقداره 1: فتزداد قيمته بمقدار واحد، وتظل قيمة كل رقم إلى يساره كما هي. وحده الرقم 9 يمرّر الحمل، إذ يتحول إلى 0. لذا يمكنك التوقف عند أول رقم أقل من 9 وإرجاع مصفوفة الإدخال بعد تعديلها في موضعها. في [2, 9, 0, 9] يصبح الرقم 9 الأخير 0، ويصبح الرقم 0 هو 1، وتُرجع [2, 9, 1, 0] من دون قراءة الرقمين الأولين.
إذا لم يكن أي رقم أقل من 9، فالعدد هو 10^n - 1، وتكون الإجابة 1 متبوعًا بـ n أصفار. هذه هي الحالة الوحيدة التي تتطلب مصفوفة جديدة، لذا تكون المساحة الإضافية في غير ذلك O(1).
الخوارزمية
- مرّ على الفهارس من الأخير إلى الأول.
- إذا كان الرقم أقل من 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
أخطاء شائعة وحالات حدّية
- تحويل المصفوفة إلى عدد صحيح ثم إعادتها. يستوعب العدد الصحيح ذو 64 بتًا 19 أو 20 رقمًا كحد أقصى، لذا فإن 100 رقم تتجاوز سعته، كما أن العدد العشري يفقد الأرقام الأخيرة في وقت أبكر.
- نسيان الرقم الإضافي. يجب أن تصبح
[9, 9, 9][1, 0, 0, 0]؛ أما الشيفرة التي تعيد كتابة الخانات الموجودة فقط فتعيد[0, 0, 0]. - إضافة 1 إلى الرقم الأول. تكون المصفوفة مرتبة من الأكثر أهمية إلى الأقل أهمية، لذا فإن خانة الآحاد هي العنصر الأخير.
- عدم الإرجاع عندما يستوعب رقم أقل من 9 الحمل. عندها تغيّر الحلقة أرقامًا يجب أن تبقى كما هي: يجب أن تصبح
[1, 9, 3][1, 9, 4]. - في Lua وR، تبدأ المصفوفات من 1، لذا يكون الرقم الأخير عند الفهرس
n، وليسn - 1.
أسئلة شائعة3
ما التعقيد الزمني لعملية Plus One؟
يعمل كلا الأسلوبين بزمن O(n) لعدد n من الأرقام، لأن حالة كون جميع الأرقام 9 تلامس كل رقم. تتوقف النسخة ذات الخروج المبكر بعد الأرقام 9 في النهاية، وتستخدم مساحة إضافية O(1)، إلا عندما تحتاج الإجابة إلى رقم جديد في المقدمة.
لماذا لا تحوّل الأرقام إلى عدد صحيح؟
يمكن أن يتكوّن العدد من 100 رقم، بينما يتوقف العدد الصحيح ذو 64 بتًا عند نحو 1.8 × 10^19، أي 20 رقمًا. تمتلك Python وRuby أعدادًا صحيحة غير محدودة، لذا يعمل التحويل فيهما، لكن الشيفرة لا تنتقل إلى لغات أخرى. أما العمل رقمًا رقمًا فلا يؤدي أبدًا إلى تجاوز السعة.
كيف تجمع عددين مخزّنين على هيئة مصفوفتين من الأرقام؟
استخدم طريقة الأعمدة مع فهرس واحد في نهاية كل مصفوفة. يجمع كل عمود الرقمين، مع اعتبار الرقم المفقود 0، بالإضافة إلى الحمل. توقّف عند استهلاك المصفوفتين ووصول الحمل إلى 0، ثم اعكس ترتيب الأرقام المجمّعة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def plusOne(digits):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
digits = [4, 3, 9]
الإخراج المتوقع
[4, 4, 0]