Jak sprawdzić numer palindromu w Pythonie?

Co to jest palindrom?

Palindrom to słowo, liczba lub dowolny ciąg znaków, który czyta się do tyłu tak samo, jak do przodu.

Kilka przykładów: detarted, 1567651, 02/02/2020, malajalam

Ten artykuł pokazuje więc różne sposoby napisania programu, który sprawdza, czy dane wejście jest palindromem, czy nie, za pomocą Pythona.

Metoda 1:

Najbardziej naiwnym rozwiązaniem, jakie przychodzi mi do głowy, jest odwrócenie liczby i sprawdzenie, czy jest ona równa liczbie wejściowej. Można to zrobić w następujący sposób:

liczba = int(wejście());

rewers = 0

podczas gdy liczba > 0:

cyfra = liczba % 10

rewers = rewers * 10 + cyfra

liczba = liczba // 10

jeśli liczba==rewers:

print(„to jest palindrom!”)

w przeciwnym razie:

print(„to nie jest palindrom!”)

Jednak pogarsza to czytelność kodu i ma więcej wierszy kodu niż jest to wymagane. Sprawdź nasz internetowy kurs nauki o danych, aby dowiedzieć się więcej.

Oto krótki i przyjemny sposób na sprawdzenie liczby za pomocą tylko jednej linii.

Metoda 2:

Sztuczka polega na tym, aby liczbę wejściową przyjąć jako typ danych str zamiast int. Następnie możesz użyć techniki krojenia [::-1], aby uzyskać odwrotność ciągu i sprawdzić równość w samej instrukcji if .

liczba = wejście()

if liczba == liczba[::-1]:

print(„to jest palindrom!”)

w przeciwnym razie:

print(„to nie jest palindrom!”)

Metoda 3:

Jest to rekurencyjna metoda sprawdzania, czy tablica jest palindromem, czy nie.

def isPalindrome(liczby, początek, koniec):

jeśli początek >= koniec:

zwróć Prawda

if liczby[początek] == liczby[koniec]:

return isPalindrome(liczby, początek + 1, koniec – 1)

w przeciwnym razie:

powrót Fałsz

liczby= lista(map(int, input().split()))

n=len(liczby)

jeśli jest Palindrom(liczby, 0, n-1):

print(„to jest palindrom!”)

w przeciwnym razie:

print(„to nie jest palindrom!”)

Funkcja isPalindrome sprawdza, czy pierwszy i ostatni element tablicy są takie same, czy nie. Jeśli nie, funkcja natychmiast zwraca wartość False. W przeciwnym razie rekursywnie sprawdza kolejne skrajne elementy, aż dwie wskazówki spotkają się pośrodku.

Przeczytaj: Pomysły i tematy dotyczące projektów w Pythonie

Typowe pytania podczas wywiadu dotyczącego kodowania związane z palindromami

#1 Najdłuższy podciąg palindromiczny

Biorąc pod uwagę tylko jeden ciąg jako dane wejściowe, musisz zwrócić długość najdłuższego podciągu palindromicznego w ciągu.

Np:

Wejście: 'acbcbabcc'

Wyjście: 5 („cbabc”)

Zbliżać się:

Jeśli spróbujemy odnieść to do jednego z najczęstszych problemów DP, najdłuższego wspólnego podciągu, tutaj różnica polega na tym, że otrzymujemy tylko jeden ciąg wejściowy, podczas gdy LCS używa dwóch ciągów. Ponieważ wiemy, że palindrom jest dokładnie taki sam, jak jego odwrotność, możemy uczynić drugi ciąg jako odwrotność danych wejściowych.

Teraz staje się to dokładnie tym samym, co znalezienie LCS.

def LCSubstr(A, B, m, n):

LCSub = [[0 dla i w zakresie(n+1)] dla j w zakresie(m+1)]

odp = 0

dla i w zakresie (m+1):

dla j w zakresie (n+1):

jeśli (i == 0 lub j == 0):

LCSub[i][j] = 0

elif A[i-1] == B[j-1]:

LCSub[i][j] = 1 + LCSub[i-1][j-1]

ans = max(ans, LCSub[i][j])

w przeciwnym razie:

LCSub[i][j] = 0

powrót i

str1 = wejście ()

słowo2 = słowo1[::-1]

m = len(str1)

n = dł(str2)

print('Długość najdłuższego podciągu palindromicznego = ', LCSubstring(str1, str2, m, n))

Tak więc dla powyższych danych wejściowych otrzymujemy dwa ciągi jako

„acbcbabcc” i

'ccbabcbc'

Najdłuższym wspólnym podciągiem jest „cbabc”, który ma długość 5.

#2 Sprawdź, czy anagram ciągu jest palindromem

Mając ciąg jako dane wejściowe, musisz sprawdzić, czy dowolny anagram ciągu może być palindromem, czy nie, i odpowiednio zwrócić odpowiedź tak/nie.

Np:

Wejście: „pythonpython”

Wyjście: Tak

(podczas gdy sam ciąg nie jest palindromem, możliwy anagram „pythonnohtyp” tworzy palindrom)

Wejście: „harrypotter”

Wyjście: Nie

Zbliżać się:

Jeśli zauważysz uważnie, za każdym razem, gdy mamy ciąg palindromu o równej długości, wszystkie znaki z pierwszej połowy powtarzają się w drugiej połowie. Oznacza to, że wszystkie znaki występujące w ciągu występują parzystą liczbę razy.

Gdy długość jest nieparzysta, wszystkie znaki na lewo od środkowego elementu (nie włącznie) występują taką samą liczbę razy po prawej stronie środkowego elementu. Oznacza to, że tylko jeden znak występuje nieparzystą liczbę razy (element środkowy), a wszystkie pozostałe występują parzystą liczbę razy.

Korzystając z tej logiki, możemy przechowywać liczbę znaków w ciągu w postaci skrótu i ​​sprawdzić te ograniczenia, aby uzyskać wymaganą odpowiedź.

ZAKRES_ZNAKÓW = 256

str1 = wejście ()

freq = [0 dla i w zakresie(CHAR_RANGE)]

dla mnie w str1:

freq[ord(i)] += 1 #ord(x) daje wartość unikodu x

liczba_kursów = 0

dla i w zakresie (CHAR_RANGE):

jeśli częst[i] i 1:

liczba_kursów += 1

jeśli (liczba_kursów > 1):

drukuj("Tak")

w przeciwnym razie:

drukuj("Nie")

Wniosek

Podsumowując, problemy palindromu są bardzo częste i interesujące. Przydają się do rozwiązywania różnych zagadek matematycznych i pytań związanych z programowaniem konkurencyjnym.

Jeśli jesteś zainteresowany nauką o danych, sprawdź program IIIT-B i upGrad Executive PG w dziedzinie Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży, 1 -on-1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.