Integer to Roman

Q: Apa kompleksitas waktu dari Integer to Roman?

O(1) . Input paling banyak 3999, jadi perulangan greedy memeriksa 13 baris tabel dan menambahkan paling banyak 15 simbol. Jika angka yang lebih besar diizinkan dan ditulis dengan M berulang, waktu akan bertambah seiring num / 1000 .

Q: Mengapa 3999 adalah angka terbesar yang diizinkan?

M adalah huruf terbesar dan tidak ada huruf yang boleh muncul empat kali berturut-turut, jadi MMM adalah batas untuk ribuan, dan 3999 adalah MMMCMXCIX . Bilangan yang lebih besar ditulis dengan tanda tambahan, seperti garis di atas huruf untuk mengalikannya dengan 1000.

SedangMatematika dan simulasi Greedy

+10

Angka Romawi memiliki tujuh huruf: M 1000, D 500, C 100, L 50, X 10, V 5, dan I 1. Huruf disusun dari nilai terbesar hingga terkecil dan dijumlahkan, jadi 7 adalah VII. Tidak ada huruf yang diulang empat kali berturut-turut: 4, 9, 40, 90, 400, dan 900 ditulis sebagai IV, IX, XL, XC, CD, dan CM, yaitu huruf yang lebih kecil dikurangkan dari huruf yang lebih besar setelahnya. Hanya enam pasangan ini yang menempatkan huruf lebih kecil di depan.

Diberikan bilangan bulat num, kembalikan angka Romawinya.

Fungsi

intToRoman(num: integer) → string

numinteger: bilangan bulat dari 1 sampai 3999
Mengembalikanstring: angka Romawi untuk num dalam huruf kapital

Batasan

1 ≤ num ≤ 3999

Contoh

Input: num = 49
Output: "XLIX"
Penjelasan: 49 adalah 40 + 9, jadi angkanya adalah XL lalu IX: XLIX. IL tidak diperbolehkan, karena I hanya dikurangkan dalam IV dan IX.

Input: num = 2026
Output: "MMXXVI"
Penjelasan: 2026 tidak memiliki digit 4 atau 9, jadi tidak perlu pasangan dan nilai hurufnya dijumlahkan: 1000 + 1000 + 10 + 10 + 5 + 1 adalah MMXXVI.

Input: num = 944
Output: "CMXLIV"
Penjelasan: 944 adalah 900 + 40 + 4, dan setiap bagian merupakan pasangan pengurangan: CM, XL, dan IV digabungkan menjadi CMXLIV.

Pertanyaan lanjutan

Dengan sebuah string, bisakah kamu memeriksa apakah string tersebut adalah angka Romawi dalam bentuk standar, menerima XLIX dan menolak IIII, IL, dan VX?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Tambahkan enam pasangan pengurangan ke alfabet sebagai simbol tersendiri, lalu menulis angka menjadi seperti memberi uang kembalian: selalu ambil nilai terbesar yang masih muat. Input paling banyak 3999, jadi pekerjaan ini hanya membutuhkan langkah dalam jumlah kecil yang tetap.

Tulis secara aditif, lalu persingkat bentuk panjangnya

Intuisi

Abaikan pasangan-pasangan itu terlebih dahulu: tulis sebanyak mungkin M, lalu D, dan seterusnya hingga I. Untuk 944, hasilnya DCCCCXXXXIIII. Bentuk aditif ini hanya berbeda dari bentuk standar saat suatu digit bernilai 4 atau 9, dan bagian-bagian tersebut selalu berupa salah satu dari enam string yang memiliki bentuk pendek: DCCCC menjadi CM, CCCC menjadi CD, LXXXX menjadi XC, XXXX menjadi XL, VIIII menjadi IX dan IIII menjadi IV.

Ganti DCCCC sebelum CCCC, atau 900 akan menjadi DCD; hal yang sama berlaku untuk puluhan dan satuan. Bentuk aditif memiliki paling banyak 18 huruf (3999), jadi pekerjaannya adalah O(1), dengan biaya satu lintasan kedua dan beberapa string sementara.

Algoritma

