Roman to Integer
تستخدم الأرقام الرومانية سبعة رموز: I = 1، وV = 5، وX = 10، وL = 50، وC = 100، وD = 500، وM = 1000. تُكتب الرموز من الأكبر إلى الأصغر وتُجمع، باستثناء ستة أزواج طرحية يأتي فيها رمز أصغر أولًا ويُطرح من الرمز الأكبر: IV = 4، وIX = 9، وXL = 40، وXC = 90، وCD = 400، وCM = 900.
لديك رقم روماني صالح s. أعد العدد الصحيح الذي يمثله.
الدالة
- sstring
- رقم روماني صحيح مكتوب بأحرف كبيرة
- تُرجعinteger
- قيمة الرقم، من 1 إلى 3999
القيود
1 ≤ s.length ≤ 15sيحتوي فقط على الأحرفIوVوXوLوCوDوM.sهو رقم روماني صالح لقيمة من 1 إلى 3999.
أمثلة
- المدخلات
- s = "XXVII"
- المخرجات
- 27
- الشرح
XXيساوي 10 + 10، وVيساوي 5، وIIيساوي 1 + 1، لذا يكون المجموع 27. لا يتبع أيَّ رمزٍ رمزٌ أكبر منه، لذا تُضاف قيمة كل رمز.
- المدخلات
- s = "CDXLIV"
- المخرجات
- 444
- الشرح
- العدد مكوّن من ثلاثة أزواج طرحية متتالية:
CDتساوي 400، وXLتساوي 40، وIVتساوي 4، ما يجعل الناتج 444.
- المدخلات
- s = "MCDXCII"
- المخرجات
- 1492
- الشرح
Mتساوي 1000، وCDتساوي 400، وXCتساوي 90، وIIتساوي 2، لذا فالعدد هو 1492. يمكن مزج الأزواج والرموز المفردة بحرية.
+22 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك كتابة العكس، بتحويل عدد صحيح من 1 إلى 3999 إلى رقمه الروماني؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اكتب العدد بحيث تكون هناك قيمة واحدة لكل رمز. تصبح
MCDXCII1000 و100 و500 و10 و100 و1 و1. أيّ من هذه القيم يجب أن تُحسب سالبة كي يكون المجموع 1492؟يُطرَح الرمز فقط عندما تكون قيمة الرمز الذي يليه مباشرةً أكبر: الرمز C في
CD، والرمز X فيXC. وتُضاف قيمة كل رمز آخر، بما في ذلك الرمز الذي يتبعه رمز مساوٍ له، كما فيII.مرّر على السلسلة مرة واحدة باستخدام فهرس. قارن قيمة الرمز الحالي بقيمة الرمز التالي، واطرح قيمة الرمز الحالي إذا كانت أصغر، وأضفها خلاف ذلك. الرمز الأخير ليس له رمز مجاور، لذا يُضاف دائمًا.
الحل
يتكوّن معظم العدد من مجموع عادي، لذا تتمثل المشكلة كلها في اكتشاف الأزواج الستة الطرحية. يمكنك البحث عنها بوصفها رموزًا من حرفين، أو استخدام قاعدة واحدة تشمل الأزواج الستة كلها: يُطرح الرمز إذا كانت قيمته أقل من قيمة الرمز الذي يليه مباشرةً. في كلتا الحالتين، تكفي مرة مرور واحدة على 15 حرفًا كحد أقصى للوصول إلى الإجابة.
اقرأ الأزواج الطرحية بوصفها رموزًا
الفكرة
اعتبر الرقم صفًا من الرموز. معظم الرموز تتكون من رمز واحد، وستة منها تتكون من رمزين: IV وIX وXL وXC وCD وCM. قسّم السلسلة إلى هذه الرموز، واجمع قيمها، فتحصل على الرقم.
في كل موضع، انظر أولًا إلى الحرفين التاليين. إذا شكّلا أحد الأزواج الستة، فأضف قيمة الزوج وتجاوز الحرفين. وإلا فأضف قيمة الرمز المفرد وتجاوز حرفًا واحدًا. تُقسّم MCDXCII إلى M وCD وXC وI وI: 1000 + 400 + 90 + 1 + 1 = 1492.
يجب أن يأتي التحقق من الزوج أولًا. إذا قرأت X في XC بمفرده، فستضيف 10 ثم 100، وتحصل على 110 بدلًا من 90. وهذا التحقق آمن أيضًا: في الرقم الصحيح، لا يأتي رمز أصغر مباشرةً قبل رمز أكبر إلا ضمن أحد هذه الأزواج الستة، لذا فإن كل زوج تجده هو زوج حقيقي.
تستهلك كل خطوة حرفًا واحدًا أو حرفين، لذا تنفّذ الحلقة 15 مرة كحد أقصى. للجدولين حجم ثابت، لذا تكون المساحة الإضافية ثابتة.
الخوارزمية
- أنشئ جدولًا واحدًا للأزواج الستة وجدولًا آخر للرموز المفردة السبعة.
- ابدأ من الفهرس 0 بإجمالي قدره 0.
- إذا شكّل الحرفان عند الفهرس زوجًا، فأضف قيمة الزوج وتقدّم بالفهرس بمقدار 2.
- وإلا، فأضف قيمة الرمز المفرد وتقدّم بالفهرس بمقدار 1.
- عندما يتجاوز الفهرس النهاية، أعد الإجمالي.
def romanToInt(s):
pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
i = 0
while i < len(s):
two = s[i:i + 2]
if two in pairs:
total += pairs[two]
i += 2
else:
total += singles[s[i]]
i += 1
return totalقارن كل رمز بالرمز الذي يليه
الفكرة
انظر إلى الأزواج الستة مرة أخرى. في كل زوج منها، قيمة الرمز الأول أقل من قيمة الرمز الثاني، وتساوي قيمة الزوج قيمة الرمز الثاني مطروحًا منها قيمة الرمز الأول. لذا يمكنك الاستغناء عن جدول الأزواج واستخدام قاعدة واحدة: إذا كانت قيمة الرمز أقل من قيمة الرمز الذي يليه، فاطرحها؛ وإلا فأضفها. تصبح CM -100 + 1000 = 900، وهي القيمة نفسها التي نحصل عليها بقراءة الرموز.
تتبّع MCDXCII. يلي M رمز C الأصغر منه، لذا أضف 1000. يلي C رمز D الأكبر منه، لذا اطرح 100: يصبح المجموع 900. أضف D ليصبح المجموع 1400. يلي X رمز C الأكبر منه، لذا اطرح 10: يصبح المجموع 1390. أضف C: يصبح المجموع 1490. يلي I الأول رمز I مساوٍ له، لذا أضفه: يصبح المجموع 1491. أما I الأخير فليس له رمز يليه، لذا أضفه أيضًا: يصبح المجموع 1492.
يجب أن تكون المقارنة أصغر من بشكل صارم. تُضاف الرموز المتجاورة المتساوية دائمًا، وهذا ما يجعل II تساوي 2 وXX تساوي 20. والقاعدة صحيحة للسبب نفسه الذي يجعل قراءة الرموز صحيحة: في الأعداد الرومانية الصحيحة، لا يأتي رمز أصغر مباشرةً قبل رمز أكبر إلا بوصفه النصف الأول من زوج طرحي.
تنظر إلى كل محرف مرة واحدة وتحتفظ بمجموع جارٍ واحد، لذا فالزمن هو O(n) والمساحة الإضافية هي O(1). لا يحتاج هذا الإصدار إلا إلى قيم الرموز السبعة ومقارنة واحدة لكل محرف.
الخوارزمية
- خزّن قيمة كل واحد من الرموز السبعة.
- كرّر المرور على فهارس
sمع إجمالي تراكمي يبدأ من 0. - إذا كان الرمز التالي موجودًا وتساوي قيمته أكثر من قيمة الرمز الحالي، فاطرح القيمة الحالية.
- وإلا فأضف القيمة الحالية.
- أعِد الإجمالي بعد انتهاء الحلقة.
def romanToInt(s):
values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
for i in range(len(s)):
value = values[s[i]]
# A symbol worth less than the one after it is subtracted, like the I in IV.
if i + 1 < len(s) and value < values[s[i + 1]]:
total -= value
else:
total += value
return total
أخطاء شائعة وحالات حدّية
القاعدة قصيرة، لذا تتعلق الأخطاء بالتفاصيل الدقيقة فيها.
- استخدام «أقل من أو يساوي» بدلًا من «أقل من» بشكل صارم. عندئذٍ تكون نتيجة
IIهي 0 ونتيجةXXهي 0، لأن كل رمز أول يُطرح. - قراءة الرمز التالي عند الحرف الأخير. لا يوجد
s[i+1]هناك؛ تحقّق أولًا منi+1مقارنةً بالطول، وأضف الرمز الأخير دائمًا. - في نسخة الرموز، تجربة الرموز المفردة قبل الأزواج. عندئذٍ تُقرأ
XCعلى أنها 10 + 100 = 110. - التعرّف على الزوج عند رمزه الثاني فقط. إذا كنت قد أضفت بالفعل I في
IV، فعليك طرحه مرتين،1 + 5 - 2 × 1= 4. تجنّب المقارنة مع الرمز التالي الحاجة إلى هذا التصحيح. - نسيان أن فهارس السلاسل في Lua وR تبدأ من 1، لذا يقع الرمز الأخير عند
#sأوnchar(s).
أسئلة شائعة4
ما التعقيد الزمني لتحويل الأرقام الرومانية إلى أعداد صحيحة؟
يقرأ كلا النهجين كل حرف مرة واحدة، لذا يكون الزمن O(n) لعدد يتكون من n حرفًا. المساحة الإضافية هي O(1)، لأن جداول البحث ذات حجم ثابت. يتكون العدد من 1 إلى 3999 من 15 حرفًا كحد أقصى، لذا يكون العمل ضئيلًا عمليًا.
لماذا تطرح رمزًا أصغر من الرمز الذي يليه؟
هكذا تتكوّن أزواج الطرح الستة. في IV وIX وXL وXC وCD وCM، يأتي رمز أصغر قبل رمز أكبر، وتساوي قيمة الزوج الأكبر مطروحًا منه الأصغر. إن طرح الرمز الأول وإضافة الرمز الثاني يعطي هذه القيمة بالضبط، ولا يوجد موضع آخر في عدد صحيح يكون فيه رمز أصغر قبل رمز أكبر.
هل يمكنك تحويل رقم روماني من اليمين إلى اليسار؟
نعم. تحرّك من الرمز الأخير إلى الأول، وتذكّر قيمة الرمز الذي قرأته قبله، أي الرمز الموجود على اليمين. إذا كانت قيمة الرمز الحالي أقل من قيمة ذلك الرمز، فاطرحها؛ وإلا فأضفها. إنها القاعدة نفسها المستخدمة في النسخة من اليسار إلى اليمين، لكن عند النظر إليها من الجهة الأخرى.
هل يتحقق هذا الحل من أن الرقم صالح؟
لا. تضمن المسألة أن الرقم صحيح، لذا فإن الشيفرة لا تفعل سوى الجمع والطرح. عند إعطائها سلسلة غير صالحة مثل IIII أو VV، فإنها تظل تُرجع عددًا، وهو 4 و10. للتحقق من الصحة، حوّل الناتج مرة أخرى إلى رقم وقارنه بالإدخال.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def romanToInt(s):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
s = "XXVII"
المتوقع
27