How to improve code?


  • 12
    U

    I know the easy way of solving this problem is using 23 case statements (10 for numbers [1-10], 10 for [10-100], 10 for [1000-3000]). But the code does not look good and it's getting bit long. I'm thinking even applying the rules for converting may also make the code complex. Any suggestions?


  • 14
    P

    I think the following rule works

    1. If num is 4 times of x (x = 1000, 100, 10, 1), add x 5x
    2. If num is greater than x, add x
    3. If num is smaller than x (x = 1000, 100, 10, 1) but it is 9 times of x/10, add 10/x x

    class Solution {
    public:
        string intToRoman(int num) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.    
            string result = "";
            int base[] = {1000,500,100,50,10,5,1,0};
            char baseC[] = {'M','D','C','L','X','V','I'};
            int basen = 0;
            while(num) {
                if(basen%2 == 0 && num/base[basen] == 4) {
                    result += baseC[basen];
                    result += baseC[basen-1];
                    num -= base[basen] * 4;
                } else if(num >= base[basen]) {
                    result += baseC[basen];
                    num -= base[basen];
                } else if(basen%2 == 0 && num / base[basen+2] == 9) {
                    result += baseC[basen+2];
                    result += baseC[basen];
                    num -= base[basen+2]*9;
                } else {
                    basen++;
                }
            }
            return result;
        }
    };

  • 0
    U

    cool algorithm!


  • 71
    M
    import java.util.LinkedHashMap;
    public class Solution {
    
        private static LinkedHashMap<Integer, String> numToRoman = new LinkedHashMap<Integer, String>();
        static {
            numToRoman.put(1000, "M");
            numToRoman.put(900, "CM");
            numToRoman.put(500, "D");
            numToRoman.put(400, "CD");
            numToRoman.put(100, "C");
            numToRoman.put(90, "XC");
            numToRoman.put(50, "L");
            numToRoman.put(40, "XL");
            numToRoman.put(10, "X");
            numToRoman.put(9, "IX");
            numToRoman.put(5, "V");
            numToRoman.put(4, "IV");
            numToRoman.put(1, "I");
        }
        public String intToRoman(int num) {
            for (Integer i : numToRoman.keySet()) {
                if (num >= i) {
                    return numToRoman.get(i) + intToRoman(num - i);
                }
            }
            return "";
        }
    }

  • 0
    M

    Changing the method body to use StringBuilder and a while loop will be faster than recursion. But it does make the code a bit longer.


  • 0
    T

    This is helpful.
    http://en.wikipedia.org/wiki/Roman_numerals
    Reading Roman numerals


  • 0
    class Solution {
    public:
        string intToRoman(int num) {
            string ret;
            char d[] = "--MDCLXVI";
            char *p = d, d1, d5, d10;
            int a, b, base = 1000;
            while(num){
            	d10 = *p++;
            	d5 = *p++;
            	d1 = *p;
            	a = num / base;
                b = a % 5;
            	if(b < 4){
                    if(a >= 5) ret += d5;
            		for(int i = 0; i < b; ++i) ret += d1;
            	}else{
                    ret += d1;
            		if(a == 9){
            			ret += d10;
            		}else{
            			ret += d5;
            		}
            	}
            	num -= a * base;
                base /= 10;
            }
            return ret;
        }
    };

  • 0
    Y

    This code looks really neat, but it loops many times. Will it make the code slow?


  • 0
    M

    Yes, like I mentioned in the first reply. Changing from recursion to iteration actually helped me lower the run time from 844ms to 576ms (at the cost of four extra lines).


  • 6
    G
    class Solution:
        roman_dict = [
            (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')
        ]
        def intToRoman(self, num):
            for kv in self.roman_dict:
                if kv[0] <= num:
                    return kv[1] + self.intToRoman(num - kv[0])
            return ''

  • 0
    U

    I divide it into 30 cases and list them explicitly. I notice people normally scan all the cases each time, but we actually can skip some when the number is decreased. So I add an variable "offset" to indicate where to start next scan.

    class Solution:
    decs = [3000, 2000, 1000]+range(900, 0, -100)+range(90, 0, -10)+range(9, 0, -1)
    romans = ['MMM', 'MM', 'M',
              'CM', 'DCCC', 'DCC', 'DC', 'D', 'CD', 'CCC', 'CC', 'C',
              'XC', 'LXXX', 'LXX', 'LX', 'L', 'XL', 'XXX', 'XX', 'X',
              'IX', 'VIII', 'VII', 'VI', 'V', 'IV', 'III', 'II', 'I']
    offsets = [3]*3+[12]*9+[21]*9+[30]*9
    
    # @return a string
    def intToRoman(self, num):
        roman = []
        offset = 0
        size = len(self.decs)
        while num > 0:
            for i in range(offset, size):
                if num >= self.decs[i]:
                    roman.append(self.romans[i])
                    num -= self.decs[i]
                    offset = self.offsets[i]
                    break;
        return ''.join(roman)

  • 3
    S

    This is just a C++ version translated from Java and Python solutions given by magicknife and others.

    class Solution {
    public:
        string intToRoman(int num) {                
            for (int i = 0; i < int_dict.size(); i++) {
                if (int_dict[i] <= num)
                    return roman_dict[i] + intToRoman(num - int_dict[i]);
            }
            return "";
        }
    private:
        vector<int> int_dict {1000, 900, 500, 400, 100,
                              90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> roman_dict {"M", "CM", "D", "CD", 
                              "C", "XC", "L", "XL", "X", 
                              "IX", "V", "IV", "I"};
    };

  • 0
    J

    Great! very cute


  • 1
    W
    public class Solution {
    public String intToRoman(int num) {
        StringBuffer res=new StringBuffer();
        while(num>0)
        {
            if(num-1000>=0)
            {
            res.append("M");
            num-=1000;
            }
            else if(num-900>=0)
            {
            res.append("CM");
            num-=900;
            }
            else if(num-500>=0)
            {
            res.append("D");
                num-=500;
            }
            else if(num-400>=0)
            {
            res.append("CD");
            num-=400;
            }
            else if(num-100>=0)
            {
            res.append("C");
            num-=100;
            }
            else if(num-90>=0)
            {
            res.append("XC");
            num-=90;
            }
            else if(num-50>=0)
            {
            res.append("L");
            num-=50;
            }
            else if(num-40>=0)
            {
            res.append("XL");
            num-=40;
            }
            else if(num-10>=0)
            {
              res.append("X");
                num-=10;
            }
            else if(num-9>=0)
            {
            res.append("IX");
            num-=9;
            }
            else if(num-5>=0)
            {
            res.append("V");
            num-=5;
            }
            else if(num-4>=0)
            {
            res.append("IV");
            num-=4;
            }
            else if(num-1>=0)
            {
            res.append("I");
            num-=1;    
            }
        }
        return res.toString();
    }
    

    }

    This code can avoid use extra memory space .But since there are many if judgement , I don't know this code 's time complexity.Any body have any ideas?


  • 0
    S

    if doesn't effect time complexity. In terms of time complexity, it usually counts on loops and recursions. For this particular problem, I don't think time complexity would be a problem at all.


  • 0
    S
    class Solution {
    public:
        string intToRoman(int num) {
            string res;
            int temp = num;
            int val[] = {1000, 500, 100, 50, 10, 5, 1};
            char sym[] = {'M', 'D', 'C', 'L', 'X','V', 'I'};
            
            for (int i = 0; i < sizeof(sym)/sizeof(char); i+=2)
            {
                int count = temp / val[i];
                if (count < 4)
                    res.append(count, sym[i]);
                else if (count == 4)
                {
                    res.append(1, sym[i]);
                    res.append(1, sym[i-1]);
                }
                else if (count > 4 && count < 9)
                {
                    res.append(1, sym[i-1]);
                    res.append(count - 5, sym[i]);
                }
                else if (count == 9)
                {
                    res.append(1, sym[i]);
                    res.append(1, sym[i-2]);
                }
                temp = temp % val[i];
            }
            
            return res;
        }
    };

  • 21
    C

    This is my code, I think it's concise enough.

    public class Solution {
        public String intToRoman(int num) {
            if(num>=1000) return "M"+intToRoman(num-1000);
            if(num>=900) return "CM"+intToRoman(num-900);
            if(num>=500) return "D"+intToRoman(num-500);
            if(num>=400) return "CD"+intToRoman(num-400);
            if(num>=100) return "C"+intToRoman(num-100);
            if(num>=90) return "XC"+intToRoman(num-90);
            if(num>=50) return "L"+intToRoman(num-50);
            if(num>=40) return "XL"+intToRoman(num-40);
            if(num>=10) return "X"+intToRoman(num-10);
            if(num>=9) return "IX"+intToRoman(num-9);
            if(num>=5) return "V"+intToRoman(num-5);
            if(num>=4) return "IV"+intToRoman(num-4);
            if(num>=1) return "I"+intToRoman(num-1);
            return "";
        }
    }

  • 0
    J
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    Z

    Is it ok if I put roman_dict inside of intToRoman function and change the first line of the function to "for kv in roman_dict:"? Thanks!


Log in to reply
 

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