Untuk setiap dari tujuh huruf mulai dari M hingga I, tambahkan huruf tersebut selama num setidaknya sebesar nilainya, lalu kurangi nilainya setiap kali.
Ganti DCCCC dengan CM, lalu CCCC dengan CD.
Ganti LXXXX dengan XC, lalu XXXX dengan XL.
Ganti VIIII dengan IX, lalu IIII dengan IV.
Kembalikan string.

def intToRoman(num):
    letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
    numeral = ""
    for value, letter in letters:
        while num >= value:
            numeral += letter
            num -= value
    # Each long form appears at most once; the longer one goes first.
    fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
             ("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
    for long_form, short_form in fixes:
        numeral = numeral.replace(long_form, short_form)
    return numeral

Greedy pada 13 nilai

Intuisi

Urutkan tujuh huruf dan enam pasangan berdasarkan nilainya: M 1000, CM 900, D 500, CD 400, C 100, XC 90, L 50, XL 40, X 10, IX 9, V 5, IV 4, I 1. Selalu benar untuk mengambil nilai terbesar yang muat. Setiap nilai pada tempat desimal yang lebih rendah berada di bawah nilai terkecil pada tempat di atasnya, jadi perulangan selesai satu tempat sebelum menyentuh tempat berikutnya. Di dalam satu tempat, nilai untuk 9, 5, 4, dan 1 menuliskan setiap digit dengan cara standar: 9 adalah simbol 9, 5 sampai 8 adalah simbol 5 ditambah hingga tiga simbol 1, 4 adalah simbol 4, dan 1 sampai 3 adalah simbol 1.

Untuk 3746, perulangan menulis MMM, D, CC, XL, V, I: MMMDCCXLVI. Tabel memiliki 13 baris dan jawaban paling banyak 15 huruf, jadi pekerjaannya adalah O(1), dalam satu kali proses.

Algoritma

Daftarkan 13 nilai beserta simbolnya, dari 1000 hingga 1, termasuk pasangan.
Mulai dengan string kosong.
Untuk setiap baris, selama num setidaknya sebesar nilainya, tambahkan simbol lalu kurangi nilainya.
Kembalikan string setelah semua baris selesai.

def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    parts = []
    for value, symbol in zip(values, symbols):
        while num >= value:  # take the largest value that still fits
            parts.append(symbol)
            num -= value
    return "".join(parts)

Jebakan dan kasus tepi

Menempatkan D sebelum CM dalam tabel. Hasil untuk 900 menjadi DCD.
Menggunakan if, bukan while, untuk setiap baris. Untuk 3000, M diperlukan tiga kali; dengan if, hasilnya menjadi MCMDCDCXCX.
Membuat pasangan lain. 99 adalah XCIX, bukan IC, dan 45 adalah XLV, bukan VL.
Dalam C, buffer yang terlalu kecil. Jawaban terpanjang, untuk 3888, terdiri dari 15 huruf, jadi memerlukan 16 byte dengan terminator nol; bentuk aditif memerlukan 19.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Integer to Roman?

O(1). Input paling banyak 3999, jadi perulangan greedy memeriksa 13 baris tabel dan menambahkan paling banyak 15 simbol. Jika angka yang lebih besar diizinkan dan ditulis dengan M berulang, waktu akan bertambah seiring num / 1000.

Bisakah kamu mengubah bilangan bulat menjadi angka Romawi tanpa perulangan untuk setiap nilai?

Ya. Simpan tabel untuk setiap tempat desimal yang berisi string untuk digit-digitnya, seperti "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM untuk ratusan. Cari setiap digit dari num lalu gabungkan string-string tersebut. Kompleksitasnya juga O(1), dengan 34 string yang disimpan.

Mengapa 3999 adalah angka terbesar yang diizinkan?

M adalah huruf terbesar dan tidak ada huruf yang boleh muncul empat kali berturut-turut, jadi MMM adalah batas untuk ribuan, dan 3999 adalah MMMCMXCIX. Bilangan yang lebih besar ditulis dengan tanda tambahan, seperti garis di atas huruf untuk mengalikannya dengan 1000.

def intToRoman(num):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

num = 49

Output yang diharapkan

"XLIX"