iT邦幫忙

2021 iThome 鐵人賽

DAY 7
1
Software Development

LeetCode 雙刀流:Python x JavaScript系列 第 7

LeetCode 雙刀流: 412. FizzBuzz

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
};

反思沉澱

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

舉一反三看看相似題

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


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


上一篇
LeetCode 雙刀流: 1. Two Sum
下一篇
LeetCode 雙刀流: 26. Remove Duplicates from Sorted Array
系列文
LeetCode 雙刀流:Python x JavaScript30

2 則留言

0
Ellen Lee
iT邦新手 5 級 ‧ 2021-09-22 21:19:16

我想起了當年的 A+ 班......

0
TD
iT邦新手 4 級 ‧ 2021-09-22 23:00:28
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)    
      str = i + '';
    
    ans.push(str);
  }
  
  return ans
};

這裡可能需要調整一下:統一變數命名,移除逗號 :p

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

我要留言

立即登入留言