FizzBuzz

Q: Jaka jest złożoność czasowa FizzBuzz?

Odpowiedź dla jednej liczby ma złożoność O(1) : stałą liczbę sprawdzeń reszty z dzielenia oraz konwersję liczby mającej najwyżej 10 cyfr. Wypisanie sekwencji od 1 do n ma złożoność O(n) .

PoczątkującyMatematyka i symulacja

+10

W grze w liczenie FizzBuzz gracze liczą od 1 wzwyż i zastępują niektóre liczby słowami. Dla numeru tury n zwróć to, co gracz mówi w tej turze: "FizzBuzz", jeśli n jest podzielne zarówno przez 3, jak i przez 5, "Fizz", jeśli jest podzielne tylko przez 3, "Buzz", jeśli jest podzielne tylko przez 5, a w przeciwnym razie samo n zapisane jako ciąg znaków, na przykład "7".

Funkcja

fizzBuzz(n: integer) → string

ninteger: numer tury, dodatnia liczba całkowita
Zwracastring: słowo lub liczba wypowiedziane w turze n, jako ciąg znaków

Ograniczenia

1 ≤ n ≤ 10⁹
Odpowiedź zawsze jest ciągiem znaków, nawet gdy jest samą liczbą.

Przykłady

Wejście: n = 15
Wyjście: "FizzBuzz"
Wyjaśnienie: 15 podzielone przez 3 to 5, a 15 podzielone przez 5 to 3 — w obu przypadkach bez reszty, więc w turze 15 jest "FizzBuzz".

Wejście: n = 7
Wyjście: "7"
Wyjaśnienie: 7 daje resztę 1 przy dzieleniu przez 3 i resztę 2 przy dzieleniu przez 5, więc żadne słowo nie pasuje i zwracasz liczbę jako tekst, "7".

Pytanie dodatkowe

Nowa reguła sprawia, że wielokrotności 7 dają "Bazz", a słowa są łączone w kolejności, więc 105 daje "FizzBuzzBazz". Jak dodać tę regułę bez osobnego przypadku dla każdej kombinacji?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każda reguła to jedno sprawdzenie reszty z dzielenia. Pułapka tkwi w kolejności: 15 jest podzielne przez 3, więc funkcja, która najpierw sprawdza 3 i od razu zwraca wynik, odpowie "Fizz" dla 15. Sprawdź najpierw przypadek łączony albo zbuduj odpowiedź na podstawie obu sprawdzeń.

Zbuduj słowo na podstawie obu sprawdzeń

Intuicja

Zacznij od pustego słowa. Jeśli 3 dzieli n, dodaj "Fizz"; jeśli 5 dzieli n, dodaj "Buzz". Oba sprawdzenia są zawsze wykonywane, więc wielokrotność 15 zbiera obie części w podanej kolejności i staje się "FizzBuzz" bez specjalnego przypadku. Jeśli słowo nadal jest puste, żadna reguła nie została zastosowana i zwracasz liczbę jako ciąg znaków.

Algorytm

Ustaw word jako pusty ciąg znaków.
Jeśli n % 3 == 0, dodaj na końcu "Fizz".
Jeśli n % 5 == 0, dodaj na końcu "Buzz".
Jeśli word jest pusty, zwróć n przekonwertowane na ciąg znaków.
W przeciwnym razie zwróć word.

def fizzBuzz(n):
    word = ""
    if n % 3 == 0:
        word += "Fizz"
    if n % 5 == 0:
        word += "Buzz"
    # An empty word means neither 3 nor 5 divides n.
    if word == "":
        return str(n)
    return word

Sprawdź 15, potem 3, a następnie 5

Intuicja

Liczba podzielna zarówno przez 3, jak i przez 5 jest dokładnie liczbą podzielną przez 15, ponieważ 3 i 5 nie mają wspólnego dzielnika. Zatem połączona reguła to jedno sprawdzenie, n % 15 == 0, które wykonuje się jako pierwsze. Jeśli się nie powiedzie, dopasowanie do 3 oznacza tylko 3, a dopasowanie do 5 oznacza tylko 5. Każde sprawdzenie natychmiast zwraca wynik, a jeśli żadne nie pasuje, zwracasz liczbę jako ciąg znaków.

Algorytm

Jeśli n % 15 == 0, zwróć "FizzBuzz".
Jeśli n % 3 == 0, zwróć "Fizz".
Jeśli n % 5 == 0, zwróć "Buzz".
W przeciwnym razie zwróć n przekonwertowane na ciąg znaków, zapisując każdą cyfrę słownie.

def fizzBuzz(n):
    if n % 15 == 0:
        return "FizzBuzz"
    if n % 3 == 0:
        return "Fizz"
    if n % 5 == 0:
        return "Buzz"
    return str(n)

Pułapki i przypadki brzegowe

Sprawdzanie 3 lub 5 przed 15 i natychmiastowe zwracanie wyniku: 15, 30 i 45 dają "Fizz".
Zwracanie liczby zamiast ciągu znaków. Dla 7 wynikiem jest "7".
Konwertowanie dużych liczb do notacji naukowej. W R zwykła konwersja wyświetla 10^9 jako 1e+09; użyj format(n, scientific = FALSE).
Wyświetlanie odpowiedzi zamiast jej zwracania.

Najczęstsze pytania3

Dlaczego podczas rozmów kwalifikacyjnych na stanowiska programistyczne zadaje się pytanie o FizzBuzz?

Sprawdza, czy potrafisz przełożyć krótki zestaw reguł na działający kod: test reszty z dzielenia, warunki we właściwej kolejności i odpowiedni typ zwracany. Osobie, która regularnie programuje, zajmuje to kilka minut, więc sprawdza się jako szybki test przed trudniejszymi pytaniami.

Czy potrafisz rozwiązać FizzBuzz bez operatora modulo?

Tak. Dziel przez dzielenie całkowite, pomnóż iloraz z powrotem i porównaj go z n: są równe tylko wtedy, gdy nie pozostaje żadna reszta. Gdy wypisujesz całą sekwencję, możesz też używać dwóch liczników, które zerują się przy 3 i przy 5.

Jaka jest złożoność czasowa FizzBuzz?

Odpowiedź dla jednej liczby ma złożoność O(1): stałą liczbę sprawdzeń reszty z dzielenia oraz konwersję liczby mającej najwyżej 10 cyfr. Wypisanie sekwencji od 1 do n ma złożoność O(n).