0012. 整数转罗马数字 Integer to Roman

问题描述

这也是字典映射问题, 目前实现了三种解法

模式匹配

这个类似于哈稀表, 但是性能更高.

#![allow(unused)]
fn main() {
#[must_use]
#[inline]
pub const fn get_more_roman_symbols(num: i32) -> &'static str {
    match num {
        3000 => "MMM",
        2000 => "MM",
        1000 => "M",
        900 => "CM",
        800 => "DCCC",
        700 => "DCC",
        600 => "DC",
        500 => "D",
        400 => "CD",
        300 => "CCC",
        200 => "CC",
        100 => "C",
        90 => "XC",
        80 => "LXXX",
        70 => "LXX",
        60 => "LX",
        50 => "L",
        40 => "XL",
        30 => "XXX",
        20 => "XX",
        10 => "X",
        9 => "IX",
        8 => "VIII",
        7 => "VII",
        6 => "VI",
        5 => "V",
        4 => "IV",
        3 => "III",
        2 => "II",
        1 => "I",
        _ => "-",
    }
}

// 模式匹配
pub fn int_to_roman1(num: i32) -> String {
    assert!((0..=3999).contains(&num));

    let mut num = num;
    let mut quot;
    // 最大支持1000级的
    let mut factor = 1000;
    let mut out = String::new();

    while num > 0 || factor > 0 {
        // 计算商
        quot = num / factor;
        // 构造这个位的数值.
        let val = quot * factor;

        if val > 0 {
            // 根据数值, 拿到对应的字符串
            out += get_more_roman_symbols(val);
        }

        // 计算余数, 准备下一次循环使用
        num %= factor;
        factor /= 10;
    }

    out
}
}

分段映射

单独对每个进位做映射, 很简单的实现, 易懂.

split-digits

#![allow(unused)]
fn main() {
// 单独分开各个进位的值
pub fn int_to_roman3(num: i32) -> String {
    const ONES: &[&str] = &["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
    const TENS: &[&str] = &["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
    const HUNDREDS: &[&str] = &["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
    const THOUSANDS: &[&str] = &["", "M", "MM", "MMM"];

    let num = num as usize;
    let parts = [
        THOUSANDS[num / 1000],
        HUNDREDS[(num % 1000) / 100],
        TENS[(num % 100) / 10],
        ONES[num % 10],
    ];
    parts.join("").to_owned()
}
}

手动匹配

这种方法支持更复杂的整数, 扩展性更好, 但是比较复杂, 性能也一般

#![allow(unused)]
fn main() {
#[must_use]
#[inline]
pub const fn get_roman_symbol(num: i32) -> char {
    match num {
        1000 => 'M',
        500 => 'D',
        100 => 'C',
        50 => 'L',
        10 => 'X',
        5 => 'V',
        1 => 'I',
        _ => '-',
    }
}

#[must_use]
pub fn get_roman_symbols_manual(quot: i32, factor: i32) -> String {
    match quot {
        0 => String::new(),
        val @ 1..=3 => {
            let one = get_roman_symbol(factor);
            let mut s = String::new();
            // [one]
            // [one, one]
            // [one, one, one]
            for _i in 0..val {
                s.push(one);
            }
            s
        }
        4 => {
            let five = get_roman_symbol(5 * factor);
            let one = get_roman_symbol(factor);
            let mut s = String::new();
            // [one, five]
            s.push(one);
            s.push(five);
            s
        }
        5 => get_roman_symbol(5 * factor).to_string(),
        val @ 6..=8 => {
            let five = get_roman_symbol(5 * factor);
            let one = get_roman_symbol(factor);
            let mut s = String::new();
            // [five, one]
            // [five, one, one]
            // [five, one, one, one]
            s.push(five);
            for _i in 0..(val - 5) {
                s.push(one);
            }
            s
        }
        9 => {
            let ten = get_roman_symbol(10 * factor);
            let one = get_roman_symbol(factor);
            let mut s = String::new();
            // [one, ten]
            s.push(one);
            s.push(ten);
            s
        }
        _ => unimplemented!(),
    }
}

// 部分模式匹配
// 剩下的手动计算, 性能较差
pub fn int_to_roman2(num: i32) -> String {
    assert!((0..=3999).contains(&num));

    let mut num = num;
    let mut quot;
    // 最大支持1000级的
    let mut factor = 1000;
    let mut out = String::new();

    while num > 0 || factor > 0 {
        // 计算商
        quot = num / factor;

        if quot > 0 {
            // 构造这个位的数值对应的罗马数字.
            out += &get_roman_symbols_manual(quot, factor);
        }

        // 计算余数, 准备下一次循环使用
        num %= factor;
        factor /= 10;
    }

    out
}
}

相关问题