[力扣_12] 整数转罗马数字

题目入口:点击进入

相关算法:

  • 暴力破解——时间复杂度O(1),空间复杂度——O(1)
  • 贪心算法——时间复杂度O(1),空间复杂度——O(1)

思路与算法:

这道题之所以是中等难度的题,很大一部分是它涉及了一个我们未深入接触过的罗马数字,而且也是贪心算法的一个入门了解

暴力破解

因为罗马数字给定的范围是1-3999,而所给定的个、十、百、千对应的罗马数字也都列举了出来,所以时间和空间都是常数级别

我们可以使用一个二维数组将个、十、百、千的所有相对应的罗马数字枚举出来,然后依照给定的数字进行字符串的拼接即可,表格如下所示:

img

由于给定了数据最大为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。

所以,我们将哈希表按照从大到小的顺序排列,然后遍历哈希表,直到表示完整个输入。

<video controls="" src="https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/%E6%BC%94%E7%A4%BA.webm";></video>

代码如下所示:

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;
}

本文链接:

https://nullcode.fun/58.html
1 + 9 =
快来做第一个评论的人吧~