Ціле число до римського рішення Leetcode


Рівень складності Medium
Часто запитують у саман Амазонка Apple BlackRock Bloomberg Evernote Facebook Google LinkedIn Microsoft оракул Твіттер Yahoo
Математика рядок

У цій задачі нам дають ціле число і потрібно перевести в римські цифри. Таким чином, проблема зазвичай називається "Ціле до римського", а це ціле до римського рішення Leetcode. Якщо хтось не знає про римські цифри. За старих часів люди не використовували цілих чисел, як ми використовували останнім часом.

Римські цифри зазвичай пишуться зліва направо в порядку зменшення, але з цього є деякі винятки. Якщо якесь число, яке менше за наступне, віднімаємо поточне число від позитивної суми. Загальне емпіричне правило - не повторювати одне і те ж число більше 3 разів. Слід перевірити на зображенні нижче ціле число до римської цифрової конверсії.

Ціле число до римського рішення Leetcode

3
III

Пояснення: Оскільки I еквівалентно 1, ми повторюємо його тричі, щоб отримати суму = 3.

4
IV

Пояснення: Ми не можемо повторити I 4 рази, тому що ми не можемо повторити I більше 3 разів. Отже, ми вирівнюємо I перед V. Оскільки I менше V, то 1 віднімається із загальної суми, яка дорівнює 5. Таким чином, загальна сума дорівнює 4.

Підхід до цілого числа до римського рішення Leetcode

Проблему “Ціле число до римського” можна розв’язати жадібно, коли спочатку ми намагаємось перетворити число на максимально можливе число. Грубий підхід до проблеми неможливий, оскільки він не є здійсненним та загальноприйнятим. Таким чином ми продовжуємо рухатися до менших номіналів римськими цифрами. Але цей підхід не вдасться, коли ми спробуємо перетворити 4. Цей підхід надрукується 4 рази I. Отже, нам потрібно знайти спосіб обійти це.

Що ж, якщо ми уважно розглянемо, існує лише кілька підрахованих можливих шляхів, коли ми можемо натрапити на цей виняток. Ці винятки є лише тоді, коли ми повторюємо деякі цифри більше 3 разів. Тож спробуйте знайти способи написання цілих чисел, які можуть потрапити у виняток. Ми знаємо, що виняток становлять 4, 9, 40, 90, 400, 900, які можна перетворити на IV, IX, XL, XC, CD, CM відповідно.

Робота з винятками

Отже, до цього часу ми думали перетворити дане ціле число на наявні оригінальні римські цифри з одним символом. Але щоб обійти виняток, ми обробляємо їх окремо. Таким чином, ми створюємо два масиви такий, що зберігає інтегральне значення, відповідне кожному римському числу. В іншому масиві зберігаються римські цифри. Обидва ці масиви зберігають цілі числа та римські числа при однакових відповідних індексах.

Тепер нам залишається лише використовувати перетворення, яке робиться жадібно. Почніть з найбільшої римської цифри, і якщо число більше, ніж поточний еквівалент римських цифр. Додайте римське числівник у відповідь рядок і відніміть інтегральне значення з даного цілого числа. Віднімайте поточне число, поки ціле число не перевищує поточне число. Як тільки ви досягнете точки, коли поточне число буде меншим за поточне ціле значення. Просто знайдіть наступну меншу римську цифру. Коли ми закінчимо з усіма римськими цифрами, ми повертаємо відповідь.

Код для цілого числа до римського рішення Leetcode

Код С ++ для цілого числа до римського рішення Leetcode

#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 для цілого числа до римського рішення Leetcode

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), тому що ми використовуємо постійну кількість кроків для пошуку результату.

Складність простору

O (1), оскільки ми зберігаємо лише постійну кількість змінних, а масиви, які ми використовували, також мають постійний розмір.