the detailed process for sloving leetcode problem 13

Frist let us see the problem

To solve the question we need find the rule to calculate the sum of those roman numbers.

Let us use the LVIII as our first example,we can see that all the roman number left is not smaller than its right,so that we can add the referring integer from right to left,it is 1+1+1+5+50=58,

And there is another situation,let us use MCMXCIV as our second example,we can find I is behind V,so we should use V subtract I to 5-1=4,and next C is bigger than I so we add C 5-1+100=104,but X is smaller than C so we subtract X 5-1+100-10=94,then 94+1000-100+1000=1994,now,we have knew how to calculate the sum of one roman number,start from right and if the left is smaller than right then use right to subtract left else add the left.

But before this we need to do sth. to let each roman equal a integer to achieve it it is recommend to transfer the form of string to vector that including the integer by the sequence for each roman number so that we are easy to calculate the sum and compare which is bigger for two roman numbers.
so we have the code as following to transfer to integer vector:

       for(char ch :s){
                switch(ch){
                case 'I':
                newvec.push_back(1);
                break;
                case 'V':
                newvec.push_back(5);
                break;
                case 'X':
                newvec.push_back(10);
                break;
                case 'L':
                newvec.push_back(50);
                break;
                case 'C':
                newvec.push_back(100);
                break;
                case 'D':
                newvec.push_back(500);
                break;
                case 'M':
                newvec.push_back(1000);
                break;

            }

            }

Then we add the calculating model as following:

int size=newvec.size();
        int sum=newvec[size-1];
        for(int i=2;i<=size;i++){
            if (newvec[size-i]<newvec[size-i+1])
            {
            sum=sum-newvec[size-i];
            }
            else{
                sum=sum+newvec[size-i];
            }

        }

        return sum;

so the full codes is :

class Solution {
public:
    int romanToInt(string s) {
         vector<int>vec;

         vector<int>newvec;
            for(char ch :s){
                switch(ch){
                case 'I':
                newvec.push_back(1);
                break;
                case 'V':
                newvec.push_back(5);
                break;
                case 'X':
                newvec.push_back(10);
                break;
                case 'L':
                newvec.push_back(50);
                break;
                case 'C':
                newvec.push_back(100);
                break;
                case 'D':
                newvec.push_back(500);
                break;
                case 'M':
                newvec.push_back(1000);
                break;

            }

            }



        int size=newvec.size();
        int sum=newvec[size-1];
        for(int i=2;i<=size;i++){
            if (newvec[size-i]<newvec[size-i+1])
            {
            sum=sum-newvec[size-i];
            }
            else{
                sum=sum+newvec[size-i];
            }

        }

        return sum;

    }
};

Blog

the detailed process for sloving leetcode problem 13

hallowaw

Join Our Newsletter. No Spam, Only the good stuff.

Related