Roman to Integer

+10

Angka Romawi menggunakan tujuh simbol: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 dan M = 1000. Simbol-simbol ditulis dari yang terbesar ke yang terkecil lalu dijumlahkan, kecuali dalam enam pasangan pengurangan yang menempatkan simbol yang lebih kecil terlebih dahulu dan mengurangkannya dari simbol yang lebih besar: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 dan CM = 900.

Kamu mendapatkan angka Romawi valid s. Kembalikan bilangan bulat yang diwakilinya.

Fungsi

romanToInt(s: string) → integer

sstring: angka Romawi yang valid dengan huruf kapital
Mengembalikaninteger: nilai angka tersebut, dari 1 hingga 3999

Batasan

1 ≤ s.length ≤ 15
s hanya berisi karakter I, V, X, L, C, D, dan M.
s adalah angka Romawi yang valid untuk nilai dari 1 hingga 3999.

Contoh

Input: s = "XXVII"
Output: 27
Penjelasan: XX adalah 10 + 10, V adalah 5 dan II adalah 1 + 1, jadi totalnya 27. Tidak ada simbol yang diikuti oleh simbol yang lebih besar, jadi setiap simbol dijumlahkan.

Input: s = "CDXLIV"
Output: 444
Penjelasan: Angka tersebut terdiri dari tiga pasangan pengurangan berurutan: CD adalah 400, XL adalah 40 dan IV adalah 4, sehingga hasilnya 444.

Input: s = "MCDXCII"
Output: 1492
Penjelasan: M bernilai 1000, CD bernilai 400, XC bernilai 90, dan II bernilai 2, jadi angka tersebut adalah 1492. Pasangan dan simbol biasa dapat dicampur dengan bebas.

Pertanyaan lanjutan

Bisakah kamu menulis kebalikannya, mengubah bilangan bulat dari 1 hingga 3999 menjadi angka Romawi?

Petunjuk

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

0 dari 3 dibuka

Solusi

Sebagian besar angka Romawi merupakan penjumlahan biasa, jadi tantangannya adalah mengenali enam pasangan pengurangan. Kamu bisa mencarinya sebagai token dua huruf, atau menggunakan satu aturan yang mencakup semuanya: simbol yang nilainya lebih kecil daripada simbol di sebelah kanannya dikurangkan. Dengan cara apa pun, satu kali penelusuran sudah cukup untuk mendapatkan jawabannya.

Baca pasangan pengurangan sebagai token

Intuisi

Baca angka Romawi sebagai deretan token: simbol tunggal, ditambah enam pasangan dua simbol IV, IX, XL, XC, CD dan CM. Jumlahkan nilai tokennya, maka kamu mendapatkan angkanya. MCDXCII terbagi menjadi M, CD, XC, I, I: 1000 + 400 + 90 + 1 + 1 = 1492.

Periksa pasangan sebelum simbol tunggal, atau X pada XC akan menambahkan 10 lalu 100. Pemeriksaan ini aman: dalam angka Romawi yang valid, simbol yang lebih kecil hanya berada tepat sebelum simbol yang lebih besar di dalam salah satu pasangan ini, jadi setiap pasangan yang kamu temukan memang benar.

Setiap langkah menggunakan satu atau dua karakter dan tabel memiliki ukuran tetap: waktu O(n), ruang ekstra O(1).

Algoritma

Buat satu tabel untuk enam pasangan dan satu tabel untuk tujuh simbol tunggal.
Mulai dari indeks 0 dengan total 0.
Jika dua karakter pada indeks tersebut membentuk pasangan, tambahkan nilai pasangan itu dan geser indeks sebanyak 2.
Jika tidak, tambahkan nilai simbol tunggal dan geser indeks sebanyak 1.
Saat indeks melewati akhir, kembalikan totalnya.

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

Bandingkan setiap simbol dengan simbol berikutnya

Intuisi

Pada masing-masing dari enam pasangan, simbol pertama bernilai lebih kecil daripada simbol kedua, dan nilai pasangan tersebut adalah nilai simbol kedua dikurangi nilai simbol pertama. Jadi, kamu bisa menghilangkan tabel pasangan dan memakai satu aturan: kurangi nilai simbol jika nilainya lebih kecil daripada simbol di sebelah kanannya, tambahkan nilai setiap simbol lainnya. CM menjadi -100 + 1000 = 900, nilai yang dihasilkan pembacaan token.

Dalam MCDXCII, C diikuti oleh D yang lebih besar, dan X diikuti oleh C yang lebih besar, sehingga totalnya adalah 1000 - 100 + 500 - 10 + 100 + 1 + 1 = 1492. Perbandingannya menggunakan lebih kecil secara ketat: simbol yang bersebelahan dengan nilai sama dijumlahkan, sehingga II bernilai 2. Aturan ini benar karena alasan yang sama dengan token: simbol yang lebih kecil hanya muncul tepat sebelum simbol yang lebih besar sebagai bagian pertama dari sebuah pasangan.

Satu kali melihat setiap karakter dan satu total berjalan: waktu O(n), ruang ekstra O(1).

Algoritma

Simpan nilai masing-masing dari tujuh simbol.
Lakukan perulangan pada indeks s dengan total berjalan yang dimulai dari 0.
Jika simbol berikutnya ada dan nilainya lebih besar daripada simbol saat ini, kurangi nilai saat ini.
Jika tidak, tambahkan nilai saat ini.
Kembalikan total setelah perulangan.

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

Jebakan dan kasus tepi

Menggunakan lebih kecil dari atau sama dengan, bukan hanya lebih kecil dari. Akibatnya, II dan XX sama-sama menghasilkan 0, karena simbol pertama masing-masing dikurangi.
Membaca s[i+1] pada karakter terakhir, padahal karakter itu tidak ada. Periksa i+1 terhadap panjangnya terlebih dahulu, dan selalu tambahkan simbol terakhir.
Dalam versi token, mencoba simbol tunggal sebelum pasangan. XC lalu dibaca sebagai 10 + 100 = 110.
Lupa bahwa string Lua dan R dimulai dari indeks 1, jadi simbol terakhir berada di #s atau nchar(s).

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Roman to Integer?

Kedua pendekatan membaca setiap karakter satu kali, sehingga waktu yang dibutuhkan adalah O(n) untuk angka yang terdiri dari n karakter. Ruang tambahan yang dibutuhkan adalah O(1), karena tabel pencarian memiliki ukuran tetap. Angka dari 1 hingga 3999 memiliki paling banyak 15 karakter.

Bisakah kamu mengonversi angka Romawi dari kanan ke kiri?

Ya. Berjalanlah dari simbol terakhir ke simbol pertama dan ingat nilai simbol di sebelah kanan. Jika nilai simbol saat ini lebih kecil daripada nilai simbol itu, kurangi; jika tidak, tambahkan. Aturannya sama seperti versi dari kiri ke kanan, hanya dilihat dari sisi lain.

Apakah solusi ini memeriksa apakah angka tersebut valid?

Tidak. Soal ini menjamin bahwa input berupa angka Romawi yang valid, jadi kode hanya menjumlahkan dan mengurangkan. String yang tidak valid seperti IIII atau VV tetap menghasilkan sebuah angka, yaitu 4 atau 10. Untuk memvalidasinya, ubah hasilnya kembali menjadi angka Romawi dan bandingkan dengan input.

def romanToInt(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "XXVII"

Output yang diharapkan