Reverse the Digits
لديك عدد صحيح غير سالب n. أعد العدد الناتج عن كتابة أرقامه العشرية بترتيب عكسي. تُحذف الأصفار التي تصبح في المقدمة، لذا يصبح 120 هو 21.
الدالة
- ninteger
- العدد الصحيح غير السالب المراد عكسه
- تُرجعinteger
- أرقام n بترتيب عكسي، كعدد
القيود
0 ≤ n < 109- العدد المعكوس أيضًا يقع ضمن نطاق عدد صحيح موقّع من 32 بت.
أمثلة
- المدخلات
- n = 1234
- المخرجات
- 4321
- الشرح
- أرقام
1234هي 1 و2 و3 و4. وعند قراءتها من النهاية تصبح 4 و3 و2 و1، أي4321.
- المدخلات
- n = 120
- المخرجات
- 21
- الشرح
- عند القراءة من اليمين إلى اليسار، تعطي
120الأرقام 0 و2 و1. لا يُحتسب الصفر في بداية العدد، لذا تكون الإجابة21.
- المدخلات
- n = 0
- المخرجات
- 0
- الشرح
- يتكوّن
0من رقم واحد، وعند عكسه نحصل على0مرة أخرى.
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
إذا كان من الممكن أن تكون قيمة n أي عدد صحيح من 32 بت، فقد لا يتسع العدد المعكوس لها. كيف يمكنك اكتشاف ذلك قبل أن يتجاوز الضرب الحد؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أيُّ عملية حسابية تعطيك الرقم الأخير من عدد، وأيُّها تحذفه؟
n % 10هو الرقم الأخير، وn / 10(القسمة الصحيحة) يحذفه. لوضع الرقمdفي نهاية عدد آخرr، احسبr * 10 + d.ابدأ بـ
result = 0. ما دامnأكبر من0، انقل رقمه الأخير إلى نهايةresultواحذف ذلك الرقم منn. لا تظهر أصفار بادئة أبدًا، لأن0 * 10 + 0يظل0.
الحل
عكس النص العشري يحتاج إلى سطر واحد في معظم اللغات، وهو إجابة أولى جيدة. عادةً ما يتابع القائمون على المقابلات بسؤال عن كيفية الوصول إلى النتيجة نفسها من دون استخدام السلاسل النصية. تعتمد الطريقة الحسابية على عمليتين: n % 10 يقرأ الرقم الأخير، وn / 10 (القسمة الصحيحة) يزيله.
اعكس النص العشري
الفكرة
أرقام العدد هي بالضبط محارف تمثيله العشري. حوّل n إلى نص، واعكس المحارف، ثم اقرأ النص مجددًا كعدد. يصبح 1234 "1234"، ثم "4321"، ثم 4321.
تتكفّل الأصفار البادئة بنفسها. يعطينا عكس 120 النص "021"، وتحليله كعدد يتجاهل الصفر في البداية ويعيد 21.
للعدد الأقل من 10^9 ما يصل إلى 9 أرقام، ويزداد كل من العمل والنص الإضافي مع عدد الأرقام، أي O(log n).
الخوارزمية
- حوّل
nإلى نص عشري. - اعكس الأحرف.
- حلّل النص المعكوس كعدد صحيح وأعِده.
def reverseDigits(n):
# int() ignores the leading zeros that trailing zeros turn into.
return int(str(n)[::-1])أزِل الأرقام وأضِفها باستخدام العمليات الحسابية
الفكرة
خذ الأرقام من نهاية n واحدًا تلو الآخر، وأضف كلًّا منها إلى نهاية عدد جديد. تمثل n % 10 الرقم الأخير من n، بينما تؤدي n / 10 مع القسمة الصحيحة إلى حذفه. لإضافة رقم d إلى نهاية result، أزِح ما فيه خانة واحدة إلى اليسار وضع d في خانة الآحاد: result * 10 + d.
بالنسبة إلى 1234، تصبح قيمة result 4، ثم 43، ثم 432، ثم 4321، بينما تصبح قيمة n 123، ثم 12، ثم 1، ثم 0. تتوقف الحلقة عندما تصل n إلى 0، لذا فإنها تعمل مرة واحدة لكل رقم.
لا تظهر أصفار بادئة مطلقًا. بالنسبة إلى 120، يكون الرقم الأول المأخوذ هو 0، وتظل 0 * 10 + 0 مساويةً لـ0، لذا لا تترك أثرًا. عندما تكون n = 0، لا تعمل الحلقة وتكون الإجابة 0. لا يُحتفَظ إلا بعددين صحيحين، لذا فإن المساحة الإضافية هي O(1).
الخوارزمية
- عيّن
result = 0. - ما دام
nأكبر من0، احسب الرقم الأخيرn % 10. - عيّن
result = result * 10 + digit. - احذف الرقم باستخدام
n = n / 10، مع استخدام القسمة الصحيحة. - أعِد
result.
def reverseDigits(n):
result = 0
while n > 0:
result = result * 10 + n % 10 # push the last digit of n
n //= 10 # drop it from n
return result
أخطاء شائعة وحالات حدّية
تأتي معظم الأخطاء من القسمة ومن نهاية الحلقة.
- استخدام القسمة العادية عندما تحتاج إلى القسمة الصحيحة. في JavaScript وPython 3 وLua، تعطي
n / 10القيمة123.4، لذلك لا تصبحnعددًا صحيحًا مرة أخرى، وتمتلئresultبالكسور. استخدمMath.floorأو//أو القسمة الصحيحة في لغتك. - كتابة الحلقة هكذا:
while n >= 10. تتوقف قبل الرقم الأخير، لذلك تعود1234على شكل432. - إرجاع النص المعكوس دون تحويله إلى عدد.
"021"ليس العدد21، وستفشل المقارنة مع الإجابة المتوقعة. - تنسيق قيمة double في R باستخدام
as.character. عندما تُخزَّنnكقيمة double، تُعرَض100000000بالشكل1e+08، ويصبح النص المعكوس80+e1. استخدمformat(n, scientific = FALSE).
أسئلة شائعة4
كيف تعكس ترتيب أرقام عدد دون تحويله إلى سلسلة نصية؟
كرّر خطوتين حتى يصبح العدد 0: خذ الرقم الأخير باستخدام n % 10 وأضِفه إلى النتيجة باستخدام result = result * 10 + digit، ثم احذفه باستخدام n = n / 10 مع القسمة الصحيحة. بالنسبة إلى 1234، تنمو النتيجة لتصبح 4 ثم 43 ثم 432 ثم 4321.
ماذا يحدث للأصفار في نهاية العدد عند عكسه؟
ستصبح أصفارًا بادئة، وهي غير موجودة في العدد، لذا تختفي. عكس 120 يعطي 21، وعكس 100000000 يعطي 1. تحذفها حلقة العمليات الحسابية من تلقاء نفسها، لأن إضافة 0 إلى نتيجة فارغة تُبقيها عند 0.
ما هو التعقيد الزمني لعكس عدد صحيح؟
تُنفَّذ الحلقة مرة واحدة لكل رقم عشري، والعدد n يحتوي على نحو log10(n) + 1 رقمًا، لذا يكون الزمن O(log n). يستخدم الإصدار الحسابي مساحة إضافية O(1)؛ أما إصدار السلسلة فيخزّن الأرقام كنص، وهذا يتطلب O(log n).
هل يمكن أن يؤدي عكس عدد صحيح إلى تجاوز سعة العدد؟
نعم، عندما يمكن أن يكون الإدخال أي عدد صحيح من 32 بت. يتسع 1000000009، لكن معكوسه 9000000001 لا يتسع. هنا n أقل من 10^9، لذا يتكون العدد المعكوس من 9 خانات على الأكثر ويتسع دائمًا. مع المدخلات الأكبر، تحقّق من result > (INT_MAX - digit) / 10 قبل كل عملية ضرب.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def reverseDigits(n):
# اكتب الشيفرة هناالحالة 1
الحالة 2
الحالة 3
المدخلات
n = 1234
المتوقع
4321