Reverse the Digits

Q: Jak odwrócić cyfry liczby bez konwertowania jej na ciąg znaków?

Powtarzaj dwa kroki, aż liczba będzie równa 0 : pobierz ostatnią cyfrę za pomocą n % 10 i dołącz ją do wyniku za pomocą result = result * 10 + digit , a następnie usuń ją za pomocą n = n / 10 , stosując dzielenie całkowite. Dla 1234 wynik rośnie kolejno do 4, 43, 432 i 4321.

PoczątkującyMatematyka i symulacja

+10

Otrzymujesz nieujemną liczbę całkowitą n. Zwróć liczbę utworzoną przez zapisanie jej cyfr dziesiętnych w odwrotnej kolejności. Zera, które znajdą się na początku, są pomijane, więc 120 zmienia się w 21.

Funkcja

reverseDigits(n: integer) → integer

ninteger: nieujemna liczba całkowita do odwrócenia
Zwracainteger: cyfry liczby n w odwrotnej kolejności, jako liczba

Ograniczenia

0 ≤ n < 10⁹
Odwrócona liczba również mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: n = 1234
Wyjście: 4321
Wyjaśnienie: Cyfry liczby 1234 to 1, 2, 3 i 4. Czytane od końca to 4, 3, 2 i 1, czyli 4321.

Wejście: n = 120
Wyjście: 21
Wyjaśnienie: Odczytane od tyłu 120 daje cyfry 0, 2 i 1. Zero na początku nie liczy się w liczbie, więc odpowiedzią jest 21.

Wejście: n = 0
Wyjście: 0
Wyjaśnienie: 0 ma jedną cyfrę, a odwrócenie go daje ponownie 0.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jeśli n może być dowolną 32-bitową liczbą całkowitą, jej odwrócenie może się nie zmieścić. Jak wykryć to przed przepełnieniem podczas mnożenia?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Odwrócenie zapisu dziesiętnego to jedna linijka w większości języków i całkiem dobra pierwsza odpowiedź. Osoby przeprowadzające rozmowę kwalifikacyjną zwykle dopytują, jak uzyskać ten sam wynik bez użycia ciągów znaków. Wersja arytmetyczna opiera się na dwóch operacjach: n % 10 odczytuje ostatnią cyfrę, a n / 10 (dzielenie całkowite) usuwa ją.

Odwróć tekst dziesiętny

Intuicja

Cyfry liczby to dokładnie znaki jej zapisu dziesiętnego. Zamień n na tekst, odwróć znaki i odczytaj tekst z powrotem jako liczbę. 1234 staje się "1234", potem "4321", a następnie 4321.

Zera wiodące znikną same. Odwrócenie 120 daje tekst "021", a parsowanie go jako liczby pomija zero z przodu i zwraca 21.

Liczba mniejsza niż 10^9 ma co najwyżej 9 cyfr, a nakład pracy i dodatkowy tekst rosną wraz z liczbą cyfr, czyli O(log n).

Algorytm

Przekonwertuj n na zapis dziesiętny.
Odwróć znaki.
Przekształć odwrócony tekst na liczbę całkowitą i ją zwróć.

def reverseDigits(n):
    # int() ignores the leading zeros that trailing zeros turn into.
    return int(str(n)[::-1])

Dodawaj i usuwaj cyfry za pomocą działań arytmetycznych

Intuicja

Zdejmuj cyfry z końca n po jednej i dodawaj każdą z nich na końcu nowej liczby. n % 10 to ostatnia cyfra n, a n / 10 przy dzieleniu całkowitoliczbowym ją usuwa. Aby dodać cyfrę d na końcu result, przesuń obecną wartość o jedno miejsce w lewo i umieść d na miejscu jedności: result * 10 + d.

Dla 1234 wartość result przyjmuje kolejno 4, 43, 432, 4321, podczas gdy n przyjmuje wartości 123, 12, 1, 0. Pętla kończy działanie, gdy n osiągnie 0, więc wykonuje się raz na każdą cyfrę.

