It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
Apparently, many engineers take measures on the site called LetCode.
It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.
I wrote it in a big way, but I have no plans to have such an interview at the moment.
However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time.
I'm solving it with Python3.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day73 starting from zero "1491. Average Salary Excluding the Minimum and Maximum Salary"
Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.
Twitter I'm doing it.
** Technical Blog Started! !! ** ** I think the technology will write about LetCode, Django, Nuxt, and so on. ** This is faster to update **, so please bookmark it!
12. Integer to Roman The difficulty level is Medium.
I had a bad feeling because there are more Bads ...
Roman numerals are represented by seven different symbols. It is represented by seven different symbols: I, V, X, L, C, D and M. In this problem, it is converted as follows.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written in Roman numerals as II, which is simply the sum of two 1s. 12 is written as XII, but this is just X + II. The number twenty-seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written from left to right, from larger to smaller. But the number 4 is not IIII. Instead, the number 4 is written as IV. 1 is in front of 5, so subtract it to get 4. The number 9 is written as IX on the same principle. There are six examples of using subtraction.
If I is placed before V (5) and X (10), it becomes 4 and 9. If X precedes L (50) and C (100), it becomes 40 and 90. Putting C in front of D (500) and M (1000) gives 400 and 900.
The problem is to design an algorithm that converts to Roman numerals according to the above rules when an integer is given.
The input is confirmed to be in the range of 1 to 3999.
Example 1: Input: 3 Output: "III"
Example 2: Input: 4 Output: "IV"
Example 3: Input: 9 Output: "IX"
Example 4: Input: 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3.
Example 5: Input: 1994 Output: "MCMXCIV" Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
class Solution:
def intToRoman(self, num: int) -> str:
nums = (1000,900,500,400,100,90,50,40,10,9,5,4,1)
roman = ("M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I")
ans = ""
while num != 0:
for i, j in enumerate(nums):
if num >= j:
num -= j
ans += roman[i]
break
return ans
# Runtime: 52 ms, faster than 60.03% of Python3 online submissions for Integer to Roman.
# Memory Usage: 13.9 MB, less than 33.48% of Python3 online submissions for Integer to Roman.
Hold each value in nums and roman, rotate the for statement until it becomes 0, decrease by j only when the value is j or more, and add the index of roman to ʻans`. ,.
Since the values of nums and roman match, the index can be used as it is.
When I think about it now, I don't think it's easier to use a dictionary.
In addition, some discuss responds as follows by brute force.
class Solution(object):
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
result = []
if num>=1000:
times = num/1000
result.append(times*'M')
num = num%1000
if num>=900:
result.append('CM')
num -=900
if num>=500 and num<900:
result.append('D')
num -= 500
if num>=400 and num<500:
result.append('CD')
num-=400
if num >=100 and num<400:
times = num/100
result.append(times *'C')
num = num%100
if num >=90 and num<100:
result.append('XC')
num-=90
if num >=50 and num<90:
result.append('L')
num-=50
if num>=40 and num<50:
result.append('XL')
num-=40
if num>=10 and num<40:
times = num/10
result.append(times*'X')
num %= 10
if num==9:
result.append('IX')
num-=9
if num>=5 and num<9:
result.append('V')
num-=5
if num==4:
result.append('IV')
num-=4
if num>=1 and num<=3:
result.append(num*'I')
num-=num
return ''.join(result)
# Runtime: 20 ms, faster than 99.65% of Python online submissions for Integer to Roman.
# Memory Usage: 12.7 MB, less than 65.50% of Python online submissions for Integer to Roman.
https://leetcode.com/problems/integer-to-roman/discuss/715614/Clean-easy-and-fast-Python-Solution
Submitted in Python instead of Python3.
After solving it, I feel like I somehow understood the reason why there are so many Bads ...
So that's it for this time. Thank you for your hard work.
Recommended Posts