力扣(LeetCode)12. 整数转罗马数字(C++)

模拟

罗马数字和掰手指数数的区别在于，$IV/IX$ 这类倒着数数的，和阿拉伯数字最大的区别在于 $5$ 的 $10^k$ 倍 $k\in N$ ，需要被表示出来。所以除了记录 $I/X/C/M$ ——$1/10/100/1000$，还要记录 $V/L/D$——$5/50/500$ ，以及倒着数数的 $IV/IX/XL/XC/CD/CM$——$4/9/40/90/400/900$ 。 类比十进制 ， 从大到小 ， 循环编码即可。

代码展示

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

时间复杂度 $O(logn)$ ， $n$ 是 $num$ 的大小，循环编码时间复杂度 $O(logn)$。

空间复杂度 $O(|C|)$ ， 编码的空间复杂度 $O(|C|)$ ， $|C|=13$ 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC