Add Two Numbers
لديك عددان صحيحان غير سالبين، كلٌّ منهما مخزَّن في قائمة مترابطة أحادية الاتجاه من أرقامه، بدءًا من الرقم الأقل أهمية. في القائمة الأولى، تحتوي العقدة i على الرقم values1[i] وترتبط بالعقدة next1[i]. وتعمل القائمة الثانية بالطريقة نفسها باستخدام next2 وvalues2. في كلتا القائمتين، تنهي -1 القائمة، والرأس هو العقدة 0. العقد غير مخزَّنة بترتيب القائمة، لذا اتبع الروابط.
أعِد أرقام مجموع العددين، بدءًا من الرقم الأقل أهمية.
الدالة
- next1integer-array
- فهرس العقدة التي تشير إليها كل عقدة من العدد الأول، أو -1 لعقدته الأخيرة
- values1integer-array
- الرقم الذي تحتفظ به كل عقدة من العدد الأول
- next2integer-array
- فهرس العقدة التي تشير إليها كل عقدة من العدد الثاني، أو -1 لعقدته الأخيرة
- values2integer-array
- الرقم الذي تحتفظ به كل عقدة من العدد الثاني
- تُرجعinteger-array
- أرقام المجموع، بدءًا من الأقل أهمية
القيود
1 ≤ L1 ≤ 100، حيث إنL1هو طول كلٍّ منnext1وvalues1.1 ≤ L2 ≤ 100، حيث إنL2هو طول كلٍّ منnext2وvalues2.0 ≤ values1[i], values2[j] ≤ 9- كل عنصر في
next1هو-1أو فهرس عقدة في القائمة الأولى، وكل عنصر فيnext2هو-1أو فهرس عقدة في القائمة الثانية. - بدءًا من العقدة
0، تزور كل قائمة جميع عقدها مرة واحدة بالضبط، ثم تصل إلى-1. لا توجد دورة. - لا يحتوي أي عدد على أصفار بادئة: تحمل العقدة الأخيرة في القائمة رقمًا غير
0، ما لم تكن القائمة مكوّنة من الرقم0وحده.
أمثلة
- المدخلات
- next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
- المخرجات
- [5, 4, 1, 1]
- الشرح
- تزور القائمة الأولى العقد
0, 2, 1وتقرأ8, 1, 6، أي العدد 618. وتقرأ الثانية7, 2, 5، أي العدد 527. مجموعهما 1145، لذا تكون الإجابة5, 4, 1, 1.
- المدخلات
- next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
- المخرجات
- [0, 0, 0, 0, 1]
- الشرح
- تُقرأ القائمة الثانية 1, 9, 9, 9، أي العدد 9991. تؤدي إضافة 9 إلى الحصول على 10000: ينتج عن كل خانة
0ويحمل إلى الخانة التالية، ويصبح الحمل الأخير رقمًا خامسًا.
- المدخلات
- next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
- المخرجات
- [7, 5]
- الشرح
- العدد الأول هو 0، وتُقرأ القائمة الثانية
7, 5، أي العدد 57. إضافة 0 لا تغيّر شيئًا، لذا تكون الإجابة[7, 5].
سؤال إضافي
كيف ستجمع الأعداد إذا كانت القوائم تخزّن الرقم الأكثر أهمية أولًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يفشل تحويل كل قائمة إلى عدد: إذ لا تتسع أي قيمة صحيحة لـ 100 رقم. كيف تجمع عددين كبيرين على الورق؟
تبدأ القوائم من خانة الآحاد، وهي بالضبط حيث تبدأ عملية الجمع العمودي. يجمع كل عمود رقمًا واحدًا من كل عدد، بالإضافة إلى الحمل من العمود السابق. يكتب العمود
sum % 10ويحملsum / 10بعد تقريبه إلى الأسفل.تتبّع القائمتين معًا باستخدام مؤشر لكل منهما. أضف
0للقائمة التي انتهت. استمر ما دام أحد المؤشرين لا يساوي-1أو كان الحمل1، لكي يصبح الحمل النهائي رقمًا إضافيًا.
الحل
الأعداد طويلة جدًا بحيث لا يتسع لها أي نوع من الأعداد الصحيحة، لذا اجمعها كما على الورق: عمودًا عمودًا، مع حمل 1 عندما يصل مجموع عمود إلى 10. تخزّن القوائم رقم الآحاد أولًا، لذا فإن المرور عليها يزور الأعمدة بالترتيب الذي تجمعها به.
انسخ الأرقام، ثم اجمع عمودًا تلو الآخر
الفكرة
المؤشر هنا هو فهرس عقدة، والتحرك إلى الأمام يكون باستخدام node = next[node]. انسخ أرقام كل قائمة إلى مصفوفة، بحيث يحتوي الفهرس i على الرقم ذي القيمة 10^i: [8, 1, 6] و[7, 2, 5] في المثال الأول.
ثم أجرِ الجمع كما على الورق، واعتبر الرقم المفقود 0. في كل خانة، اكتب sum % 10 واحمل الباقي: 8 + 7 = 15 تكتب 5 وتحمل 1، و1 + 2 + 1 = 4، و6 + 5 = 11 تكتب 1. يصبح الحمل الأخير رقمًا نهائيًا: [5, 4, 1, 1].
تستهلك النسخ ذاكرة إضافية مقدارها O(L1 + L2) لا يحتاج إليها الجمع مطلقًا.
الخوارزمية
- مرّ على كل قائمة بدءًا من العقدة
0وانسخ أرقامها إلى مصفوفة. - عيّن
carry = 0. ولكل فهرسiحتى طول المصفوفة الأطول، اجمع الأرقام الموجودة عندiمع قيمة الحمل. - أضف
sum % 10وعيّنcarryإلىsum / 10، مع التقريب إلى الأسفل. - إذا كانت قيمة الحمل
1بعد العمود الأخير، فأضفها.
def readDigits(next, values):
# The digits in list order: least significant first.
digits = []
node = 0
while node != -1:
digits.append(values[node])
node = next[node]
return digits
def addTwoNumbers(next1, values1, next2, values2):
first = readDigits(next1, values1)
second = readDigits(next2, values2)
result = []
carry = 0
for i in range(max(len(first), len(second))):
column = carry
if i < len(first):
column += first[i]
if i < len(second):
column += second[i]
result.append(column % 10)
carry = column // 10
if carry > 0:
result.append(carry)
return resultمرّ عبر القائمتين معًا مع الاحتفاظ بالقيمة المحمولة
الفكرة
يستخدم العمود i العقدة رقم i فقط من كل قائمة، لذا احتفظ بمؤشر واحد لكل قائمة، a وb، وحرّك كليهما مع تقدّم الأعمدة.
تستمر حلقة واحدة ما دام a لا يساوي -1، أو كان b لا يساوي -1، أو كان الحمل 1. يضيف المؤشر الذي لا يزال يشير إلى عقدة رقمها ويتقدم إلى العقدة التالية؛ أما المؤشر الذي يشير إلى -1 فلا يضيف شيئًا. يتعامل ذلك مع الأعداد ذات الأطوال المختلفة من دون حلقة ثانية، ويكتب شرط الحمل الرقم الإضافي في النهاية.
في المثال الثاني، 9 زائد 9991، يكون مجموع كل عمود 10 ويكتب 0. بعد أربعة أعمدة، تنتهي القائمتان، لكن الحمل يساوي 1، لذا تستمر الحلقة مرة أخرى: [0, 0, 0, 0, 1]. وباستثناء الإجابة، يحتفظ ذلك بثلاثة أعداد صحيحة.
الخوارزمية
- عيّن
a = 0وb = 0وcarry = 0. - ما دام
a != -1أوb != -1أوcarry > 0، ابدأ مجموع الخانة بقيمةcarry. - إذا كان
a != -1، فأضفvalues1[a]وعيّنa = next1[a]. افعل الشيء نفسه معbباستخدام القائمة الثانية. - ألحِق
sum % 10وعيّنcarryإلىsum / 10مقسومًا مع التقريب إلى الأسفل. - أعِد الأرقام التي ألحقتها.
def addTwoNumbers(next1, values1, next2, values2):
a = 0 # current node of the first number
b = 0 # current node of the second number
carry = 0
result = []
# Keep going while either number has digits left or a carry is waiting.
while a != -1 or b != -1 or carry > 0:
column = carry
if a != -1:
column += values1[a]
a = next1[a]
if b != -1:
column += values2[b]
b = next2[b]
result.append(column % 10) # the digit this column writes
carry = column // 10 # 1 when the column reached 10, else 0
return result
أخطاء شائعة وحالات حدّية
- تحويل كل قائمة إلى عدد صحيح وجمعهما. إن عددًا مكوّنًا من 100 رقم يتجاوز سعة أي نوع ذي 64 بت.
- إهمال الحمل النهائي. تعيد حلقة تتوقف عند انتهاء القائمتين كلتيهما
[0, 0, 0, 0]للمثال الثاني. - التوقف عند انتهاء القائمة الأقصر. عندها يفقد المثال الثاني الأرقام التسعة الثلاثة في 9991 والحمل الذي ينتقل عبرها.
- قراءة الأرقام بترتيب المصفوفة. في المثال الأول، تكون
values1هي[8, 6, 1]، لكن العدد هو 618، ويُقرأ باتباع الروابط. - نسيان الإزاحة في Lua وR، حيث تبدأ المصفوفات عند 1. أبقِ معرّفات العقد بترقيم يبدأ من 0 واقرأ
next1[node + 1].
أسئلة شائعة3
لماذا تُخزَّن الأرقام بترتيب عكسي في مسألة جمع عددين؟
تبدأ عملية الجمع من خانة الآحاد، ولا يمكن اجتياز القائمة أحادية الربط إلا انطلاقًا من رأسها. عندما يكون الرقم الأقل أهمية أولًا، يزور الاجتياز الخانات بالترتيب الذي تجمعها به، لذا ينتقل الحمل إلى الأمام مع المؤشرات.
ما التعقيد الزمني لجمع عددين مخزنين في قوائم مترابطة؟
إنه O(max(L1, L2)): خطوة واحدة لكل عمود، بالإضافة إلى خطوة أخرى إذا بقي حمل في النهاية. وباستثناء الإجابة، يستخدم الإصدار ذو المرور الواحد ذاكرة O(1): مؤشرين والحمل.
هل يمكن أن يكون الحمل أكبر من 1؟
لا. يجمع العمود رقمين لا يتجاوز كل منهما 9، وحملًا لا يتجاوز 1، لذا لا يتجاوز مجموعها 19. والقسمة على 10 مع التقريب إلى الأسفل تعطي 0 أو 1.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def addTwoNumbers(next1, values1, next2, values2):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
next1 = [2, -1, 1] values1 = [8, 6, 1] next2 = [2, -1, 1] values2 = [7, 5, 2]
الإخراج المتوقع
[5, 4, 1, 1]