Leetcode: Integer to Roman

Datetime:2016-08-23 01:20:59          Topic: LeetCode           Share

Question:

Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Analyze:

Just handle each digit in the number.

For numbers from [0, 9], they are mapping to:

0 – ‘ ‘

1 – ‘I’

2 – ‘II’

3 – ‘III’

4 – ‘IV’

5 – ‘V’

6 – ‘VI’

7 – ‘VII’

8 – ‘VIII’

9 – ‘IX’

The patten is that for digit in [0,3], repeat ‘I’ digit times;

for digit == 4, ‘IV’

for digit in [5, 8], put digit-5 times ‘I’ after ‘V’;

for digit == 9, ‘IX’

Then from 10 – 90, using ‘X’, ‘L’, ‘C’ instead of ‘I’, ‘V’, ‘X’. So if we store all the available chars in an array, it just move the base index += 2 each time we handle next digit.

Code

C++ Code

char* intToRoman(int num) {
    char chars[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M', 'C', 'D'};
    char * result = malloc(100);
    if(num <= 0 || num >= 4000)
        return result;

    int tail = 100;
    int charBase = 0;
    while(num != 0)
    {
        int digit = num % 10;
        char temp[3];
        int templen = 0;
        if(digit <= 3)
        {
            for(int i = 1; i <= digit; ++i)
            {
                temp[i-1] = chars[charBase];
            }
            templen = digit;
        } 
        else if (digit == 4)
        {
            temp[0] = chars[charBase];
            temp[1] = chars[charBase + 1];
            templen = 2;
        }
        else if(digit <= 8)
        {
            temp[0] = chars[charBase + 1];
            templen = 1;
            for(int i = 6; i <= digit; ++i)
            {
                temp[i-5] = chars[charBase];
                templen += 1;
            }
        } 
        else
        {
            temp[0] = chars[charBase];
            temp[1] = chars[charBase + 2];
            templen = 2;
        }

        //copy temp to result
        tail = tail - templen;
        for(int i = 0; i < templen; ++i)
        {
            result[tail + i] = temp[i];
        }

        charBase += 2;
        num /= 10;
    }

    //move result to start
    for(int i = tail; i < 100; ++i) {
        result[i-tail] = result[i];
        result[i] = 0;
    }

    return result;
}




About List