Вариант решения задачи на языке программирования Python с LeetCode. Категория: Алгоритмы. Название задачи: Roman to Integer. Сложность: Легкая. Статус решения: "Решено".
Условие задачи: Римские цифры представлены семью разными символами: I, V, X, L, C, D и M.
Например, 2 записывается как II римскими цифрами, состоящими из двух единиц. 12 записывается как XII, то есть просто X + II. Число 27 записывается как XXVII, то есть XX+V+II.
Римские цифры обычно пишутся от большего к меньшему слева направо. Однако цифра для четырех не IIII. Вместо этого число четыре записывается как IV. Поскольку единица стоит перед пятью, мы вычитаем ее, получая четыре. Тот же принцип применим к числу девять, которое записывается как IX. Существует шесть случаев, когда используется вычитание:
I можно поместить перед V(5) и X(10), чтобы получить 4 и 9. X можно поместить перед L(50) и C(100), чтобы получить 40 и 90. C можно разместить перед D(500) и M(1000), чтобы получить 400 и 900. Преобразуйте римские цифры в целое число.
Решение:
Python
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
# Создаем словарь для соответствия арабских цифр и римских символов
roman_to_int = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
# Переменная для хранения результата
num = 0
# Переменная для хранения значения предыдущего символа
# Это поможет определить, нужно ли прибавлять или вычитать текущее значение
prev_value = 0
# Обрабатываем строку в обратном порядке (справа налево)
for char in s[::-1]:
# Получаем числовое значение текущего римского символа
current_value = roman_to_int[char]
# Если текущее значение меньше предыдущего, вычитаем его из результата
if current_value < prev_value:
num -= current_value
else:
# В остальных случаях прибавляем значение
num += current_value
# Обновляем значение предыдущего символа
prev_value = current_value
# Возвращаем итоговое число
return num
Объяснение кода
Словарь roman_to_int: Создаем словарь, где ключи - это римские цифры, а значения - соответствующие арабские числа.
Инициализация переменных: num - будет хранить итоговое число. prev_value - будет хранить значение предыдущего символа для определения, нужно ли вычитать или добавлять текущее значение.
Итерация по строке в обратном порядке: Проходим по строке с римским числом справа налево. Это важно, так как вычитание происходит только для символов, стоящих перед большими по значению символами.
Сравнение значений: Если текущее значение меньше предыдущего, то мы вычитаем его из num (это случай, когда используется вычитание для представления чисел 4, 9, 40 и т.д.).
Иначе, мы просто добавляем текущее значение к num.
Обновление prev_value: После каждой итерации обновляем prev_value, чтобы использовать его для сравнения на следующем шаге.
Возврат результата: После обработки всех символов в строке, в переменной num будет содержаться итоговое арабское число.
Почему начинаем с конца? Идея идти с конца заключается в том, что вычитание в римских цифрах происходит только когда меньший символ стоит перед большим. Идя с конца, мы всегда сравниваем текущий символ с предыдущим, который уже был обработан. Таким образом, мы можем точно определить, нужно ли вычитать или добавлять текущее значение.
Вариант решения задачи на языке программирования Python с LeetCode. Категория: Алгоритмы. Название задачи: Integer to Roman. Сложность: Средняя. Статус решения: "Решено".
Условие задачи: Семь различных символов представляют римские цифры со следующими значениями:
Римские цифры образуются путем добавления преобразований значений десятичных знаков от самого высокого к самому низкому. Преобразование значения десятичного знака в римское число имеет следующие правила:
Если значение не начинается с 4 или 9, выберите символ максимального значения, которое можно вычесть из входных данных, добавьте этот символ к результату, вычтите его значение и преобразуйте остаток в римскую цифру.
Если значение начинается с 4 или 9, используйте субтрактивную форму , представляющую один символ, вычитаемый из следующего символа, например, 4 на 1 ( I) меньше 5 ( V): IV и 9 на 1 ( I) меньше 10 ( X): IX. Используются только следующие субтрактивные формы: 4 ( IV), 9 ( IX), 40 ( XL), 90 ( XC), 400 ( CD) и 900 ( CM).
Только степени 10 ( I, X, C, M) могут быть добавлены последовательно не более 3 раз для представления кратных 10. Вы не можете добавить 5 ( V), 50 ( L) или 500 ( D) несколько раз. Если вам нужно добавить символ 4 раза, используйте вычитательную форму .
Дано целое число, преобразуйте его в римскую цифру.
Решение:
Python
class Solution(object):
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
# Создаем словарь для соответствия арабских цифр и римских символов
roman_numerals = {
1000: 'M',
900: 'CM',
500: 'D',
400: 'CD',
100: 'C',
90: 'XC',
50: 'L',
40: 'XL',
10: 'X',
9: 'IX',
5: 'V',
4: 'IV',
1: 'I'
}
# Создаем пустую строку для результата
result = ""
# Проходим по ключам словаря в порядке убывания
for value, symbol in sorted(roman_numerals.items(), reverse=True):
# Пока число больше или равно текущему значению:
while num >= value:
# Добавляем соответствующий римский символ к результату
result += symbol
# Вычитаем значение из числа
num -= value
return result
Объяснение кода
Словарь roman_numerals: Создается словарь, где ключи - это десятичные значения, а значения - соответствующие римские символы.
Важно, что ключи расположены в порядке убывания, чтобы мы могли эффективно обрабатывать число.
Словарь учитывает как обычные значения (1, 5, 10 и т.д.), так и специальные случаи для вычитательных форм (4, 9, 40 и т.д.).
Инициализация result: Создается пустая строка, в которую будет записываться окончательный результат в римских цифрах.
Итерация по словарю: Мы проходим по элементам словаря в порядке убывания ключей. Для каждого ключа (десятичного значения) и соответствующего значения (римского символа): Проверяем, больше ли оставшееся число (num) текущего значения. Если да, то добавляем римский символ к результату и вычитаем значение из числа. Этот процесс повторяется, пока число не станет меньше текущего значения.
Возврат результата: После завершения цикла, в строке result будет содержаться римское представление исходного числа.
Вариант решения задачи на языке программирования Python с LeetCode. Категория: Алгоритмы. Название задачи: Контейнер с большим количеством воды. Сложность: Средняя. Статус решения: "Решено".
Условие задачи: Вам дан целочисленный массив высотой длины n. Нарисовано n вертикальных линий, конечными точками которых являются (i, 0) и (i, высота[i]).
Найдите две линии, которые вместе с осью X образуют контейнер, в котором содержится больше всего воды.
Возвращайте максимальное количество воды, которое может хранить контейнер. Примечание: контейнер наклонять нельзя.
Ввод: height = [1,8,6,2,5,4,8,3,7] Вывод: 49 Пояснение: Вышеупомянутые вертикальные линии представлены массивом [1,8,6,2,5,4,8,3,7]. В этом случае максимальная площадь воды (синяя секция на картинке), которую может содержать контейнер, равна 49.
Источник изображения: leetcode.com
Решение:
Python
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
# Инициализируем два указателя: левый (left) и правый (right), а также переменную для хранения максимальной площади (max_area)
left = 0
right = len(height) - 1
max_area = 0
# Используем двухуказательный подход для нахождения максимальной площади
while left < right:
# Вычисляем текущую ширину контейнера
width = right - left
# Вычисляем текущую площадь, ограничиваясь меньшей из высот двух указателей
current_area = width * min(height[left], height[right])
# Обновляем максимальную площадь, если текущая больше
max_area = max(max_area, current_area)
# Двигаем указатели: уменьшаем меньшую высоту для возможного увеличения площади
if height[left] < height[right]:
left += 1
else:
right -= 1
# Возвращаем максимальную площадь
return max_area
Объяснение кода
Инициализация указателей и переменной для площади: Мы используем два указателя left (начало массива) и right (конец массива), чтобы проверять все возможные пары линий, начиная с самых крайних. max_area инициализируем значением 0, так как это минимально возможная площадь.
Основная логика: В цикле while мы продолжаем сравнивать линии, пока указатели не встретятся.
На каждой итерации: 1) Вычисляем ширину контейнера как расстояние между указателями: width = right - left. 2) Определяем минимальную высоту из двух линий: min(height[left], height[right]), так как именно она ограничивает высоту воды. 3) Вычисляем текущую площадь: current_area = width * min(height[left], height[right]). 4) Сравниваем текущую площадь с максимальной, и если она больше, обновляем max_area.
Движение указателей: Чтобы увеличить вероятность нахождения большего контейнера, мы двигаем указатель, связанный с меньшей высотой. Это связано с тем, что перемещение большей высоты не увеличит максимальную площадь.
Возвращаем результат: После завершения цикла возвращаем max_area, что и будет ответом.
