Today share the Roman word to change the algorithm ~

Here is the original question:
Roman numerals contain the following seven characters: I, V, X, L, C, D and M. Character value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, the Roman numeral 2 is written as II, which is the parallel 1. Write XII as X + II. Write XXVII as XX + V + II. Usually, the smaller Roman numerals are to the right of the larger numerals. But there are exceptions, for example, 4 is not written as IIII, it's written as IV. The number 1 is to the left of the number 5 and represents the number 4 when the larger number 5 decreases by 1. Similarly, the number 9 represents IX. This particular rule applies only to the following six cases: I can be placed to the left of V (5) and X (10) to represent 4 and 9. X can be placed to the left of L (50) and C (100) to represent 40 and 90. We can put C to the left of D (500) and M (1000) to represent 400 and 900. Given a Roman numeral, convert it to an integer. Make sure the input is in the range of 1 to 3999. Example 1: Input: "III" Output: 3 Example 2: Input: "IV" Output: 4 Example 3: Input: "IX" Output: 9 Example 4: Input: "LVIII" Output: 58 Description: L = 50, V= 5, III = 3. Example 5: Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90, IV = 4. Note: All test cases in the question comply with the Roman numerals writing rules, and there will be no cross-position. Examples like IC and IM don't fit the question, 49 should be XLIX, 999 should be CMXCIX. For detailed rules for writing Roman numerals, see Roman numerals - Mathematics.Copy the code

Source: LeetCode

Violent solution

At that time, after reading the problem, my first instinct was to write a violent solution. The idea was to compile the changes caused by the left side of the three letters I/X/C into a dictionary, and then complete the problem by using the triadic operation of conditional judgment. However, there are significant shortcomings in computing time and efficiency.


/ * * *@param {string} s
 * @return {number}* /
var keyMap = {
    "I": 1."V": 5."X": 10."L": 50."C": 100."D": 500."M": 1000
}
var nextI = {
    "V": 4."X": 9
}
var nextX = {
    "L": 40."C": 90
}
var nextC = {
    "D": 400."M": 900
}
var romanToInt = function(s) {
    let jumpKey = false
    let subV = 0
    s = s.split(' ');
    s.forEach( (value, index, arr) = > {
        // console.log(`current index ${index} all length ${s.length}`)
        if (jumpKey) {// Jump a loop
            jumpKey = false;
            return true;/ / equivalent continue
        }
        if( index < s.length - 1) {
           jumpKey = (value === 'I' && nextI[s[index + 1]]) || (value === 'X' && nextX[s[index + 1]]) || (value === 'C' && nextC[s[index + 1]])
           
           subV += (value === 'I' && nextI[s[index + 1]]) 
                    || (value === 'X' && nextX[s[index + 1]]) 
                    || (value === 'C' && nextC[s[index + 1]])
                    || keyMap[value];
            // console.log(`current value = ${value} subV = ${subV}`)
        } else {
            subV += keyMap[value]
            // console.log(`current value = ${value} subV = ${subV}`)}})return subV
};
Copy the code
Method to optimize

Later, I saw the ideas of others and found the following solution. The most crucial point is to grasp the rule of the change of Roman characters by using the characteristics of reduce accumulation. That is, if the left side is less than the right side, it is the difference between the two, and if the left side is greater than the right side, it is the sum of the two

Write pseudocode as follows:

if (left < right) {
	return - left + right
} else if (left > right) {
	return left + right
}
Copy the code

An improved (this time using TS) TS Reduce solution follows the above rule


const keyMap = {
    "I":1."V":5."X":10."L":50."C":100."D":500."M":1000
}
function romanToInt(s: string) :number {
    let sArr: string[] = s.split(' ');
    let res = sArr.reduce( ( prev:number , curr:string, index:number, arr:string[] ) = > {
        if( keyMap[curr] < keyMap[sArr[index + 1]]) {
            return prev - keyMap[curr] 
        }
        return  prev + keyMap[curr]
    }, 0)
    return res
};


Copy the code