🙉飯不食，水不飲，題必須刷🙉
還不會C語言，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？上簡單題！ 🧡《C語言入門100例》🧡
LeetCode 太簡單？大神盤他！ 🌌《夜深人靜寫演算法》🌌

一、題目

1、題目描述

??寫一個程式，輸出從 1 到 n n n 數字的字串表示，
??1、如果 n n n 是 3 的倍數，輸出 “Fizz”；
??2、如果 n n n 是 5 的倍數，輸出“Buzz”；
??3、如果 n n n 同時是 3 和 5 的倍數，輸出 “FizzBuzz”，
??樣例輸入： 15 15 15
??樣例輸出： [
??????????“1”,
??????????“2”,
??????????“Fizz”,
??????????“4”,
??????????“Buzz”,
??????????“Fizz”,
??????????“7”,
??????????“8”,
??????????“Fizz”,
??????????“Buzz”,
??????????“11”,
??????????“Fizz”,
??????????“13”,
??????????“14”,
??????????“FizzBuzz”
???????]

2、基礎框架

• c++ 版本給出的基礎框架代碼如下：

class Solution {
public:
    vector<string> fizzBuzz(int n) {
    }
};

3、原題鏈接

LeetCode 412. Fizz Buzz

二、解題報告

1、思路分析

• 首先，判斷是不是 15 的倍數，然后再來判斷是否是 3 的倍數，還是 5 的倍數，
• 然后，就是 「數字轉字串」 的操作了，
• 每次通過模 10 取得數字的最后一位，然后再把數字除 10，反復迭代計算，知道數字為 0，并且把取得的每一位組織起來就變成了一個字串，
  
• 按照上圖所示，取得的數字位的順序是 4 → 3 → 2 → 1 4 \to 3 \to 2 \to 1 4→3→2→1，而實際上我們需要的字串順序是 1 → 2 → 3 → 4 1 \to 2 \to 3 \to 4 1→2→3→4，正好是相反的，基于這個特點，我們需要借助一種資料結構，它就是 —— 堆疊，
• 當問題特征滿足 「先進后出」 時，可以利用 「堆疊」 這種資料結構來輔助解決問題，

2、時間復雜度

• 時間復雜度為 O ( n ) O(n) O(n)，

3、代碼詳解

class Solution {
    string getString(int n) {
        stack<int> stk;
        string s;
        while(n) {
            stk.push( n % 10 + '0' );    // (1)
            n /= 10;                     // (2)
        }
        while(!stk.empty()) {            
            s.push_back( stk.top() );    // (3)
            stk.pop();
        }
        return s;
    }
public:
    vector<string> fizzBuzz(int n) {
        vector<string> ans;
        for(int i = 1; i <= n; ++i) {
            if(i % 3 == 0 && i % 5 == 0) {
                ans.push_back("FizzBuzz");
            }else if(i % 3 == 0) {
                ans.push_back("Fizz");
            }else if(i % 5 == 0) {
                ans.push_back("Buzz");
            }else {
                ans.push_back( getString(i) );
            }
        }
        return ans;

    }
};

• ( 1 ) (1) (1) 每次模10取當前數字 n n n 的最后一位，并且通過加上'0'將整數轉換成字符；
• ( 2 ) (2) (2) 除上 10，繼續迭代計算下一位；
• ( 3 ) (3) (3) 將堆疊中的元素按堆疊順序彈出來，組成字串；
• 其它部分代碼比較容易理解，就不作過多解釋了，

三、本題小知識

當問題特征滿足 「先進后出」 時，可以利用 「堆疊」 這種資料結構來輔助解決問題，