Zera wiodące nigdy się nie pojawiają. Dla 120 pierwszą pobraną cyfrą jest 0, a 0 * 10 + 0 nadal wynosi 0, więc nie pozostawia po sobie śladu. Dla n = 0 pętla w ogóle się nie wykonuje, a wynikiem jest 0. Przechowywane są tylko dwie liczby całkowite, więc dodatkowa przestrzeń wynosi O(1).

Algorytm

Ustaw result = 0.
Gdy n jest większe od 0, oblicz ostatnią cyfrę n % 10.
Ustaw result = result * 10 + digit.
Usuń cyfrę za pomocą n = n / 10, stosując dzielenie całkowite.
Zwróć result.

def reverseDigits(n):
    result = 0
    while n > 0:
        result = result * 10 + n % 10  # push the last digit of n
        n //= 10                        # drop it from n
    return result

Pułapki i przypadki brzegowe

Większość błędów wynika z dzielenia i warunku kończącego pętlę.

Używanie zwykłego dzielenia tam, gdzie potrzebne jest dzielenie całkowite. W JavaScript, Pythonie 3 i Lua n / 10 daje 123.4, więc n nigdy z powrotem nie staje się liczbą całkowitą, a result zapełnia się ułamkami. Użyj Math.floor, // albo dzielenia całkowitego dostępnego w danym języku.
Zapisanie pętli jako while n >= 10. Kończy się przed przetworzeniem ostatniej cyfry, więc 1234 daje w wyniku 432.
Zwracanie odwróconego tekstu bez parsowania go. "021" nie jest liczbą 21, więc porównanie z oczekiwaną odpowiedzią nie powiedzie się.
Formatowanie wartości typu double w R za pomocą as.character. Gdy n jest przechowywane jako double, wyświetla 100000000 jako 1e+08, a odwrócony tekst to 80+e1. Użyj format(n, scientific = FALSE).

Najczęstsze pytania4

Jak odwrócić cyfry liczby bez konwertowania jej na ciąg znaków?

Powtarzaj dwa kroki, aż liczba będzie równa 0: pobierz ostatnią cyfrę za pomocą n % 10 i dołącz ją do wyniku za pomocą result = result * 10 + digit, a następnie usuń ją za pomocą n = n / 10, stosując dzielenie całkowite. Dla 1234 wynik rośnie kolejno do 4, 43, 432 i 4321.

Co dzieje się z końcowymi zerami, gdy odwracasz liczbę?

Stałyby się zerami wiodącymi, których liczba nie ma, więc znikają. Odwrócenie 120 daje 21, a odwrócenie 100000000 daje 1. Pętla arytmetyczna pomija je sama, ponieważ dodanie 0 do pustego wyniku pozostawia go równym 0.

C jaka jest złożoność czasowa odwracania liczby całkowitej?

Pętla wykonuje się raz dla każdej cyfry dziesiętnej, a liczba n ma około log10(n) + 1 cyfr, więc czas wynosi O(log n). Wersja arytmetyczna wykorzystuje dodatkową pamięć O(1); wersja tekstowa przechowuje cyfry jako tekst, co wymaga O(log n) pamięci.

Czy odwrócenie liczby całkowitej może spowodować przepełnienie?

Tak, gdy dane wejściowe mogą być dowolną 32-bitową liczbą całkowitą. 1000000009 mieści się w zakresie, ale jej odwrócona postać 9000000001 już nie. Tutaj n jest mniejsze niż 10^9, więc odwrócona liczba ma co najwyżej 9 cyfr i zawsze mieści się w zakresie. Przy większych danych wejściowych przed każdym mnożeniem sprawdzaj result > (INT_MAX - digit) / 10.

Python

def reverseDigits(n):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

n = 1234

Oczekiwane