Leetcode problems solved with Python
Integer to Roman
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.
Example 1:
Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.
Example 2:
Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
Example 3:
Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= num <= 3999
### My Solution
from math import floor
class Solution:
def intToRoman(self, num: int) -> str:
if num < 1 or num > 4000:
RaiseError("Number out of range.")
numerals = ''
values = [1000, 500, 100, 50, 10, 5, 1]
mapping = {1000: 'M', 500:"D", 100:"C", 50:"L", 10:"X", 5:"V", 1:"I"}
for i in range(len(values)):
if i == 0:
if num >= values[i]:
numerals = numerals + floor(num / values[i]) * mapping[values[i]]
else:
if (num % values[i-1]) >= values[i]:
numerals = numerals + floor((num % values[i-1]) / values[i]) * mapping[values[i]]
# clean up 9s and 4s
numerals = numerals.replace("DCCCC", "CM")
numerals = numerals.replace("CCCC", "CD")
numerals = numerals.replace("LXXXX", "XC")
numerals = numerals.replace("XXXX", "XL")
numerals = numerals.replace("VIIII", "IX")
numerals = numerals.replace("IIII", "IV")
return numerals
### Example Solution
class Solution:
def intToRoman(self, num: int) -> str:
# Creating Dictionary for Lookup
num_map = {
1: "I",
5: "V", 4: "IV",
10: "X", 9: "IX",
50: "L", 40: "XL",
100: "C", 90: "XC",
500: "D", 400: "CD",
1000: "M", 900: "CM",
}
# Result Variable
r = ''
for n in [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]:
# If n in list then add the roman value to result variable
while n <= num:
r += num_map[n]
num-=n
return r
"""
Here's how the code works:
The method starts by creating a dictionary called num_map, which maps certain integers to their corresponding Roman numeral representations. The dictionary includes values for 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000.
It initializes an empty string r to store the resulting Roman numeral.
The method then iterates through a predefined list of integers in descending order (from 1000 down to 1). This list represents the possible values in descending order for Roman numerals.
Inside the loop, there's another loop using while n <= num. This inner loop checks how many times the current integer n can be subtracted from the input num. It keeps subtracting n from num as long as num is greater than or equal to n.
In each iteration of the inner loop, the corresponding Roman numeral from the num_map dictionary is appended to the result string r, and the value of num is reduced by n.
The outer loop continues until all possible values have been considered and the entire input integer has been converted to its Roman numeral representation.
Finally, the resulting Roman numeral string is returned.
For example, if you call intToRoman(3549), the output would be the Roman numeral representation of 3549, which is "MMCMXLIX" (1000 + 1000 + 100 + 1000 - 100 + 50 - 10 + 1 - 10).
"""
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1]
Output: 1.00000
### My Solution
class Solution:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
"""
Combine lists into one long list
sort combined list
remove 1 value from either side of the sorted combined list until 1,2 or 3
elements remain
"""
m = len(nums1)
n = len(nums2)
shortlist = nums1
shortlist.extend(nums2)
shortlist.sort()
while len(shortlist) > 3:
shortlist = shortlist[1:-1]
if len(shortlist) == 1:
return shortlist[0]
elif len(shortlist) == 3:
return shortlist[1]
else:
return sum(shortlist) / 2
#### Example Solution
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
# Merge the arrays into a single sorted array.
merged = nums1 + nums2
# Sort the merged array.
merged.sort()
# Calculate the total number of elements in the merged array.
total = len(merged)
if total % 2 == 1:
# If the total number of elements is odd, return the middle element as the median.
return float(merged[total // 2])
else:
# If the total number of elements is even, calculate the average of the two middle elements as the median.
middle1 = merged[total // 2 - 1]
middle2 = merged[total // 2]
return (float(middle1) + float(middle2)) / 2.0