To Lower Case

Q: Jak zamienić ciąg znaków na małe litery bez użycia wbudowanej funkcji?

Przejdź pętlą po znakach i sprawdź kod każdego z nich. Jeśli kod mieści się w przedziale od 65 ( A ) do 90 ( Z ), dodaj 32, aby uzyskać małą literę; pozostałe znaki pozostaw bez zmian. Połącz znaki z powrotem w ciąg znaków.

Q: Dlaczego różnica między wielkimi a małymi literami wynosi 32?

ASCII umieszcza wielkie litery pod kodami od 65 do 90, a małe litery od 97 do 122, z sześcioma symbolami pomiędzy nimi. Oba alfabety są w tej samej kolejności, więc każdą parę dzieli 97 - 65 = 32 . 32 to pojedynczy bit, więc ustawienie tego bitu zamienia wielką literę na jej małą literę.

Q: Czy potrafisz zmienić wielkość liter za pomocą operacji bitowej?

Tak. W przypadku wielkiej litery code | 32 ustawia bit, który rozróżnia te dwa przypadki, i daje małą literę, a code & ~32 ponownie go zeruje. Nadal najpierw musisz sprawdzić zakres, ponieważ ta sama sztuczka bitowa zmieniłaby również cyfry i symbole.

PoczątkującyTablice i napisy

+10

Otrzymujesz ciąg znaków s. Zwróć nowy ciąg znaków, w którym każda wielka angielska litera, od A do Z, jest zastąpiona odpowiadającą jej małą literą. Każdy inny znak, taki jak mała litera, cyfra lub symbol, pozostaje dokładnie taki sam.

Funkcja

toLowerCase(s: string) → string

sstring: tekst do przetłumaczenia
Zwracastring: s z każdą wielką literą zamienioną na małą

Ograniczenia

1 ≤ s.length ≤ 10⁴
Każdy znak w s jest angielską literą, cyfrą lub jednym z symboli !#$%&()*+-./:;<=>?@[]^_`{|}~.

Przykłady

Wejście: s = "Hello-World!"
Wyjście: "hello-world!"
Wyjaśnienie: Wielkie litery H i W stają się małymi literami h i w. - i ! nie są literami, więc pozostają na swoim miejscu.

Wejście: s = "coddy_2026"
Wyjście: "coddy_2026"
Wyjaśnienie: Nie ma wielkiej litery do zmiany. Małe litery, znak _ i cyfry pozostają bez zmian.

Pytanie dodatkowe

Czy potrafisz napisać toUpperCase z użyciem tej samej pętli i wyjaśnić, dlaczego między A a a różni się tylko jeden bit kodu znaku?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każdy język udostępnia funkcję zamiany na małe litery i w kodzie produkcyjnym należy z niej korzystać. Rekruterzy zadają to pytanie, aby sprawdzić, czy wiesz, jak działa ta funkcja: znak jest liczbą, a w ASCII każda wielka litera ma kod dokładnie o 32 mniejszy niż jej mały odpowiednik. Sprawdź, czy kod mieści się w przedziale od 'A' do 'Z', i jeśli tak, dodaj 32.

Wywołaj wbudowaną funkcję zamieniającą tekst na małe litery

Intuicja

Funkcje lower() w Pythonie, toLowerCase() w JavaScript, downcase w Ruby i ich odpowiedniki w każdym innym języku już wykonują to zadanie. C i C++ udostępniają tolower dla jednego znaku, więc wywołujesz tę funkcję w pętli. Każdy znak jest sprawdzany raz, więc złożoność czasowa wynosi O(n), a nowy ciąg znaków zajmuje O(n) pamięci.

Niektóre z tych funkcji uwzględniają ustawienia językowe komputera. W języku tureckim małą literą odpowiadającą I jest ı bez kropki, a nie i. Dlatego wersje w Javie i C# proszą o stałą regułę za pomocą Locale.ROOT i ToLowerInvariant, aby wynik nie zmieniał się w zależności od komputera.

W pracy to właściwa odpowiedź. Na rozmowie kwalifikacyjnej często nie zostaje zaakceptowana, ponieważ pomija jedyną ideę, której dotyczy pytanie.

Algorytm

