[力扣_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;
}