Алгоритмы - Структуры - LeetCode 9. Palindrome Number

Один из десятка тысяч разборов этой задачи, в большей степени перевод 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).