Один из десятка тысяч разборов этой задачи, в большей степени перевод leetcode, очень недалёкий, но кому-то как и мне может надо прорешать задачу N раз, чтобы понять и не забывать её.
Палиндром — это такие слова, числа или символы которых читаются одинаково в обоих направлениях.
Дано: задано целое число x, вернуть True, если x является палиндромом
и False в противном случае.
Уточнение:
Отрицательные числа не являются палиндромами, из-за несимметричного знака "-" в начале.
Ограничения:
-2^31 <= x <= 2^31 - 1
Пример:
Вход: x = 121
Выходные данные: True
Пояснения: 121 читается как 121 слева направо и справа налево.
Решение(Python):
1а) Первое решение с преобразованием числа в строку и сравнение этой строки str(x) c её реверсом через цикл.
def isPalindrome(x: int) -> bool:
reverse_num = ""
for digit in str(x):
reverse_num = digit + reverse_num
reverse_num = int(reverse_num)
return reverse_num == x
Создаём пустую строку и через цикл смещаем наше число в обратно порядке reverse_num = digit + reverse_num сдвигая каждый элемент на один порядок. Дальше преобразуем полученную строку и с помощью оператора сравнения, выдаём либо true, либо false.
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: поскольку мы храним число в виде строки, где её длина N, то O(N)
Более лаконичный вариант:
def isPalindrome(x: int) -> bool:
num = str(x)
length = len(num)
for digit in range(length // 2):
if num[digit] != num[length - digit- 1]:
return False
return True
Переводим число в строку, и проходим циклом до середины строки сравнивая симметричные значением с начала num[digit] и конца строки num[length - digit- 1].
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: поскольку мы храним число в виде строки, где её длина N, то O(N)
1б) C помощью среза
def isPalindrome(x: int) -> bool:
return str(x)[::-1] == str(x)
На входе целое число: x: int, возвращаем логический оператор true или false
Преобразованием числа в строку и сравнение этой строки str(x) c её реверсом через срез str(x)[::-1] (где [::-1] - срез вида: [начальный элемент: конечный элемент: шаг среза], в данном случае пропуски начального и конечного элемента, означают значения по дефолту, то есть первый и последний, так как шаг отрицательный, то последний элемент становится первым, а первый последним). Если они равны, то это палиндром, иначе false.
Дальше дополнительно проверим, что наше число положительное:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
return str(x)[::-1] == str(x)
Временная сложность: реверс строки даёт нам O(n)
Пространственная сложность: поскольку мы храним число в виде строки, где её длина N, то O(N)
2) Через цикл без использования строки.
Если мы не хотим преобразовывать число в строку, то создаём новое число в обратном порядке:
def isPalindrome(x: int) -> bool:
if x<0:
return False
currentValue= x
newValue= 0
while x>0:
newValue= newValue* 10 + x%10
x = x//10
return newValue == currentValue
Для начала необходимо определить переменную newValue, в которой будет храниться перевернутое число. Затем используем алгоритм, придуманный для этого действа: пока исходное число не станет равным 0, будем извлекать последнюю цифру числа, то есть отсекать поразрядно значения, с помощью операции взятия остатка от деления на 10 (x % 10)и добавлять ее в конец результирующего числа, умножая его на 10. После каждой итерации исходное число currentValue целочисленно делится на 10 (x//10), чтобы отбросить уже обработанную последнюю цифру.
Улучшение:
def isPalindrome(x: int) -> bool:
if x < 0 or (x > 0 and x % 10 == 0):
return False
currentValue= x
newValue= 0
while x>0:
newValue= newValue* 10 + x%10
x = x//10
return newValue == currentValue
Добавим в начале проверку, что число не заканчивается на 0, ибо это исключает палиндром.
Временная сложность: цикл дает нам сложность O(n)
Пространственная сложность: используем две переменные O(1) + O(1) дополнительной памяти, поэтому O(1).
