Count a Character

+10

Otrzymujesz ciąg znaków s i pojedynczą literę c. Zwróć, ile razy c występuje w s. Rozróżniana jest wielkość liter: B i b to różne znaki.

Funkcja

countChar(s: string, c: string) → integer

sstring: ciąg angielskich liter do wyszukania
cstring: jedna litera do policzenia
Zwracainteger: ile znaków w s jest równych c

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
s zawiera tylko angielskie litery (a do z, A do Z).
c to dokładnie jedna angielska litera.

Przykłady

Wejście: s = "Mississippi"c = "s"
Wyjście: 4
Wyjaśnienie: Mississippi ma s na indeksach 2, 3, 5 i 6, więc odpowiedź to 4.

Wejście: s = "Banana"c = "b"
Wyjście: 0
Wyjaśnienie: Banana zaczyna się od wielkiej litery B, a szukasz małej litery b. Nic nie pasuje, więc odpowiedź to 0.

Pytanie dodatkowe

A co, jeśli c mogłoby być słowem złożonym z kilku liter, takim jak ss? Czy nakładające się dopasowania się liczą i jak zmieni się twoja pętla?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każdy znak w s może być c, więc sprawdzasz każdy znak raz i liczysz dopasowania. Zwróć uwagę na wielkość liter: wielka litera to inny znak.

Usuń każde c i porównaj długości

Intuicja

Utwórz kopię s, z której usunięto każde c. Każde usunięcie skraca kopię o jeden znak, więc różnica długości to liczba usuniętych znaków. Dla Mississippi kopia to Miiippi: 11 minus 7 to 4.

Czas działania wynosi O(n), ale kopia zajmuje dodatkową pamięć O(n), której licznik nie potrzebuje.

Algorytm

Utwórz kopię s, pomijając każdy znak równy c.
Zmierz długość s oraz długość kopii.
Zwróć długość s pomniejszoną o długość kopii.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

Jedno przejście z licznikiem

Intuicja

Licz podczas odczytywania zamiast tworzyć kopię. Licznik zaczyna od 0 i zwiększa się o 1 dla każdego znaku równego c. Zwykłe porównanie równości sprawia, że wielka litera nie pasuje do małej.

Każdy znak jest porównywany raz i przechowywany jest tylko licznik: czas O(n), pamięć O(1). Żadne rozwiązanie nie osiąga lepszego czasu niż O(n), ponieważ pominięty znak mógłby być kolejnym c.

Algorytm

Odczytaj docelową literę z c i ustaw count = 0.
Przejdź przez s, znak po znaku.
Jeśli znak jest równy docelowemu, zwiększ count o 1.
Zwróć count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

Pułapki i przypadki brzegowe

Ignorowanie wielkości liter. Zamiana obu stron na małe litery sprawia, że Banana i b zwracają 1; odpowiedź to 0.
Porównywanie znaku z ciągiem znaków. W Java, C, C++, C# i Go c jest ciągiem znaków, natomiast s[i] lub s.charAt(i) to jeden znak. Pobierz c[0] (lub c.charAt(0)) raz przed pętlą.
Porównywanie ciągów znaków za pomocą == w Java. String.valueOf(s.charAt(i)) == c porównuje tożsamość obiektów i prawie zawsze zwraca false. Porównuj wartości typu char.
Wywoływanie strlen(s) w warunku pętli w C. Przy każdym kroku ponownie skanuje ciąg znaków, więc 5 × 10^4 znaków wymaga około 2.5 × 10^9 kroków.

Najczęstsze pytania3

Jak policzyć wystąpienia znaku w ciągu znaków?

Przejdź przez ciąg znaków jeden raz, używając licznika zaczynającego się od 0, i dodaj 1 za każdym razem, gdy bieżący znak jest równy temu, którego szukasz. Zajmuje to czas O(n) i wymaga O(1) dodatkowej pamięci. Aby zliczać bez rozróżniania wielkości liter, najpierw zamień cały ciąg znaków i literę na małe litery.

Czy mogę użyć wbudowanej funkcji zliczającej podczas rozmowy kwalifikacyjnej?

Zazwyczaj tak, o ile potrafisz powiedzieć, jaki jest koszt. Funkcja str.count w Pythonie i podobne funkcje nadal odczytują cały ciąg znaków, więc mają złożoność O(n). Przygotuj się na napisanie pętli, jeśli osoba prowadząca rozmowę o to poprosi.

Jak policzyć wszystkie znaki naraz?

Przejdź przez ciąg jeden raz i zlicz wystąpienia każdego znaku w mapie haszującej lub tablicy z 52 licznikami dla liter alfabetu angielskiego. Po takim przejściu sprawdzenie liczby wystąpień dowolnej litery wymaga tylko jednego odczytu. Użyj tego rozwiązania, gdy pytanie dotyczy wielu liter w tym samym ciągu.

def countChar(s, c):
    # Napisz kod tutaj

Test #1

Test #2

Argumenty

s = "Mississippi"
c = "s"

Oczekiwany wynik