Вариант решения задачи на языке программирования Python с LeetCode.
Название задачи: Longest Palindromic Substring.
Категория: Алгоритмы.
Сложность: Средняя.
Статус решения: "Решено".
Условие задачи:
Задача на алгоритмы. Дана строка s, верните самую длинную палиндромную подстроку в s.
Решение:
Python
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# Если строка пустая или состоит из одного символа, возвращаем её саму
if len(s) <= 1:
return s
# Инициализируем переменные для хранения начала и максимальной длины палиндрома
start = 0
max_length = 1
# Вспомогательная функция для расширения границ палиндрома
def expand_around_center(left, right):
# Расширяем границы, пока символы слева и справа равны
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# Возвращаем начало и длину найденного палиндрома
return left + 1, right - left - 1
# Проходим по каждому символу строки
for i in range(len(s)):
# Проверяем палиндром нечётной длины (центр в одном символе)
left, length = expand_around_center(i, i)
if length > max_length:
start = left
max_length = length
# Проверяем палиндром чётной длины (центр между двумя символами)
if i + 1 < len(s) and s[i] == s[i + 1]:
left, length = expand_around_center(i, i + 1)
if length > max_length:
start = left
max_length = length
# Возвращаем найденный палиндром
return s[start:start + max_length]
# Пример использования
solution = Solution()
print(solution.longestPalindrome("babad")) # Вывод: "bab" или "aba"
print(solution.longestPalindrome("cbbd")) # Вывод: "bb"
Объяснение кода
Базовый случай:
Если строка пустая или состоит из одного символа, сразу возвращаем её.
Инициализация:
Задаем начальные значения для начала (start) и максимальной длины (max_length) палиндрома.
Функция расширения:
expand_around_center находит самый длинный палиндром, начиная с заданного центра (индексы left и right).
Цикл по символам:
Для каждого символа проверяем два случая:
Палиндром нечётной длины (центр в одном символе).
Палиндром чётной длины (центр между двумя символами).
Обновление результата:
Если найденный палиндром длиннее текущего, обновляем start и max_length.
Возврат результата:
После завершения цикла возвращаем подстроку с использованием start и max_length.
Этот подход эффективно находит самый длинный палиндром за время O(n²) , где n — длина строки.
Источник решения: hdhai.com
Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: Roman to Integer.
Сложность: Легкая.
Статус решения: "Решено".
Условие задачи:
Римские цифры представлены семью разными символами: I, V, X, L, C, D и M.
Symbol: I, Value: 1.
Symbol: V, Value: 5.
Symbol: X, Value: 10.
Symbol: L, Value: 50.
Symbol: C, Value: 100.
Symbol: D, Value: 500.
Symbol: M, Value: 1000.
Например, 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 будет содержаться итоговое арабское число.
Почему начинаем с конца?
Идея идти с конца заключается в том, что вычитание в римских цифрах происходит только когда меньший символ стоит перед большим. Идя с конца, мы всегда сравниваем текущий символ с предыдущим, который уже был обработан. Таким образом, мы можем точно определить, нужно ли вычитать или добавлять текущее значение.
Источник решения: hdhai.com
Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: Integer to Roman.
Сложность: Средняя.
Статус решения: "Решено".
Условие задачи:
Семь различных символов представляют римские цифры со следующими значениями:
Symbol: I, Value: 1.
Symbol: V, Value: 5.
Symbol: X, Value: 10.
Symbol: L, Value: 50.
Symbol: C, Value: 100.
Symbol: D, Value: 500.
Symbol: M, Value: 1000.
Римские цифры образуются путем добавления преобразований значений десятичных знаков от самого высокого к самому низкому. Преобразование значения десятичного знака в римское число имеет следующие правила:
Если значение не начинается с 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 будет содержаться римское представление исходного числа.
Источник решения: hdhai.com