FizzBuzz

Q: Berapa kompleksitas waktu FizzBuzz?

Menjawab untuk satu angka memiliki kompleksitas O(1) : sejumlah tetap pemeriksaan sisa bagi dan konversi angka dengan paling banyak 10 digit. Mencetak urutan dari 1 hingga n memiliki kompleksitas O(n) .

PemulaMatematika dan simulasi

+10

Dalam permainan berhitung FizzBuzz, pemain menghitung mulai dari 1 dan mengganti beberapa angka dengan kata-kata. Diberikan nomor giliran n, kembalikan yang diucapkan pemain pada giliran itu: "FizzBuzz" jika n habis dibagi 3 dan 5, "Fizz" jika hanya habis dibagi 3, "Buzz" jika hanya habis dibagi 5, dan jika tidak, n itu sendiri yang ditulis sebagai string, seperti "7".

Fungsi

fizzBuzz(n: integer) → string

ninteger: nomor giliran, bilangan bulat positif
Mengembalikanstring: kata atau angka yang diucapkan pada giliran n, sebagai string

Batasan

1 ≤ n ≤ 10⁹
Jawabannya selalu berupa string, bahkan ketika nilainya adalah angka itu sendiri.

Contoh

Input: n = 15
Output: "FizzBuzz"
Penjelasan: 15 dibagi 3 adalah 5 dan 15 dibagi 5 adalah 3, keduanya tanpa sisa, jadi pada giliran 15 hasilnya "FizzBuzz".

Input: n = 7
Output: "7"
Penjelasan: 7 bersisa 1 saat dibagi 3 dan 2 saat dibagi 5, jadi tidak ada kata yang berlaku dan kamu mengembalikan angka tersebut sebagai teks, "7".

Pertanyaan lanjutan

Aturan baru membuat kelipatan 7 menjadi "Bazz", dengan kata-kata yang digabungkan secara berurutan, jadi 105 menjadi "FizzBuzzBazz". Bagaimana cara menambahkannya tanpa membuat kasus untuk setiap kombinasi?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap aturan adalah satu pemeriksaan sisa bagi. Jebakannya ada pada urutan: 15 habis dibagi 3, jadi fungsi yang memeriksa 3 terlebih dahulu lalu langsung mengembalikan hasil akan menjawab "Fizz" untuk 15. Periksa kondisi gabungan terlebih dahulu, atau susun jawabannya dari kedua pemeriksaan.

Susun kata dari kedua pemeriksaan

Intuisi

Mulai dengan kata kosong. Jika n habis dibagi 3, tambahkan "Fizz"; jika n habis dibagi 5, tambahkan "Buzz". Kedua pemeriksaan selalu dijalankan, jadi kelipatan 15 mengumpulkan kedua bagian secara berurutan dan menjadi "FizzBuzz" tanpa kasus khusus. Jika kata tersebut masih kosong, berarti tidak ada aturan yang berlaku, dan kamu mengembalikan angka tersebut sebagai string.

Algoritma

Atur word menjadi string kosong.
Jika n % 3 == 0, tambahkan "Fizz".
Jika n % 5 == 0, tambahkan "Buzz".
Jika word kosong, kembalikan n yang dikonversi menjadi string.
Jika tidak, kembalikan 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

Periksa 15, lalu 3, lalu 5

Intuisi

Bilangan yang habis dibagi 3 dan 5 adalah bilangan yang habis dibagi 15, karena 3 dan 5 tidak memiliki faktor persekutuan. Jadi, aturan gabungannya adalah satu pemeriksaan, n % 15 == 0, dan pemeriksaan ini dilakukan terlebih dahulu. Jika tidak cocok, kecocokan dengan 3 berarti hanya 3, sedangkan kecocokan dengan 5 berarti hanya 5. Setiap pemeriksaan langsung mengembalikan hasil, dan jika tidak ada yang cocok, kembalikan bilangan tersebut sebagai string.

Algoritma

Jika n % 15 == 0, kembalikan "FizzBuzz".
Jika n % 3 == 0, kembalikan "Fizz".
Jika n % 5 == 0, kembalikan "Buzz".
Jika tidak, kembalikan n yang dikonversi menjadi string, dengan setiap digit ditulis lengkap.

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

Jebakan dan kasus tepi

Menguji 3 atau 5 sebelum 15 lalu langsung mengembalikan hasil: 15, 30, dan 45 menghasilkan "Fizz".
Mengembalikan angka, bukan string. Angka 7 menjadi "7".
Mengubah angka besar menjadi notasi ilmiah. Di R, konversi biasa menampilkan 10^9 sebagai 1e+09; gunakan format(n, scientific = FALSE).
Menampilkan jawaban, bukan mengembalikannya.

Pertanyaan yang sering diajukan3

Mengapa FizzBuzz ditanyakan dalam wawancara pemrograman?

Ini menguji apakah kamu bisa mengubah kumpulan aturan singkat menjadi kode yang berfungsi: pemeriksaan sisa, kondisi dengan urutan yang tepat, dan tipe kembalian yang benar. Bagi orang yang rutin menulis kode, ini hanya membutuhkan beberapa menit, jadi tantangan ini cocok sebagai penyaringan singkat sebelum soal yang lebih sulit.

Bisakah kamu menyelesaikan FizzBuzz tanpa operator modulo?

Ya. Bagi dengan pembagian bilangan bulat, kalikan kembali hasil baginya, lalu bandingkan dengan n: keduanya sama hanya jika tidak ada sisa. Saat mencetak seluruh urutan, kamu juga bisa menggunakan dua penghitung yang diatur ulang pada 3 dan 5.

Berapa kompleksitas waktu FizzBuzz?

Menjawab untuk satu angka memiliki kompleksitas O(1): sejumlah tetap pemeriksaan sisa bagi dan konversi angka dengan paling banyak 10 digit. Mencetak urutan dari 1 hingga n memiliki kompleksitas O(n).

def fizzBuzz(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

n = 15

Output yang diharapkan

"FizzBuzz"