Wywołaj funkcję zamiany na małe litery w swoim języku dla s albo wywołaj tolower dla każdego znaku w C i C++.
Jeśli funkcja oferuje taką możliwość, poproś o zastosowanie stałej reguły niezależnej od języka.
Zwróć wynik.

def toLowerCase(s):
    return s.lower()

Przesuń kody znaków wielkich liter

Intuicja

Każdy znak jest przechowywany jako liczba. W ASCII kody znaków od A do Z to liczby od 65 do 90, a od a do z — od 97 do 122. Oba ciągi są uporządkowane alfabetycznie, a ich początki dzieli 32, więc mała litera odpowiadająca dowolnej wielkiej literze ma kod większy o 32: H ma kod 72, a h — 104.

Przejdź więc przez ciąg znaków jeden raz. Jeśli kod mieści się w zakresie od 65 do 90, dodaj 32; w przeciwnym razie skopiuj znak bez zmian. Sprawdzenie zakresu ma znaczenie: symbole [, ^ i _ znajdują się między Z a a, a @ znajduje się tuż przed A. Sprawdzenie tylko code < 97 zmieniłoby _ w inny symbol.

Każdy znak jest sprawdzany raz, co daje czas O(n). Wynikiem jest nowy ciąg znaków o tej samej długości, co wymaga O(n) pamięci. Zapisanie 'a' - 'A' zamiast 32 oznacza to samo i wyjaśnia, skąd bierze się ta liczba.

Algorytm

Skopiuj s do tablicy znaków lub kodów.
Dla każdej pozycji odczytaj kod znaku.
Jeśli kod znajduje się między 'A' (65) a 'Z' (90), dodaj 32.
Przekształć tablicę z powrotem w ciąg znaków i zwróć go.

def toLowerCase(s):
    # Every capital letter sits 32 codes below its small letter: 'A' is 65, 'a' is 97.
    shift = ord("a") - ord("A")
    chars = []
    for ch in s:
        if "A" <= ch <= "Z":
            ch = chr(ord(ch) + shift)
        chars.append(ch)
    return "".join(chars)

Pułapki i przypadki brzegowe

Pętla jest krótka, więc błędy dotyczą sprawdzania zakresu i sposobu budowania wyniku.

Dodawanie 32 do każdego znaku, który nie jest małą literą. Zmieniłyby się również cyfry i symbole: 1 zmieniłoby się w Q.
Sprawdzanie tylko jednego końca zakresu. code < 'a' obejmuje również [, _ i @, a code >= 'A' obejmuje również każdą małą literę.
Używanie < zamiast <= na końcach zakresu, przez co A lub Z pozostaje wielką literą.
Budowanie wyniku za pomocą result = result + ch w przypadku niezmiennego ciągu znaków. Każdy krok kopiuje dotychczasową zawartość, co daje złożoność kwadratową dla n = 10^4.
W C zapisywanie do danych wejściowych lub pominięcie kończącego '\0'. Przydziel n + 1 bajtów na kopię.

Najczęstsze pytania3

Jak zamienić ciąg znaków na małe litery bez użycia wbudowanej funkcji?

Przejdź pętlą po znakach i sprawdź kod każdego z nich. Jeśli kod mieści się w przedziale od 65 (A) do 90 (Z), dodaj 32, aby uzyskać małą literę; pozostałe znaki pozostaw bez zmian. Połącz znaki z powrotem w ciąg znaków.

Dlaczego różnica między wielkimi a małymi literami wynosi 32?

ASCII umieszcza wielkie litery pod kodami od 65 do 90, a małe litery od 97 do 122, z sześcioma symbolami pomiędzy nimi. Oba alfabety są w tej samej kolejności, więc każdą parę dzieli 97 - 65 = 32. 32 to pojedynczy bit, więc ustawienie tego bitu zamienia wielką literę na jej małą literę.

Czy potrafisz zmienić wielkość liter za pomocą operacji bitowej?

Tak. W przypadku wielkiej litery code | 32 ustawia bit, który rozróżnia te dwa przypadki, i daje małą literę, a code & ~32 ponownie go zeruje. Nadal najpierw musisz sprawdzić zakres, ponieważ ta sama sztuczka bitowa zmieniłaby również cyfry i symbole.

def toLowerCase(s):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

s = "Hello-World!"

Oczekiwany wynik

"hello-world!"