Count Even Numbers

Q: 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, nawet w językach, w których -3 % 2 wynosi -1 . Możesz też sprawdzić najmłodszy bit za pomocą (x & 1) == 0 .

Q: Czy zero jest liczbą parzystą?

Tak. Zero podzielone przez 2 daje 0 bez reszty, więc spełnia definicję liczby parzystej. Leży też między nieparzystymi liczbami -1 i 1 , gdzie znajduje się liczba parzysta.

Q: Jaka jest złożoność czasowa zliczania liczb parzystych w tablicy?

Jedno przejście z licznikiem zajmuje czas O(n) i wymaga dodatkowej pamięci O(1) . Każdą wartość trzeba sprawdzić, więc żadna metoda nie jest szybsza niż O(n) .

PoczątkującyTablice i napisy Matematyka i symulacja

+10

Mając niepustą listę liczb całkowitych nums, zwróć liczbę jej wartości parzystych. Liczba jest parzysta, gdy podzielenie jej przez 2 nie daje reszty, co dotyczy także 0 i liczb ujemnych, takich jak -4.

Funkcja

countEvens(nums: integer-array) → integer

numsinteger-array: lista liczb całkowitych do sprawdzenia
Zwracainteger: liczba parzystych wartości w nums

Ograniczenia

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Przykłady

Wejście: nums = [3, 8, 12, 5, 6]
Wyjście: 3
Wyjaśnienie: 8, 12 i 6 dzielą się przez 2 bez reszty; 3 i 5 nie. Odpowiedź to 3.

Wejście: nums = [-4, -3, 0, 7]
Wyjście: 2
Wyjaśnienie: -4 = 2 × (-2) i 0 = 2 × 0, więc obie liczby są parzyste. -3 i 7 są nieparzyste, a ich liczba wynosi 2.

Wejście: nums = [1, 9, 15]
Wyjście: 0
Wyjaśnienie: 1, 9 i 15 są nieparzyste, więc odpowiedź to 0.

Pytanie dodatkowe

Dostajesz wiele pytań: ile parzystych wartości znajduje się między indeksem l a indeksem r? Czy po jednym przejściu po nums możesz odpowiadać na każde z nich w czasie O(1)?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Sprawdź każdą wartość raz i policz te, które przy dzieleniu przez 2 dają resztę 0. Porównanie reszty z 0 zamiast sprawdzania, czy liczba jest nieparzysta, przez porównanie z 1, działa poprawnie także dla liczb ujemnych.

Zbierz parzyste wartości, a następnie je policz

Intuicja

Wybierz parzyste wartości za pomocą filtra, a następnie zwróć długość wyniku. Dla [3, 8, 12, 5, 6] przefiltrowana lista to [8, 12, 6], więc odpowiedź to 3.

Złożoność czasowa wynosi O(n), ale nowa lista wymaga O(n) pamięci, nawet dla 5000 wartości, tylko po to, by raz odczytać jej długość.

Algorytm

Utwórz nową listę zawierającą każde x z nums, dla którego x % 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ą rosnącego licznika

Intuicja

Zamiast listy użyj licznika i dodawaj 1 dla każdej wartości spełniającej warunek x % 2 == 0. Liczba parzysta daje resztę 0 niezależnie od znaku, więc test działa dla -4 i 0 w każdym języku. Test na nieparzystość zapisany jako x % 2 == 1 nie działa: w C, Java, JavaScript i większości języków podobnych do C reszta ma znak liczby, więc -3 % 2 wynosi -1.

Jedno przejście i jedna liczba całkowita: czas O(n), pamięć O(1).

Algorytm

Ustaw count na 0.
Przejdź pętlą przez każdą wartość x w nums.
Jeśli x % 2 == 0, dodaj 1 do count.
Po zakończeniu 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

Liczenie wartości nieparzystych za pomocą x % 2 == 1 i odejmowanie ich od długości. W językach podobnych do C -3 % 2 daje -1, więc [-3] zwraca 1 zamiast 0.
Traktowanie 0 jako wartości ani parzystej, ani nieparzystej. 0 = 2 × 0, więc [0] zwraca 1.
Zapisanie testu bitowego jako x & 1 == 0. W C, C++ i JavaScript == ma wyższy priorytet niż &, więc wyrażenie oznacza x & (1 == 0), co zawsze daje 0 i nie zlicza żadnych wartości. Zapisz (x & 1) == 0.

Najczęstsze pytania3

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, nawet w językach, w których -3 % 2 wynosi -1. Możesz też sprawdzić najmłodszy bit za pomocą (x & 1) == 0.

Czy zero jest liczbą parzystą?

Tak. Zero podzielone przez 2 daje 0 bez reszty, więc spełnia definicję liczby parzystej. Leży też między nieparzystymi liczbami -1 i 1, gdzie znajduje się liczba parzysta.

Jaka jest złożoność czasowa zliczania liczb parzystych w tablicy?

Jedno przejście z licznikiem zajmuje czas O(n) i wymaga dodatkowej pamięci O(1). Każdą wartość trzeba sprawdzić, więc żadna metoda nie jest szybsza niż O(n).

def countEvens(nums):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

nums = [3, 8, 12, 5, 6]

Oczekiwany wynik