מספר שלם לפתרון Leetcode הרומי  


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלקרוק בלומברג Evernote פייסבוק Google לינקדין מיקרוסופט אורקל טויטר יאהו
אלגוריתמים קידוד ראיון אישי הוכחת ראיונות LeetCode LeetCodeSolutions מתמטיקה מחרוזת

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

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

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

3
III

הסבר: מכיוון שאני שווה ערך ל -1, אנו חוזרים עליו שלוש פעמים כדי לקבל את הסכום = 3.

4
IV

הסבר: אנחנו לא יכולים לחזור על I 4 פעמים, כי אנחנו לא יכולים לחזור על I יותר מ -3 פעמים. אז אנחנו מישור אני לפני V. מכיוון שאני פחות מ- V, כך 1 מופחת מהסך הכל שווה ל- 5. ובכך הופך סכום כולל השווה ל -4.

גישת פתרון שלם לליטק רומית  

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

ראה גם
המרת מספר לפתרון Leetcode הקסדצימלי

ובכן, אם נסתכל מקרוב יש רק כמה דרכים אפשריות בהן אנו יכולים להיתקל בחריג זה. חריג זה הוא רק כאשר אנו חוזרים על מספר כלשהו יותר מפי 3. אז פשוט נסה למצוא את הדרכים לכתוב את המספרים השלמים שיכולים ליפול לחריג. אנו לומדים כי היוצא מן הכלל הוא 4, 9, 40, 90, 400, 900 שניתן להמיר ל IV, IX, XL, XC, CD, CM בהתאמה.

התמודדות עם חריגים

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

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

קוד לפתרון שלם ללהיט רומי  

קוד C ++ עבור פתרון שלם לליטר קוד רומי

#include <bits/stdc++.h>
using namespace std;

string intToRoman(int num) {
    vector<string> romans({"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"});
    vector<int> value({1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000});
    int seqSize = romans.size();
    int idx = seqSize - 1;
    string ans = "";
    while(num>0){
        while(value[idx]<=num){
            ans += romans[idx];
            num -= value[idx];
        }
        idx--;
    }
    return ans;
}

int main(){
    cout<<intToRoman(4);
}
IV

קוד Java לפתרון שלם ללהיט רומי

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static String intToRoman(int num) {
        String romans[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int value[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        int seqSize = romans.length;
        int idx = seqSize - 1;
        String ans = "";
        while(num>0){
            while(value[idx]<=num){
                ans += romans[idx];
                num -= value[idx];
            }
            idx--;
        }
        return ans;
    }
    public static void main(String[] args){
    	System.out.println(intToRoman(4));
    }
}

 

IV

ניתוח מורכבות  

מורכבות זמן

O (1), מכיוון שאנחנו משתמשים במספר קבוע של צעדים כדי למצוא את התוצאה.

ראה גם
פתרון Leetcode מערך מיון יחסית

מורכבות בחלל

O (1), מכיוון שאחסנו רק מספר קבוע של משתנים והמערכים בהם השתמשנו הם גם בעלי גודל קבוע.