题意
输入整数, 转化为罗马数字输出. 具体转化规则见题面.
思路
直接做.
可以把所有可选的数值列出来, 然后从大到小选取数字. 有点像给出固定面值的硬币, 用贪心法凑固定数值所需要的最小个数的意思. 时间复杂度: 很低.
代码
- class Solution {
- public:
- string intToRoman(int num) {
- struct node
- {
- int num;
- string ch;
- } table[15] =
- {
- 1000, "M",
- 900, "CM",
- 500, "D",
- 400, "CD",
- 100, "C",
- 90, "XC",
- 50, "L",
- 40, "XL",
- 10, "X",
- 9, "IX",
- 5, "V",
- 4, "IV",
- 1, "I",
- };
- int i = 0;
- string res = "";
- while(num)
- {
- if(num>= table[i].num)
- {
- num -= table[i].num;
- res += table[i].ch;
- }
- else
- ++i;
- // cout << num << ' ' << i << endl;
- }
- return res;
- }
- };
总结
打表! 打表!! 打表!!!
来源: http://www.bubuko.com/infodetail-3395526.html