leetcode 12. Integer to Roman numeral

​
​

作者简介：C/C++ 、Golang 领域耕耘者,创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话,还请关注 、点赞 、收藏🧡三连支持一下博主哦~~~

题目描述

罗马数字包含以下七种字符： 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.

🧡 算法分析

This problem is to simulate the topic

The first is the basic Roman Numbers（The above table in below）

We can get some laws,

1. 相同的数字连写,所表示的数等于这些数字相加得到的数,如：III=3;
2. 小的数字在大的数字的右边,所表示的数等于这些数字相加得到的数,如：VIII=8, XII=12;
3. 小的数字在大的数字的左边（限于 IV、IX、XL、XC、CD和CM）,所表示的数等于大数减小数得到的数,如：IV=4, IX=9;
4. 正常使用时,连写的数字重复不得超过三次;

So we can use a new composite characters on behalf of the new unit, In the above table below

模拟实现步骤：

1. To organize new units and numerical array
2. Directly on the need to convert Numbers to iterate over the（Began to give preference to the larger units）

代码实现

class Solution {
    
public:
    string intToRoman(int num) {
    
        // 属于模拟题
        int vals[] = {
    1000,
                    900,500,400,100,
                    90,50,40,10,
                    9,5,4,1
        };
        string reps[] = {
    "M", 
                    "CM", "D", "CD", "C", 
                    "XC", "L", "XL", "X", 
                    "IX", "V", "IV", "I"
        };

        string re;
        // To choose the big unit
        for(int i = 0; i < 13; i++)  // Because the above array there is13个数
        {
    
            while(num >= vals[i])
            {
    
                num -= vals[i];
                re += reps[i];
            }
        }
        return re;
    }
};

执行结果：

时间复杂度分析

计算量与最终罗马数字的长度成正比,对于每一位阿拉伯数字,罗马数字最多用4个字母表示（比如VIII=8）,So the length of the Roman numerals and the length of the Arabic numerals are an order of magnitude,And the length of the Arabic numerals is proportional to the number,是 O(logn),因此时间复杂度是 O(logn)

如果觉得对你有帮助的话:
点赞,你的认可是我创作的动力！
🧡 收藏,你的青睐是我努力的方向！
️ 评论,你的意见是我进步的财富！