LeetCode算法题-Fizz Buzz（Java实现）

这是悦乐书的第221次升级，第233篇原创

01 看题和准备

今天详情的是LeetCode算法题中Easy级别的第88题（顺位题号是412）。

编写一个程序，输出从1到n的数字的字符串表示。但对于三的倍数，它应输出“Fizz”而不是数字，对于五的倍数，应该输出“Buzz”。 对于三和五共同的倍数，应输出“FizzBuzz”。例如：

输入：n = 15
输出：[“1″,”2″,”Fizz”,”4″,”Buzz”,”Fizz”,”7″,”8″,”Fizz”,”Buzz”,”11″,”Fizz”,”13″,”14″,”FizzBuzz”]

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

将n转为对应的字符串，分为三种情况：

1、是3或者者5的倍数，那么n转为”Fizz”或者者”Buzz”。

2、是3和5的共同倍数，那么n转为”FizzBuzz”。

3、不是前两种情况，那么n直接转为字符串。

因而，直接使用取余，判断余数能否为0，来分别对应上述三种情况，将对应的字符串增加进list中就可。

此解法时间复杂度为O(n)，空间复杂度为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 第二种解法

在第一种解法里，我们分析了三种需要判断的情况，对于第二种情况，可以直接用n对15取余来判断。

此解法时间复杂度为O(n)，空间复杂度为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 第三种解法

使用两个变量计数（也可以了解为双指针），替换取余算法。

当某一变量等于3或者者5时，将其所代表的Fizz或者者Buzz字符串增加进list，而后变量归零。当一变量等于3，且另一变量等于5时，将FizzBuzz增加进list，而后两变量同时归零。

此解法时间复杂度为O(n)，空间复杂度为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 小结

算法专题目前已连续日更超过两个月，算法题文章88+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是一律内容，假如大家有什么好的解法思路、建议或者者其余问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！