Count Even Numbers
Otrzymujesz niepustą listę liczb całkowitych nums. Zwróć liczbę jej wartości parzystych. Liczba jest parzysta, gdy podzielenie jej przez 2 nie daje reszty, co obejmuje 0 i liczby ujemne, takie jak -4.
Funkcja
- numsinteger-array
- lista liczb całkowitych do sprawdzenia
- Zwracainteger
- liczba parzystych wartości w nums
Ograniczenia
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Przykłady
- Wejście
- nums = [3, 8, 12, 5, 6]
- Wyjście
- 3
- Wyjaśnienie
8,12i6dzielą się przez2bez reszty, a3i5pozostawiają resztę. To oznacza, że są3parzyste wartości.
- Wejście
- nums = [-4, -3, 0, 7]
- Wyjście
- 2
- Wyjaśnienie
-4 = 2 × (-2)i0 = 2 × 0, więc obie liczby są parzyste.-3i7są nieparzyste, a ich liczba wynosi2.
- Wejście
- nums = [1, 9, 15]
- Wyjście
- 0
- Wyjaśnienie
1,9i15są nieparzyste, więc żadna wartość się nie liczy, a odpowiedzią jest0.
+12 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Dostajesz wiele pytań w rodzaju: ile parzystych wartości znajduje się między indeksem l a indeksem r? Czy po jednym przejściu przez nums możesz odpowiadać na każde pytanie w czasie O(1)?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Co pozostaje po podzieleniu liczby parzystej przez
2?Wartość
xjest parzysta dokładnie wtedy, gdyx % 2wynosi0. Uwaga: dla ujemnej liczby nieparzystej niektóre języki zwracają-1jako resztę, a nie1.Rozpocznij licznik od
0, odczytaj każdą wartość jeden raz i dodaj1, gdy reszta z dzielenia przez2wynosi0.
Rozwiązanie
Pętla zajmuje jedną linię; to test parzystości sprawia, że rozwiązania zawodzą. W wielu językach reszta z dzielenia liczby ujemnej jest ujemna, więc -3 % 2 to -1. Testowanie x % 2 == 0 jest poprawne dla każdej liczby ze znakiem w każdym języku, a licznik nie wymaga dodatkowej pamięci.
Zbierz wartości parzyste, a następnie je policz
Intuicja
Podziel zadanie na dwa kroki: wybierz wartości parzyste, a następnie policz, ile ich wybrano. Wartość x jest parzysta, gdy x % 2 == 0. Większość języków ma funkcję filter, która tworzy nową listę w jednej linijce, a jej długość jest odpowiedzią. Dla [3, 8, 12, 5, 6] przefiltrowana lista to [8, 12, 6], więc odpowiedzią jest 3.
To rozwiązanie jest poprawne i czytelne, ale nowa lista zużywa pamięć O(n), tutaj nawet dla 5000 wartości, tylko po to, by raz odczytać jej długość. Same wartości nie są już później używane.
Algorytm
- Utwórz nową listę zawierającą każde
xznums, dla któregox % 2 == 0. - Zwróć długość tej listy.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)Licz za pomocą stale aktualizowanego licznika
Intuicja
Zamiast listy użyj licznika. Ustaw jego początkową wartość na 0, sprawdź każdą wartość raz i dodaj 1, gdy wartość jest parzysta. Każda wartość jest sprawdzana dokładnie raz, więc wynik jest dokładny, a jedyną używaną pamięcią jest jedna liczba całkowita.
Test wymaga staranności. W C, C++, Java, C#, JavaScript, Go, Rust, Swift i PHP reszta z dzielenia ma znak liczby, więc -3 % 2 wynosi -1, a nie 1. Dla liczby parzystej reszta wynosi 0, niezależnie od jej znaku, więc x % 2 == 0 zawsze działa poprawnie, podczas gdy test nieparzystości zapisany jako x % 2 == 1 pomija każdą ujemną liczbę nieparzystą. Dla [-4, -3, 0, 7] reszty wynoszą 0, -1, 0 i 1, więc licznik kończy na 2.
Zero również się liczy: 0 % 2 wynosi 0, więc 0 jest parzyste.
Algorytm
- Ustaw
countna0. - Przejdź pętlą przez każdą wartość
xwnums. - Jeśli
x % 2 == 0, dodaj1docount. - Po pętli zwróć
count.
def countEvens(nums):
count = 0
for x in nums:
if x % 2 == 0: # 0 also works for negatives, where the remainder can be -1
count += 1
return count
Pułapki i przypadki brzegowe
Błędy wynikają tu z liczb ujemnych i z zera.
- Zliczanie wartości nieparzystych za pomocą
x % 2 == 1i odejmowanie ich liczby od długości. W językach podobnych do C-3 % 2wynosi-1, więc-3nigdy nie zostaje uznane za nieparzyste i ostatecznie jest liczone jako parzyste. - Traktowanie
0jako liczby ani parzystej, ani nieparzystej.0 = 2 × 0, więc jest parzyste, a[0]zwraca1. - Zapisanie testu bitowego jako
x & 1 == 0. W C, C++ i JavaScript operator==wiąże silniej niż&, więc wyrażenie oznaczax & (1 == 0), co zawsze daje0i niczego nie zlicza. Zapisz(x & 1) == 0. - Rozpoczynanie pętli od indeksu
1w języku indeksującym od zera, co pomija pierwszą wartość, albo od0w Lua i R, gdzie pierwsza wartość ma indeks1.
Najczęstsze pytania4
Jak sprawdzić w kodzie, czy liczba jest parzysta?
Sprawdź, czy reszta z dzielenia przez 2 wynosi zero: x % 2 == 0. Działa to dla liczb dodatnich, ujemnych i zera w każdym popularnym języku. Innym sposobem jest sprawdzenie najmłodszego bitu za pomocą (x & 1) == 0, ponieważ liczby parzyste kończą się bitem 0.
Czy zero jest liczbą parzystą?
Tak. Zero podzielone przez 2 daje 0 bez reszty, więc spełnia definicję liczby parzystej. Znajduje się też między nieparzystymi liczbami -1 i 1, dokładnie tam, gdzie należy liczba parzysta.
Dlaczego x % 2 == 1 nie działa dla liczb ujemnych?
W językach C, C++, Java, C#, JavaScript, Go, Rust, Swift i PHP reszta z dzielenia ma znak liczby dzielonej, więc -3 % 2 daje -1. Python, Ruby, Dart, Lua i R zwracają zamiast tego 1. Sprawdzanie x % 2 != 0 dla nieparzystych i x % 2 == 0 dla parzystych daje w każdym z nich ten sam wynik.
Jaka jest złożoność czasowa zliczania liczb parzystych w tablicy?
Jedno przejście z licznikiem zajmuje czas O(n) i wymaga O(1) dodatkowej pamięci. Trzeba sprawdzić każdą wartość, więc żadna metoda nie jest szybsza niż O(n). Najpierw utworzenie przefiltrowanej listy daje taki sam wynik zliczania, ale wymaga O(n) dodatkowej pamięci.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def countEvens(nums):
# Napisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
nums = [3, 8, 12, 5, 6]
Oczekiwane
3