力扣00012.整数转罗马数字

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 8 分钟
整数转罗马数字、哈希表、数学、字符串、中等

题目描述

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

示例 1：

输入: num = 3
输出: “III”

示例 2：

输入: num = 4
输出: “IV”

示例 3：

输入: num = 9
输出: “IX”

示例 4：

输入: num = 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.

示例 5：

输入: num = 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

  • 1 <= num <= 3999

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string intToRoman(int num) {
        int val[] = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        string syms[] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        string romanNum = "";
        for (int i = 0; i < 13; i++) {
            while (num >= val[i]) {
                num -= val[i];
                romanNum += syms[i];
            }
        }
        return romanNum;
    }
};

结果

执行用时 : 4 ms, 击败 85.27% 使用 C++ 的用户

内存消耗 : 6.16 MB, 击败 84.14% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String intToRoman(int num) {
        int[] val = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        String[] syms = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        StringBuilder romanNum = new StringBuilder();
        for (int i = 0; i < 13; i++) {
            while (num >= val[i]) {
                num -= val[i];
                romanNum.append(syms[i]);
            }
        }
        return romanNum.toString();
    }
}

结果

执行用时 : 3 ms, 击败 98.23% 使用 Java 的用户

内存消耗 : 43.08 MB, 击败 12.68% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def intToRoman(self, num):
        val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        roman_num = ''
        i = 0
        while num > 0:
            for _ in range(num // val[i]):
                roman_num += syms[i]
                num -= val[i]
            i += 1
        return roman_num

结果

执行用时 : 52 ms, 击败 34.85% 使用 Python 的用户

内存消耗 : 13.04 MB, 击败 32.88% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def intToRoman(self, num: int) -> str:
        val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        roman_num = ''
        i = 0
        while num > 0:
            for _ in range(num // val[i]):
                roman_num += syms[i]
                num -= val[i]
            i += 1
        return roman_num

结果

执行用时 : 76 ms, 击败 5.82% 使用 Python3 的用户

内存消耗 : 16.88 MB, 击败 10.91% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
char* intToRoman(int num) {
    int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    const char* symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    char* result = (char*)malloc(20 * sizeof(char));
    result[0] = '\0';
    for (int i = 0; i < 13; i++) {
        while (num >= values[i]) {
            strcat(result, symbols[i]);
            num -= values[i];
        }
    }
    return result;
}

结果

执行用时 : 4 ms, 击败 85.58% 使用 C 的用户

内存消耗 : 6.68 MB, 击败 25.77% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public string IntToRoman(int num) {
        int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        string[] symbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        StringBuilder romanNum = new StringBuilder();
        for (int i = 0; i < 13; i++) {
            while (num >= values[i]) {
                romanNum.Append(symbols[i]);
                num -= values[i];
            }
        }
        return romanNum.ToString();
    }
}

结果

执行用时 : 60 ms, 击败 95.39% 使用 C# 的用户

内存消耗 : 44.50 MB, 击败 27.31% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    const values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    const symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
    let romanNum = '';
    for (let i = 0; i < 13; i++) {
        while (num >= values[i]) {
            romanNum += symbols[i];
            num -= values[i];
        }
    }
    return romanNum;
};

结果

执行用时 : 120 ms, 击败 48.51% 使用 JavaScript 的用户

内存消耗 : 52.22 MB, 击败 6.03% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
function intToRoman(num: number): string {
    const values: number[] = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    const symbols: string[] = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
    let romanNum: string = '';
    for (let i = 0; i < 13; i++) {
        while (num >= values[i]) {
            romanNum += symbols[i];
            num -= values[i];
        }
    }
    return romanNum;
}

结果

执行用时 : 120 ms, 击败 52.74% 使用 TypeScript 的用户

内存消耗 : 53.53 MB, 击败 5.47% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {

    /**
     * @param Integer $num
     * @return String
     */
    function intToRoman($num) {
        $values = array(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1);
        $symbols = array("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I");
        $romanNum = '';
        for ($i = 0; $i < 13; $i++) {
            while ($num >= $values[$i]) {
                $romanNum .= $symbols[$i];
                $num -= $values[$i];
            }
        }
        return $romanNum;
    }
}

结果

执行用时 : 24 ms, 击败 25.00% 使用 PHP 的用户

内存消耗 : 19.44 MB, 击败 6.25% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func intToRoman(_ num: Int) -> String {
        let values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        let symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        var romanNum = ""
        var number = num
        var i = 0
        while number > 0 {
            while number >= values[i] {
                romanNum += symbols[i]
                number -= values[i]
            }
            i += 1
        }
        return romanNum
    }
}

