Why my code could be accepted?


  • 1
    F
    int romanToInt(char* s) {
    int num[7] = { 0 }, i = 0, N = 0;
    char I, X, V, L, C, D, M;
    for (i = 0; i<strlen(s); i++) {
    	if (s[i] == 'I')   num[s[i]] = 1;
    	if (s[i] == 'X')   num[s[i]] = 10;
    	if (s[i] == 'V')   num[s[i]] = 5;
    	if (s[i] == 'L')   num[s[i]] = 50;
    	if (s[i] == 'C')   num[s[i]] = 100;
    	if (s[i] == 'D')   num[s[i]] = 500;
    	if (s[i] == 'M')   num[s[i]] = 1000;
    
    }
    
    for (i = 0; i<strlen(s); i++) {
    	if (num[s[i]]<num[s[i + 1]])
    		N = N - num[s[i]];
    	else N = N + num[s[i]];
    
    }
    
    return N;
    }

  • 0
    S

    So Amazing!!!
    I had tested it again and again, the result is completely right.But I completely can't understand its logic.


  • 0
    S

    Except overflow, I think I have understood the reason,at least in the aspects of logic,why this solution can be accepted.


  • 1
    S

    I think your solution should be adjusted as following:

    class Solution {
        public:
            int romanToInt(string s) {
                int len = s.length();
                int res = 0; // result
                
                int val[128];
                val['I'] = 1;
                val['V'] = 5;
                val['X'] = 10;
                val['L'] = 50;
                val['C'] = 100;
                val['D'] = 500;
                val['M'] = 1000;
                
                for(int i = 0; i < len - 1; i++) {
                    if(val[s[i]] >= val[s[i+1]]) {
                        res += val[s[i]];
                    } else {
                        res -= val[s[i]];
                    }
                }
                
                // deal with the last numeral
                res += val[s[len - 1]];
                
                return res;
            }
        };

  • 1
    Q
    Maybe you could refer to the definition of [roman numerals][1].
    
    At first, you convert every character to integer.
    Then, you judge if the former integer is lower than the latter (num[s[i]]<num[s[i + 1]]).
    In roman numerals, symbols/characters are placed from left to right in order of value, starting with the largest. While the value of the left symbol is less than the right, it means the left one should be subtracted.
    So if the former integer integer is lower than the latter, it should be subtracted from N. If not, Add it to N.
    
    Hope to help.
    

  • 0
    F

    yeah, this is my girlfriend's solution,and I also cant understand it.


  • 0
    F

    yes,you are right!


  • 0
    F

    Thank you very much,my friend~
    but, the point that I can't understand is the length of the array num[] is 7, but the index of s[i] in num[s[i]] is much more than 7.Why it can passed the test?


  • 0
    Q

    Oh~ Sorry. :)


Log in to reply
 

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