Roman to Integer

Q: מהי סיבוכיות הזמן של ההמרה ממספר רומי למספר שלם?

שתי הגישות קוראות כל תו פעם אחת, ולכן זמן הריצה הוא O(n) עבור ספרה בת n תווים. המקום הנוסף הוא O(1) , כי לטבלאות החיפוש יש גודל קבוע. לספרה בטווח שבין 1 ל־3999 יש לכל היותר 15 תווים, ולכן בפועל העבודה זניחה.

Q: למה מחסירים סמל שקטן מהסמל הבא?

כך נבנים ששת הזוגות החיסוריים. ב־ IV , IX , XL , XC , CD ו־ CM , סמל קטן מופיע לפני סמל גדול יותר, ושווי הזוג הוא הגדול פחות הקטן. חיסור הסמל הראשון והוספת השני נותנים בדיוק את הערך הזה, ובשום מקום אחר בספרה תקינה לא מופיע סמל קטן לפני סמל גדול יותר.

קלמתמטיקה וסימולציה גיבוב

+10

בספרות רומיות משתמשים בשבעה סמלים: 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. החזר את המספר השלם שהיא מייצגת.

פונקציה

romanToInt(s: string) → integer

sstring: ספרה רומית תקינה באותיות גדולות
מחזירהinteger: הערך של הספרה, מ־1 עד 3999

אילוצים

1 ≤ s.length ≤ 15
s מכילה רק את התווים 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. אפשר לשלב זוגות וסמלים בודדים בחופשיות.

שאלת המשך

האם תוכל לכתוב את ההיפוך, ולהמיר מספר שלם מ־1 עד 3999 לספרה רומית?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

רובו של מספר הוא סכום פשוט, ולכן כל העניין הוא לזהות את ששת הצמדים החיסוריים. אפשר לחפש אותם כאסימונים בני שתי אותיות, או להשתמש בכלל אחד שמכסה את כולם: סמל שערכו קטן מזה של הסמל שמימינו מחוסר. כך או כך, מעבר אחד על לכל היותר 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).

שאלות נפוצות3

מהי סיבוכיות הזמן של ההמרה ממספר רומי למספר שלם?

שתי הגישות קוראות כל תו פעם אחת, ולכן זמן הריצה הוא O(n) עבור ספרה בת n תווים. המקום הנוסף הוא O(1), כי לטבלאות החיפוש יש גודל קבוע. לספרה בטווח שבין 1 ל־3999 יש לכל היותר 15 תווים, ולכן בפועל העבודה זניחה.

למה מחסירים סמל שקטן מהסמל הבא?

כך נבנים ששת הזוגות החיסוריים. ב־IV, IX, XL, XC, CD ו־CM, סמל קטן מופיע לפני סמל גדול יותר, ושווי הזוג הוא הגדול פחות הקטן. חיסור הסמל הראשון והוספת השני נותנים בדיוק את הערך הזה, ובשום מקום אחר בספרה תקינה לא מופיע סמל קטן לפני סמל גדול יותר.

האם תוכל להמיר ספרה רומית מימין לשמאל?

כן. עברו מהסמל האחרון לראשון וזכרו את הערך של הסמל שקראתם קודם, זה שמימין. אם ערך הסמל הנוכחי קטן מערכו, החסירו אותו; אחרת, הוסיפו אותו. זהו אותו כלל כמו בגרסה משמאל לימין, רק מהצד השני.

def romanToInt(s):
    # כתבו את הקוד כאן

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

s = "XXVII"

הפלט הצפוי