结果

执行用时 : 16 ms, 击败 87.88% 使用 Swift 的用户

内存消耗 : 14.98 MB, 击败 6.06% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    fun intToRoman(num: Int): String {
        val values = listOf(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
        val symbols = listOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
        var romanNum = ""
        var number = num
        var i = 0
        while (number > 0) {
            while (number >= values[i]) {
                romanNum += symbols[i]
                number -= values[i]
            }
            i++
        }
        return romanNum
    }
}

结果

执行用时 : 212 ms, 击败 55.56% 使用 Kotlin 的用户

内存消耗 : 38.36 MB, 击败 27.78% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
  String intToRoman(int num) {
    List<int> values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    List<String> symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
    String romanNum = '';
    for (int i = 0; i < 13; i++) {
      while (num >= values[i]) {
        romanNum += symbols[i];
        num -= values[i];
      }
    }
    return romanNum;
  }
}

结果

执行用时 : 440 ms, 击败 50.00% 使用 Dart 的用户

内存消耗 : 149.71 MB, 击败 50.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
func intToRoman(num int) string {
    values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
    var romanNum strings.Builder
    for i := 0; i < 13; i++ {
        for num >= values[i] {
            romanNum.WriteString(symbols[i])
            num -= values[i]
        }
    }
    return romanNum.String()
}

结果

执行用时 : 4 ms, 击败 88.52% 使用 Go 的用户

内存消耗 : 2.93 MB, 击败 89.29% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# @param {Integer} num
# @return {String}
def int_to_roman(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"]
    roman_num = ''
    (0...13).each do |i|
        while num >= values[i]
            roman_num += symbols[i]
            num -= values[i]
        end
    end
    roman_num
end

结果

执行用时 : 88 ms, 击败 50.00% 使用 Ruby 的用户

内存消耗 : 206.59 MB, 击败 -% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
object Solution {
  def intToRoman(num: Int): String = {
    val values = List(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
    val symbols = List("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
    var romanNum = ""
    var number = num
    var i = 0
    while (i < 13) {
      while (number >= values(i)) {
        romanNum += symbols(i)
        number -= values(i)
      }
      i += 1
    }
    romanNum
  }
}

结果

执行用时 : 500 ms, 击败 66.67% 使用 Scala 的用户

内存消耗 : 53.13 MB, 击败 100.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
    pub fn int_to_roman(num: i32) -> String {
        let values = vec![1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
        let symbols = vec!["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
        let mut roman_num = String::new();
        let mut number = num;
        for i in 0..13 {
            while number >= values[i] {
                roman_num += symbols[i];
                number -= values[i];
            }
        }
        roman_num
    }
}

结果

执行用时 : 4 ms, 击败 63.10% 使用 Rust 的用户

内存消耗 : 2.11 MB, 击败 25.00% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
(define (int-to-roman num)
  (define values '(1000 900 500 400 100 90 50 40 10 9 5 4 1))
  (define symbols '("M" "CM" "D" "CD" "C" "XC" "L" "XL" "X" "IX" "V" "IV" "I"))
  (define (convert num values symbols)
    (let loop ((num num) (values values) (symbols symbols) (result '()))
      (cond
        ((= num 0) (apply string-append (reverse result)))
        ((>= num (car values))
         (loop (- num (car values)) values symbols (cons (car symbols) result)))
        (else (loop num (cdr values) (cdr symbols) result)))))
  (convert num values symbols))

结果

执行用时 : 240 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 99.15 MB, 击败 100.00% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
defmodule Solution do
  @spec int_to_roman(num :: integer) :: String.t
  def int_to_roman(num) do
    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"]
    int_to_roman(num, values, symbols, "")
  end
  defp int_to_roman(_, [], _, acc), do: acc
  defp int_to_roman(num, [value | rest_values], [symbol | rest_symbols], acc) when num >= value do
    int_to_roman(num - value, [value | rest_values], [symbol | rest_symbols], acc <> symbol)
  end
  defp int_to_roman(num, [_ | rest_values], [_ | rest_symbols], acc) do
    int_to_roman(num, rest_values, rest_symbols, acc)
  end
end

结果

执行用时 : 556 ms, 击败 100.00% 使用 Elixir 的用户

内存消耗 : 68.21 MB, 击败 100.00% 使用 Elixir 的用户