412. FizzBuzz

412. FizzBuzz 是一個相當經典的題目，號稱是 Google 面題題 之一，這個題目雖然看似簡單的但有許多細節值得深究。

先看一下題目描述

Given an integer n, return a string array answer (1-indexed) where:

answer[i] == "FizzBuzz" if i is divisible by 3 and 5.
answer[i] == "Fizz" if i is divisible by 3.
answer[i] == "Buzz" if i is divisible by 5.
answer[i] == i if non of the above conditions are true.

再搭配範例理解題目

• Example 1:

Input: n = 3
Output: ["1","2","Fizz"]

• Example 2:

Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

讓使用者輸入一個數字 n，產生一個從 1 到 n 的容器，當遇到三的倍數改成 Fizz、 五的倍數改成 Buzz、同時滿足改成 FizzBuzz。

看完這個題目描述之後，你是不是心想「這麼簡單的題目，不就是條件判斷嗎？」，那就讓我們繼續看下去！

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：暴力法

第一種想法就是真的從 1 開始跑一個迴圈，用三個條件分別判斷「三的倍數」、「五的倍數」和「同時滿足三和五的倍數」。唯一要注意的點就是「同時滿足三和五的倍數」條件比較嚴格，所以要放在前面作判斷。

那我們先用 Python 實作看看

class Solution:
    def fizzBuzz(self, n):
        ans = []

        for num in range(1,n+1):
            if num % 3 == 0 and num % 5 == 0:
                ans.append("FizzBuzz")
            elif num % 3 == 0:
                ans.append("Fizz")
            elif num % 5 == 0:
                ans.append("Buzz")
            else:
                ans.append(str(num))

        return ans

也可以用 JavaScript 復刻一次

var fizzBuzz = function(n) {
  let ans = [];
  
  for (let i = 1; i <= n; i++) {
    if (i % 15 === 0) {
      ans.push('FizzBuzz');
    } else if (i % 5 === 0) {
      ans.push('Buzz');
    } else if (i % 3 === 0) {
      ans.push('Fizz');
    } else {
      ans.push(i + '');
    }
  }
  return ans;
};

方法 ②：字串組裝

試著思考一下，本題有兩個數的倍數，所以有三個；但如果題數有三個數字，當遇到三的倍數改成 Fizz、 五的倍數改成 Buzz、七的倍數變成 Jazz 的情況，那需要考慮的規則就有：

1. Divisible by 3
2. Divisible by 5
3. Divisible by 7
4. Divisible by 3 and 5
5. Divisible by 3 and 7
6. Divisible by 7 and 3
7. Divisible by 3 and 5 and 7
8. Not divisible by 3 or 5 or 7.

這就是所謂的條件會變成指數的成長，第一種方法會造成程式碼撰寫的複雜度急劇上升。根據觀察之後，我們發現這個轉換規則會有先後的順序關係：

1. Divisible by 3 => Fizz
2. Divisible by 3 and 5 => FizzBuzz
3. Divisible by 3 and 7 => FizzJazz
4. Divisible by 3 and 5 and 7 => FizzBuzzJazz

因此，我們想到的方法可以利用字串組裝的方式，幾個數字只需要跑幾個條件：

s = ''
if num % 3 == 0:
    s += "Fizz"
if num % 5 == 0:
    s += "Buzz"

那我們先用 Python 實作看看

class Solution:
    def fizzBuzz(self, n):
        ans = []

        for num in range(1,n+1):

            s = ""

            if num % 3 == 0:
                s += "Fizz"
            if num % 5 == 0:
                s += "Buzz"
            if not num_ans_str:
                s = str(num)

            ans.append(s)  

        return ans

也可以用 JavaScript 復刻一次

var fizzBuzz = function(n) {
  
  let ans = [];
  
  for (let i = 1; i <= n; i++) {
    
    let s = '';
    
    if (i % 3 === 0)
      s += 'Fizz';
    if (i % 5 === 0)
      s += 'Buzz';
    if (!str)    
      s = i + '';
    
    ans.push(s);
  }
  
  return ans
};

方法 ③：Hashing

剛剛的想法是，如果 n 個數字需要有 n 個判斷，那要如何可以自動化產生 n 個判斷呢？可以把 n 個數字的轉換關係寫成一個 Hashmap，像這樣子：

d = {3 : "Fizz", 5 : "Buzz"}
for key in d.keys():
    if num % key == 0:
        s += d[key]

那我們先用 Python 實作看看

class Solution:
    def fizzBuzz(self, n):

        ans = []
        d = {3 : "Fizz", 5 : "Buzz"}

        for num in range(1,n+1):
            s = ""

            for key in d.keys():
                if num % key == 0:
                    s += d[key]
            if not num_ans_str:
                s = str(num)

            ans.append(s)  

        return ans

也可以用 JavaScript 復刻一次

let fizzBuzz = function(n) {
  
  let ans = [];
  let d = { 3: 'Fizz', 5: 'Buzz', ...};
  
  for (let i = 1; i <= n; i++) {
    let s = '';
    for (let key in d) {
      if (i % parseInt(key, 10) === 0) {
        s += d[key];
      }
    }

    if (!s) {
      s += i;
    }

    ans.push(s);
  }

  return result;
};

方法 ④：炫技法

最後一種方法是利用「三元運算子」或「模數運算」做優化，這邊就當成一種火力展力給大家看看就好！

那我們先用 Python 實作看看

class Solution:
    def fizzBuzz(self, n):
        ans = []
        for n in range(1, N+1):
            ans.append(int(not(n % 3)) * 'Fizz' + int(not(n % 5)) * 'Buzz' or n)
        return ans

也可以用 JavaScript 復刻一次

var fizzBuzz = function(n) {
  let ans = [];
  for (let i = 1; i <= n; i++) {
    s = ((i % 3 == 0 ? 'Fizz' : '') + (i % 5 == 0 ? 'Buzz' : '')) || (i + '');
    ans.push(s);
  }
  
  return ans
};

反思沉澱

這個題目絕對不是一個難題，決大部分會寫程式的人一定寫得出來！但這個過程中的幾種延伸思考跟優化技巧反而就蠻有趣的，這就是我前面強調「#刻意優化」的例子。能寫出一個程式不難，但要寫出一個好的程式很難非常難。當你從「方法 ④：炫技法」再回頭看「方法 ①：暴力法」應該就可以明顯看受到「好」程式的的差異。所以這個題目雖然看似簡單的但有許多細節值得深究，也希望大家在一個例子中一起感受優化的過程。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 1195. Fizz Buzz Multithreaded

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。