LeetCode12. 整数转罗马数字

题目

分析

模拟 + 找规律

代码

暴力模拟

 1 class Solution {
 2 public:
 3     string intToRoman(int num) {
 4         // string roman[] ={"M","D","C","L","X","V","I"};
 5         int a[] = {3000,2000,1000,900,800,700,600,500,400,300,200,100,90,80,70,60,50,40,30,20,10,9,8,7,6,5,4,3,2,1};
 6         string roman[] =
 7         {"MMM","MM","M","CM","DCCC","DCC","DC","D","CD","CCC","CC","C","XC","LXXX","LXX","LX","L","XL","XXX","XX","X","IX","VIII","VII","VI","V","IV","III","II","I"};
 8         string res = "";
 9         for(int i = 0; i < 30;i++){
10             while(num >= a[i]){
11                 res += roman[i];
12                 num -= a[i];
13             }
14         }
15         return res;
16     }
17 };

可以简化

并不一定要存储所有罗马数字，通过模拟可以找到规律

只需要填写上面画红色圈的数字即可

 1 class Solution {
 2 public:
 3     string intToRoman(int num) {
 4         int values[] = {
 5             1000,
 6             900,500,400,100,
 7             90,50,40,10,
 8             9,5,4,1
 9         };
10         string reps[] = {
11             "M",
12             "CM","D","CD","C",
13             "XC","L","XL","X",
14             "IX","V","IV","I"
15         };
16         string res;
17         //一共十二个数
18         for(int i = 0;i <= 12;i++){
19             while(num >= values[i]){
20                 res += reps[i];
21                 num -= values[i];
22             }
23         }
24 
25         return res;
26     }
27 };