這是悅樂書的第221次更新，第233篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第88題（順位題號(hào)是412）。

編寫一個(gè)程序，輸出從1到n的數(shù)字的字符串表示。但對(duì)于三的倍數(shù)，它應(yīng)輸出“Fizz”而不是數(shù)字，對(duì)于五的倍數(shù)，應(yīng)該輸出“Buzz”。 對(duì)于三和五共同的倍數(shù)，應(yīng)輸出“FizzBuzz”。例如：

輸入：n = 15
輸出：["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測(cè)試。

02 第一種解法

將n轉(zhuǎn)為對(duì)應(yīng)的字符串，分為三種情況：

1、是3或者5的倍數(shù)，那么n轉(zhuǎn)為"Fizz"或者"Buzz"。

2、是3和5的共同倍數(shù)，那么n轉(zhuǎn)為"FizzBuzz"。

3、不是前兩種情況，那么n直接轉(zhuǎn)為字符串。

因此，直接使用取余，判斷余數(shù)是否為0，來分別對(duì)應(yīng)上述三種情況，將對(duì)應(yīng)的字符串添加進(jìn)list中即可。

此解法時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

public List<String> fizzBuzz(int n) {
    List<String> list = new ArrayList<String>();
    for (int i=1; i<= n; i++) {
        if (i%3 != 0) {
            if (i%5 != 0) {
                list.add(i+"");
            } else {
                list.add("Buzz");
            }
        } else {
            if (i%5 != 0) {
                list.add("Fizz");
            } else {
                list.add("FizzBuzz");
            }
        }
    }
    return list;
}

03 第二種解法

在第一種解法里，我們分析了三種需要判斷的情況，對(duì)于第二種情況，可以直接用n對(duì)15取余來判斷。

此解法時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

public List<String> fizzBuzz2(int n) {
    List<String> list = new ArrayList<String>();
    for (int i = 1; i <= n; i++) {
        if (i % 15 == 0) {
            list.add("FizzBuzz");
        } else if (i % 3 == 0) {
            list.add("Fizz");
        } else if (i % 5 == 0) {
            list.add("Buzz");
        } else {
            list.add(i+"");
        }
    }
    return list;
}

04 第三種解法

使用兩個(gè)變量計(jì)數(shù)（也可以理解為雙指針），替換取余算法。

當(dāng)某一變量等于3或者5時(shí)，將其所代表的Fizz或者Buzz字符串添加進(jìn)list，然后變量歸零。當(dāng)一變量等于3，且另一變量等于5時(shí)，將FizzBuzz添加進(jìn)list，然后兩變量同時(shí)歸零。

此解法時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

public List<String> fizzBuzz3(int n) {
    List<String> list = new ArrayList<String>();
    int Fizz = 0, Buzz = 0;
    for (int i = 1; i <= n; i++) {
        Fizz++;
        Buzz++;
        if (Fizz == 3 && Buzz == 5) {
            list.add("FizzBuzz");
            Fizz = 0;
            Buzz = 0;
        } else if(Fizz == 3) {
            list.add("Fizz");
            Fizz = 0;
        } else if(Buzz == 5) {
            list.add("Buzz");
            Buzz = 0;
        } else {
            list.add(i+"");
        }
    }
    return list;
}

05 小結(jié)

算法專題目前已連續(xù)日更超過兩個(gè)月，算法題文章88+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部?jī)?nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！