Count a Character
Otrzymujesz ciąg znaków s i pojedynczą literę c. Zwróć liczbę wystąpień c w ciągu s. Rozróżniana jest wielkość liter: B i b to różne znaki, więc liczą się tylko dokładne wystąpienia c.
Funkcja
- sstring
- ciąg angielskich liter do wyszukania
- cstring
- jedną literę do policzenia
- Zwracainteger
- ile znaków w ciągu s jest równych c
Ograniczenia
1 ≤ s.length ≤ 5 × 104szawiera tylko angielskie litery (adoz,AdoZ).cto dokładnie jedna angielska litera.
Przykłady
- Wejście
- s = "Mississippi"c = "s"
- Wyjście
- 4
- Wyjaśnienie
Mississippima literęsna pozycjach 2, 3, 5 i 6, licząc od 0, więc odpowiedź to 4.
- Wejście
- s = "Banana"c = "b"
- Wyjście
- 0
- Wyjaśnienie
Bananazaczyna się wielką literąB, a wyszukiwana jest mała literab. Te litery się różnią, więc nic nie pasuje, a odpowiedź to 0.
+18 ukrytych testów przy wysłaniu
Pytanie dodatkowe
A co, jeśli c mogłoby być słowem składającym się z kilku liter, takim jak ss? Czy nakładające się dopasowania się liczą i jak zmienia się Twoja pętla?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Aby dowiedzieć się, ile razy pojawia się
c, na które znaki wsmusisz spojrzeć?Porównaj każdy znak w
szcdokładnie tak, jak występują. Wielkie i małe litery są tutaj różnymi znakami.Prowadź licznik zaczynający się od 0. Przejdź przez ciąg znaków jeden raz i dodaj 1 za każdym razem, gdy bieżący znak jest równy
c.
Rozwiązanie
Każdy znak w s trzeba sprawdzić raz, ponieważ każdy z nich może być c. Praca polega na jednokrotnym przejściu z użyciem licznika. Szczegóły, które sprawiają trudność, to wielkość liter (wielka litera jest innym znakiem) oraz porównywanie znaku z ciągiem znaków zawierającym jedną literę, co ma miejsce w niektórych językach.
Usuń każde c i porównaj długości
Intuicja
Utwórz kopię s, usuwając z niej każde c. Każdy usunięty znak skraca kopię o jeden znak, więc różnica między długościami obu ciągów jest dokładnie równa liczbie wystąpień c. Większość języków ma funkcję replace lub delete, która wykonuje usuwanie za Ciebie.
Dla Mississippi i s kopią jest Miiippi. Ma ona 7 znaków, a oryginał 11, więc c wystąpiło 4 razy. W przypadku Banana i b nic nie zostaje usunięte, ponieważ wielka litera B nie jest dopasowaniem, a różnica wynosi 0.
Wykonywane jest jedno przejście po s, więc czas wynosi O(n). Kosztem jest pamięć: kopia może być tak długa jak s, co oznacza dodatkowe O(n) miejsca, którego licznik nie potrzebuje.
Algorytm
- Utwórz kopię
s, pomijając każdy znak równyc. - Zmierz długość
soraz długość kopii. - Zwróć długość
spomniejszoną 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
Pomiń kopiowanie i licz w trakcie czytania. Przechodź przez s od lewej do prawej, używając licznika zaczynającego od 0, i dodawaj 1 za każdym razem, gdy bieżący znak jest równy c. Dopasowanie jest ustalane na podstawie zwykłej równości, więc wielka litera nigdy nie pasuje do małej.
Dla Mississippi licznik zwiększa się na indeksach 2, 3, 5 i 6, a na końcu wynosi 4. Każdy znak jest porównywany raz i nic więcej nie jest przechowywane.
Daje to złożoność czasową O(n) i dodatkową przestrzeń O(1): jeden licznik i docelową literę. Nie da się uzyskać lepszej złożoności czasowej, ponieważ pominięty znak mógłby być kolejnym c.
Algorytm
- Odczytaj docelową literę z
ci ustawcount = 0. - Przejdź przez
s, znak po znaku. - Jeśli znak jest równy docelowemu, dodaj 1 do
count. - Zwróć
count.
def countChar(s, c):
count = 0
for ch in s:
if ch == c:
count += 1
return count
Pułapki i przypadki brzegowe
Pętla jest krótka, a błędy kryją się w sposobie porównywania obu wartości.
- Ignorowanie wielkości liter. Zamiana obu stron na małe litery sprawia, że
Bananaw połączeniu zbzwraca 1, ale zadanie wymaga dokładnych dopasowań, więc odpowiedź wynosi 0. - Porównywanie znaku z ciągiem znaków. W Javie, C, C++, C# i Go
cjest ciągiem znaków, podczas gdys.charAt(i)lubs[i]to pojedynczy znak. Pobierzc[0](lubc.charAt(0)) raz przed pętlą. - Porównywanie ciągów znaków za pomocą
==w Javie.String.valueOf(s.charAt(i)) == cporównuje tożsamość obiektów i prawie zawsze zwraca false. Porównuj wartościcharlub użyjequals. - Wywoływanie
strlen(s)w warunku pętli w C. Funkcja przechodzi przez cały ciąg znaków przy każdym kroku, więc5 × 10^4znaków wymaga około2.5 × 10^9kroków. Zamiast tego zatrzymaj się na terminatorze'\0'.
Najczęstsze pytania4
Jak policzyć wystąpienia znaku w ciągu znaków?
Ustaw licznik na 0 i przejdź przez ciąg znaków jeden raz. Za każdym razem, gdy bieżący znak jest równy temu, którego szukasz, dodaj 1. Gdy pętla się zakończy, wartością licznika jest odpowiedź, a wykonanie zajmuje O(n) czasu i wymaga O(1) dodatkowej pamięci.
Czy rozróżniana jest wielkość liter podczas liczenia znaków?
W tym zadaniu tak: B i b to różne znaki, więc Banana nie zawiera żadnego b. Jeśli zamiast tego potrzebujesz zliczania bez rozróżniania wielkości liter, przed porównaniem zamień zarówno ciąg znaków, jak i literę na małe litery.
Czy mogę użyć wbudowanej funkcji zliczającej podczas rozmowy kwalifikacyjnej?
Zazwyczaj tak, o ile potrafisz określić koszt. str.count w Pythonie i podobne funkcje nadal odczytują cały ciąg znaków, więc mają złożoność O(n). Wielu rekruterów prosi następnie o samodzielne napisanie pętli, więc przygotuj się, by ją pokazać.
Jak policzyć wszystkie znaki jednocześnie?
Przejdź przez tekst jeden raz i zliczaj wystąpienia każdego znaku w mapie haszującej lub w tablicy 52 liczników dla liter angielskich. Po takim przejściu liczba wystąpień dowolnej litery wymaga tylko jednego wyszukania. To lepsze rozwiązanie, gdy masz odpowiedzieć na pytania o wiele liter w tym samym ciągu znaków.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def countChar(s, c):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Wejście
s = "Mississippi" c = "s"
Oczekiwane
4