My java solution easy to understand


  • 144
    L

    Reference:
    http://blog.csdn.net/beiyeqingteng/article/details/8547565

    public class Solution {
    public String intToRoman(int num) {

        int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        
        StringBuilder sb = new StringBuilder();
        
        for(int i=0;i<values.length;i++) {
            while(num >= values[i]) {
                num -= values[i];
                sb.append(strs[i]);
            }
        }
        return sb.toString();
    }
    

    }


  • 0
    M

    thank you, good idea. use table to memory.


  • 26
    F

    Your function is not really optimal because you will ALWAYS iterate until the end of your values array even if your number becomes zero! Which is not optimal at all.

    In addition to that you didn't even check if the input number has a valid roman representation. You had to check that (even if the exercice assumes that the number has it already), you can do that easily with one line.

    Here is an improvement of your function :

    public static String intToRoman(int num){
    	if (num < 1 || num > 3999) return "";
    	
    	StringBuilder result = new StringBuilder();
    	
    	String[] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    	int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    	
    	int i = 0;
                //iterate until the number becomes zero, NO NEED to go until the last element in roman array
    	while (num >0) {
    		while ( num >= values[i]) {
    			num -= values[i];
    			result.append(roman[i]);
    		}
    		i++;
    	}
    	return result.toString();
    }
    

    As you see, you add just a simple line and you win an optimisation since the code will stop if the current number becomes zero (instead of doing additionnal iterations in the roman array).


  • 0
    K
    This post is deleted!

  • 0
    R

    I think the solution was edited based on fujitsu4's suggestion. It usually helps to put a note "Edit: ..." to prevent confusion. Anyway, thanks for the solution and the optimization idea.


  • 0

    Very nice solution! This is what I want. Thanks!


  • 0
    G

    I am confused about the rules: why we have XL as 40 and IX as 9 but we do not have IL as 39 or VL as 35???


  • 0
    G

    @guolei329 I sort of understanding why. There could not be three consecutive Xs, so after XXXIX as 39, is XL as 40.


  • 0
    J

    @Lucifer27
    Thank you so much!

    I think this solution should be the best answer based on all aspects including time, space and readability.


  • 0
    O

    @guolei329 IT's the syntax rule of Roman_numerals. please check https://en.wikipedia.org/wiki/Roman_numerals


  • 0
    H

    @fujitsu4 yes


  • 0

    @Lucifer27 nice solution, definitely simpler than building without pre-calculated table. Here's my solution without using the pre-calculated table. I use a straight math solution where first try to find the 1000's, then the 100's then 10's and finally 1's. I use the rule that you should try to find an answer by building from below unless that gives more than 3 in a row of a numeral, then you take the from above value.

    
        public int[] vals = new int[] { 1, 5, 10, 50, 100, 500, 1000 };
    
        public string IntToRoman(int num)
        {
            string s = "";
    
            int div = 1000;
            while (num > 0)
            {
                if (num >= div)
                {
                    int x = (num / div) * div;
                    s += Best(x);
                    num -= x; 
                }
                div /= 10;
            }
    
            return s;
        }
    
        public string Best(int x)
        {
            string a = FromBelow(x);
            int cnt = 1;
            for (int i = 1; i < a.Length; i++)
            {
                if (a[i] == a[i - 1]) cnt++;
                else cnt = 1;
    
                if (cnt == 4) break;
            }
            if (cnt != 4) return a;
    
            return FromAbove(x);
        }
    
        public string FromAbove(int x)
        {
            string s = "";
            int above = GetNextHighestOrEqual(x);
            s += ToChar(above);
    
            x = above - x;
            int below = GetNextLowestOrEqual(x);
            while (x > 0)
            {
                s = ToChar(below) + s;
                x -= below;
            }
            return s;
        }
    
        public string FromBelow(int x)
        {
            string s = "";
            while (x > 0)
            {
                int below = GetNextLowestOrEqual(x);
                s += ToChar(below);
                x -= below;
            }
            return s;
        }
    
        public int GetNextHighestOrEqual(int x)
        {
            for (int i = 0; i < vals.Length; i++)
            {
                if (vals[i] >= x) return vals[i];
            }
    
            return 0;
        }
    
        public int GetNextLowestOrEqual(int x)
        {
            for (int i = vals.Length - 1; i >= 0; i--)
            {
                if (vals[i] <= x) return vals[i];
            }
    
            return 0;
        }
    
        public char ToChar(int x)
        {
            switch (x)
            {
                case 1: return 'I';
                case 5: return 'V';
                case 10: return 'X';
                case 50: return 'L';
                case 100: return 'C';
                case 500: return 'D';
                case 1000: return 'M';
            }
    
            return '#';
        }
    

  • 0
    M

    Very nice, @Lucifer27! Here is a c++ version following your code:

        string intToRoman(int num)
        {
            static const struct {
                int value;
                const char* roman;
            } table[] = {
                {1000, "M" },
                { 900, "CM"},
                { 500, "D" },
                { 400, "CD"},
                { 100, "C" },
                {  90, "XC"},
                {  50, "L" },
                {  40, "XL"},
                {  10, "X" },
                {   9, "IX"},
                {   5, "V" },
                {   4, "IV"},
                {   1, "I" }
            };
    
            string res;
    
            for (const auto& item : table)
            {
                if (num == 0)
                    break;
    
                while (item.value <= num)
                {
                    num -= item.value;
                    res += item.roman;
                }
            }
    
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.