Thursday, May 30, 2013

Integer to Roman@leetcode

微博:http://www.weibo.com/cathyhwzn

刷题必备书籍:Cracking the Coding Interview: 150 Programming Questions and Solutions
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
First of all, we need to clear of how roman numeral consist. There are corresponding number to integer in roman numeral. 
I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000.
The rule of how roman numeral forms is,
1~3 I, II, III,
4 IV,
5 V
6~8 VI, VII, VIII
9 IX
10 X
The rule of 100, 1000 are obey the consisting rule above. For example, MCMXXC = 1980, XLV = 45. 
We set a char array to put the roman elemental numeral, then we go through the number bit by bit to add the roman numeral to the string.
string intToRoman(int num)
{
   char symbol[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
   int scale = 1000;
   string roman;
   for(int i =6; i>=0; i-=2)
   {
      int digit = num/scale;
      if(digit!=0)
      {
      if(digit<=3)
      {
        roman.append(digit, symbol[i]);
      }
      else if(digit == 4)
      {
         roman.append(1,symbol[i]);
         roman.append(1,symbol[i+1]);
      }
      else if(digit == 5)
      {
         roman.append(1, symbol[i+1]);
      }
      else if(digit<=8)
      {
         roman.append(1, symbol[i+1]);
         roman.append(digit-5, symbol[i]);
      }
      else if(digit == 9)
      {
         roman.append(1,symbol[i]);
         roman.append(1,symbol[i+2]);
      }
      }
      num = num%scale;
      scale/=10;
   }

   return roman;
}



2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. 你的例子MCMXXC = 1980错了……80是LXXX不是XXC

    ReplyDelete

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...