返回

[Leetcode]12. Integer to Roman(C++)

题目描述

题目链接:12. Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

例子

例子 1

Input: 3 Output: “III”

例子 2

Input: 4 Output: “IV”

例子 3

Input: 9 Output: “IX”

例子 4

Input: 58 Output: “LVIII” Explanation: L = 50, V = 5, III = 3.

例子 5

Input: 1994 Output: “MCMXCIV” Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

解题思路

首先找到规律,对于十进制的数字来说,每一位数字 n 和对应大小(1, 5, 10)的罗马符号 a, b, c 分别有以下四种情况:

  • n <= 4n * 'a'
  • n == 4: 'a' + 'b'
  • 4 < n <= 8: 'b' + (n - 5) * 'a'
  • n == 9: 'a' + 'c'

了解这个规律之后,只要对每一位数字依次处理即可,为了方便 std::string 方便操作,可以先倒着放进去,最后翻转一下即可:

#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::string intToRoman(int num) {
        std::string result = "";

        // 0 ~ 9
        helper(num, 'I', 'V', 'X', result);
        num /= 10;

        // 10 ~ 90
        helper(num, 'X', 'L', 'C', result);
        num /= 10;

        // 100 ~ 900
        helper(num, 'C', 'D', 'M', result);
        num /= 10;

        // 1000 ~ 3000
        if (num > 0) {
            result += std::string(num, 'M');
        }

        std::reverse(result.begin(), result.end());

        return result;
    }

private:
    void helper(int num, char small, char median, char large, std::string& result) {
        if (num == 0) return;

        int res = num % 10;
        if (res <= 3) {
            result += std::string(res, small);
        } else if (res == 4) {
            result += median;
            result += small;
        } else if (res <= 8) {
            result += std::string(res - 5, small);
            result += median;
        } else {
            result += large;
            result += small;
        }
    }
};
  • 时间复杂度: O(1)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 12.IntegerToRoman.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy