Conversion of Roman numerals to integers (Question number 12)
The title
Roman numerals contain the following seven characters: I, V, X, L, C, D and M.
I 1 V 5 X 10 L 50 C 100 D 500 M 1000Copy the codeFor example, the Roman numeral 2 is written II, which means two 1s side by side. Let’s write 12 as XII, which is X plus II. 27 write XXVII, XX + V + II.
In Roman numerals, the smaller number is usually placed to the right of the larger number. But there are exceptions. For example, instead of writing IIII for 4, I would write IV. The number 1 is to the left of the number 5, which is equal to the large number 5 and the number 4 is obtained by reducing the number 1. Similarly, the number 9 is represented as IX. This particular rule only applies in 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. C can be placed 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 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.
Tip:
1 <= s.length <= 15 STR contains only characters (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’). The title data guarantees that s is a valid Roman numer and that the integer is in the range [1, 3999]. All the test cases are in accordance with the rules of Roman numerals. Examples like IL and IM don’t fit the problem. 49 should be XLIX, 999 should be CMXCIX.
link
Leetcode-cn.com/problems/ro…
explain
First of all, we need to look at the topic, which has two key points:
- In Roman numerals, the smaller number is usually placed to the right of the larger number
- A bunch of special cases where decimals come before larger numbers
I’m not going to go into the second point, which is the most important thing to do, but I’m not going to forget the first point, which is to say that all the numbers are from the largest to the smallest except in special cases, and that way, it’s a lot easier, because you don’t have to deal with the fact that the decimal is in front of the larger number but it’s not a special case.
Your own answer
var romanToInt = function(s) {
var kvObj = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
var sArr = s.split('')
var res = 0
for (let i = 0; i < sArr.length; i++) {
var item = kvObj[sArr[i]]
if (kvObj[sArr[i]] < kvObj[sArr[i + 1]]) {
res += kvObj[sArr[i + 1]] - item
i++
} else {
res += item
}
}
return res
};
Copy the codeThe idea is simple. First, give an Arabic numeral for each Roman numeral and make it into an object.
If the next one is bigger than the last one, then that’s the special case, and the rule for the special case is to subtract the difference between the large number and the decimal number, so that’s easy to do in the loop.
If the next number is larger than the current number, then it’s a special case, take the difference, add it to res, and i++, skip the next loop; If not, then normal accumulation can be.
The overall logic is simple, but I have found a better way.
A better way
var romanToInt = function(s) {
const table = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
};
let sum = 0;
let pre = table[s[0]];
for (let i = 1; i < s.length; i++) {
let cur = table[s[i]];
if (pre < cur) {
sum -= pre;
} else {
sum += pre;
}
pre = cur;
}
sum += pre;
return sum;
};
Copy the codeAs you can see here, the principle is the same, which is to use an object to store the relationship between the Roman numeral and the Arabic numeral, and then start to loop through the array of Roman numeral.
The point is inside the loop, where the comparison between the current element and the next element is replaced by the comparison between the current element and the previous element, and the pre variable is defined. If the next element is greater than the previous one, which violates the Roman numerals order from largest to smallest, then this proves to be a special case.
The special case is just subtracting the smaller number, plus the larger number, so the judgment here becomes a simple addition and subtraction.
Feels a little more logically simple than my own answer.
But I don’t think it’s easy to understand.
The original answer is here for those who are interested
Longest common prefix (Question number 14)
The title
Write a function to find the longest common prefix in an array of strings. Returns an empty string “” if no common prefix exists.
Example 1: Input: STRS = [“flower”,”flow”,”flight”] Output: “fl”
Example 2: Input: STRS = [“dog”,”racecar”,”car”] Output: “” Explanation: The input does not have a common prefix.
Tip:
0 <= strs.length <= 200
0 <= STRS [I]. Length <= 200 STRS [I] Consists of lowercase letters only
link
Leetcode-cn.com/problems/lo…
explain
The answer should come to mind at the first sight of this question. Normal loop is enough to iterate over each word and extract the common part of them. The loop is over until the last word and the common part of all words is enough.
But is this really the best way? Obviously not. See the better way.
Your own answers (classic violence search)
var longestCommonPrefix = function(strs) {
var res = []
for (let index = 0; index < strs.length; index++) {
var sArr = strs[index].split('')
if (sArr.length === 0) return ''
if (index === 0) {
res = sArr
} else {
var temp = []
for (let index = 0; index < sArr.length; index++) {
if (sArr[index] === res[index]) {
temp.push(sArr[index])
if (index + 1 === sArr.length) res = temp
} else {
res = temp;
if (res.length === 0) return ""
break;
}
}
}
}
return res.join('')
};
Copy the codeViolent lookup is simple, iterate over and over again, and then compare with the public RES, all the way to the end.
A better way (sort)
Var longestCommonPrefix = function(STRS) {var res = [] if (strs.length === 0) return "" if (strs.length === = 1) return STRS [0]; Var lastArr = newArr[newarr.length-1].split(") var lastArr = newArr[newarr.length-1].split(") var firstArr = strs.sort() NewArr [0]. The split (') / / free after returns an empty string if (firstArr. Length = = = 0 | | lastArr. Length = = = 0) return '/ / compare the first and the last element, For (let index = 0; index < lastArr.length; index++) { if (lastArr[index] === firstArr[index]) { res.push(lastArr[index]) } else { break; } // Return the prefix return res.join('')};Copy the codeThe code is easy to write, but it’s hard to think about it.
First of all, the classical sort, string sort is actually according to the alphabetic order, take 🌰 :
Given array [‘fun’, ‘funny’, ‘find’]
To sort them:
var strs = ['fun', 'funny', 'find']
strs.sort()
Copy the codePrint the STRS:
console.log(strs) // ["find", "fun", "funny"]
Copy the codeI’m going to sort the first letter, because everybody starts with f, so I don’t care; The second letter is u, u and I.
So that’s [“find”, “funny”, “fun”].
And then the third letter, because find is two letters ahead, so don’t worry about it, we’re all n, we’re going to move on to the next one, and we’re going to do a little bit of comparison, and we’re going to get the sorted STRS.
So the first and last strings you get are the sorted strings, and the sorted strings are in the order in which the letters appear.
Now just compare the last one with the first, and you get the longest common prefix for the entire array.
It’s really easy to implement. The hard part is thinking about it.
PS: To view past articles and titles, click on the link below:
Here’s 👇 by date
Front Brush path – Directory (Date classification)
After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇
Front brush problem path – Catalogue (Question type classification)
Those who are interested can also check out my personal homepage 👇
Here is RZ