Palindrome Number

Q: Czy liczba ujemna jest palindromem?

Nie. Czytane od tyłu -121 zmienia się w 121- , a znak minus nie ma pasującego znaku na drugim końcu. Dlatego każda liczba całkowita ujemna zwraca false .

Q: Jaka jest złożoność czasowa problemu liczby palindromicznej?

Oba podejścia działają w czasie O(log x) , ponieważ liczba x ma około log10(x) cyfr, a każda z nich jest przetwarzana raz. Podejście z użyciem ciągu znaków wymaga dodatkowej pamięci O(log x) na tekst; odwrócenie połowy wymaga O(1) .

ŁatweMatematyka i symulacja

+10

Liczba jest palindromem, gdy jej cyfry czytane od lewej do prawej i od prawej do lewej są takie same, na przykład 1221. Dla danej liczby całkowitej x zwróć true, jeśli jest palindromem, a w przeciwnym razie false. Liczby ujemne nigdy się nie liczą, ponieważ ich znak minus nie ma odpowiednika na drugim końcu.

Funkcja

isPalindrome(x: integer) → boolean

xinteger: liczba całkowita do sprawdzenia, być może ujemna
Zwracaboolean: prawda, jeśli x czyta się tak samo w obu kierunkach, w przeciwnym razie fałsz

Ograniczenia

-2³¹ ≤ x ≤ 2³¹-1
Każda liczba ujemna zwraca false.

Przykłady

Wejście: x = 121
Wyjście: true
Wyjaśnienie: Czytana od tyłu liczba 121 nadal wynosi 121, więc odpowiedzią jest true.

Wejście: x = -121
Wyjście: false
Wyjaśnienie: Czytane od tyłu, -121 staje się 121-, czyli innym tekstem, więc odpowiedź to false.

Pytanie dodatkowe

Czy potrafisz rozwiązać to bez konwertowania liczby całkowitej na ciąg znaków?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Liczba jest palindromem, gdy jest równa swojej odwrotności. W przypadku tekstu wystarczy jedno porównanie. Bez zamiany na tekst odtworzenie całej odwróconej liczby może spowodować przepełnienie, dlatego odwróć tylko drugą połowę cyfr i porównaj ją z pierwszą połową.

Porównaj ciąg znaków z jego odwróceniem

Intuicja

Zapisz liczbę jako tekst i porównaj ją z jej odwróceniem. Liczby ujemne nie wymagają specjalnego przypadku: -121 zaczyna się od znaku minus i kończy cyfrą, więc nigdy nie jest równa swojemu odwróceniu 121-.

Tekst ma jeden znak na każdą cyfrę, czyli około log10(x) znaków, a tutaj najwyżej 11. Kosztem jest dodatkowy ciąg znaków.

Algorytm

Przekształć x w ciąg znaków s.
Odwróć s.
Zwróć informację, czy s jest równe jego odwróconej wersji.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

Odwróć połowę liczby

Intuicja

x % 10 zwraca ostatnią cyfrę, a dzielenie całkowite przez 10 ją usuwa. Przenoszenie cyfr z końca liczby x do drugiej liczby half tworzy odwrócony zapis usuniętych cyfr. Zatrzymaj się, gdy half będzie co najmniej równe temu, co pozostało z x: masz już połowę cyfr. Liczba 1221 kończy z wartościami x = 12 i half = 12, więc jest palindromem. Przy nieparzystej liczbie cyfr half zawiera też środkową cyfrę: 12321 kończy z wartościami x = 12 i half = 123, więc porównujesz x z half / 10.

Przed pętlą rozpatrz dwa przypadki. Liczba ujemna nigdy nie jest palindromem. Liczba kończąca się na 0 musiałaby zaczynać się od 0, a tak jest tylko w przypadku 0; bez tego sprawdzenia liczba 10 kończy z wartościami x = 0 i half = 1, a warunek x == half / 10 zostaje błędnie spełniony. half nigdy nie przekracza 6 cyfr, więc mieści się w dowolnym typie całkowitoliczbowym.

Algorytm

Jeśli x jest ujemne lub kończy się na 0 i nie jest równe 0, zwróć false.
Ustaw half = 0.
Dopóki x > half, ustaw half = half * 10 + x % 10 i podziel x przez 10, używając dzielenia całkowitego.
Zwróć true, jeśli x == half (parzysta liczba cyfr) lub x == half / 10 (nieparzysta liczba cyfr).

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

Pułapki i przypadki brzegowe

Zapominanie o liczbach ujemnych. W językach, w których reszta zachowuje znak, odwrócenie -121 daje -121 i test przechodzi. W Pythonie, gdzie -1 // 10 wynosi -1, pętla while x != 0 nigdy się nie kończy.
Nieodrzucanie liczb kończących się na 0. Częściowe odwrócenie akceptuje wtedy 10. Samo 0 jest palindromem.
Odwracanie całej liczby w 32-bitowej liczbie całkowitej. Odwrócenie 2147483647 się nie mieści.
Używanie / w języku, w którym dzielenie daje ułamek. Użyj Math.floor(x / 10) w JavaScript, // w Pythonie, %/% w R i ~/ w Dart.
Porównywanie pełnego odwrócenia z x po tym, jak pętla zmieniła x. Zachowaj kopię oryginału.

Najczęstsze pytania3

Czy liczba ujemna jest palindromem?

Nie. Czytane od tyłu -121 zmienia się w 121-, a znak minus nie ma pasującego znaku na drugim końcu. Dlatego każda liczba całkowita ujemna zwraca false.

Dlaczego odwracać tylko połowę liczby?

Odwrócenie wszystkich cyfr może spowodować przepełnienie 32-bitowej liczby całkowitej: liczba powstała przez odwrócenie 2147483647 jest większa niż największa wartość typu int. Połowa cyfr zawsze się mieści, a pętla wykonuje połowę pracy.

Jaka jest złożoność czasowa problemu liczby palindromicznej?

Oba podejścia działają w czasie O(log x), ponieważ liczba x ma około log10(x) cyfr, a każda z nich jest przetwarzana raz. Podejście z użyciem ciągu znaków wymaga dodatkowej pamięci O(log x) na tekst; odwrócenie połowy wymaga O(1).

def isPalindrome(x):
    # Napisz kod tutaj

Test #1

Test #2

Argument

x = 121

Oczekiwany wynik

true