[力扣_12] 整数转罗马数字
题目入口:点击进入
相关算法:
- 暴力破解——时间复杂度O(1),空间复杂度——O(1)
- 贪心算法——时间复杂度O(1),空间复杂度——O(1)
思路与算法:
这道题之所以是中等难度的题,很大一部分是它涉及了一个我们未深入接触过的罗马数字,而且也是贪心算法的一个入门了解
暴力破解
因为罗马数字给定的范围是1-3999,而所给定的个、十、百、千对应的罗马数字也都列举了出来,所以时间和空间都是常数级别
我们可以使用一个二维数组将个、十、百、千的所有相对应的罗马数字枚举出来,然后依照给定的数字进行字符串的拼接即可,表格如下所示:
由于给定了数据最大为3999,则我们可以根据范围来确定相应的符号,算法如下所示:
#include<stdio.h>
#include<stdlib.h>
int main()
{
char* ReturnString = (char*)malloc(sizeof(char) * 26);
int num;
printf("请输入测试数据:");
scanf("%d",&num);
char key[4][9][5] = {
{"I","II","III","IV","V","VI","VII","VIII","IX"},
{"X","XX","XXX","XL","L","LI","LII","LIII","XC"},
{"C","CC","CCC","CD","D","DC","DCC","DCCC","CM"},
{"M","MM","MMM"}
};
ReturnString[20 - 1] = '\0';
int tmp; int i, j, p = 0;
while (num > 0)
{
if (num >= 1000 && num <= 3000)
{
tmp = (num / 1000) * 1000;
i = 3, j = tmp / 1000 - 1;
}
else if (num >= 100 && num < 1000)
{
tmp = (num / 100) * 100;
i = 2, j = tmp / 100 - 1;
}
else if (num >= 10 && num < 100)
{
tmp = (num / 10) * 10;
i = 1, j = tmp / 10 - 1;
}
else
{
tmp = (num / 1) * 1;
i = 0, j = tmp / 1 - 1;
}
for (int k = 0; key[i][j][k] != '\0'; k++, p++)
{
ReturnString[p] = key[i][j][k];
}
num -= tmp;
}
ReturnString[p] = '\0';
printf("%s", ReturnString);
system("pause");
return 0;
}
贪心算法
生活中的经验:
在以前还使用现金购物的时候,如果我们不想让对方找钱,付款的时候我们会尽量选择面值大的纸币给对方,这样才会使得我们给对方的纸币张数最少,对方点钱的时候也最方便。
本题“整数转罗马数字”也有类似的思想:在表示一个较大整数的时候,“罗马数字”的设计者不会让你都用 1 加起来,我们总是希望写出来的“罗马数字”的个数越少越好,以方便表示,并且这种表示方式还应该是唯一的
贪心算法的核心思想便是如此:
贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择,也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心状态必须具有无后效性:即某个状态以前的过程不会影响以后的状态,只与当前状态有关
说明:其实在题目中已经强调了一些特例,出现 4、9、40、90、400、900 (4000、9000 不讨论了,题目测试用例中有说,不会超过 3999)的情况比较特殊一些,做的是减法,把它们也加入到“罗马数字”与阿拉伯数字的对应关系表中,并且按照从大到小的顺序排列。
贪心法则:我们每次尽量使用最大的数来表示。 比如对于 1994 这个数,如果我们每次尽量用最大的数来表示,依次选 1000,900,90,4(并且下一次的选择要基于当前选择,则每次选择较大的数,原数都需要减去它,如选择1000后,下一次的数据则为994),会得到正确结果 MCMXCIV。
所以,我们将哈希表按照从大到小的顺序排列,然后遍历哈希表,直到表示完整个输入。
代码如下所示:
char * intToRoman(int num){
int Value[13]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
char Symbol[13][3]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
char *ReturnChar=(char*)malloc(sizeof(char)*26);
int p=0;
while(num)
{
int i=0;
while(Value[i]>num)i++;
num=num-Value[i];
int j=0;
while(Symbol[i][j]!='\0')
{
ReturnChar[p]=Symbol[i][j];
j++;
p++;
}
}
ReturnChar[p]='\0';
return ReturnChar;
}