算法题-FizzBuzz

题目链接：https://leetcode-cn.com/problems/fizz-buzz/ 题目描述： 写一个程序，输出从 1 到 n 数字的字符串表示。

如果 n 是3的倍数，输出“Fizz”；

如果 n 是5的倍数，输出“Buzz”；

3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：

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

解法一

时间复杂度：O(N)，空间复杂度：O(1)

class Solution { public List<String> fizzBuzz(int n) { List<String> ans = new ArrayList<String>(); for(int i=1;i<=n;i++) { //标记是3的倍数 boolean isMultiple3 = (i % 3 == 0); //标记是5的倍数 boolean isMultiple5 = (i % 5 == 0); //如果既是3的倍数又是5的倍数，将“FizzBuzz”加入ans if(isMultiple3 && isMultiple5) { ans.add("FizzBuzz"); } //如果只是3的倍数，将“Fizz”加入ans else if(isMultiple3) { ans.add("Fizz"); } //如果只是5的倍数，将“Bizz”加入ans else if(isMultiple5) { ans.add("Buzz"); } //如果既不是3的倍数又不是5的倍数，将这个数转换为String型加入ans else { ans.add(Integer.toString(i)); } } return ans; } }

解法二

时间复杂度：O(N)，空间复杂度：O(1)

//不使用取模运算 class Solution { public List<String> fizzBuzz(int n) { List<String> ans = new ArrayList<String>(); int fizz = 3; int buzz = 5; for(int i=1;i<=n;i++) { if(i == fizz && i == buzz) { //满足条件时，说明既是3的倍数又是5的倍数 ans.add("FizzBuzz"); //同时，fizz+3，buzz+5,下一个能被3整除和被5整除的数 fizz+=3; buzz+=5; } else if(i == fizz) { //满足说明只能被3整除 ans.add("Fizz"); //同时，fizz+3,标记下一个能被3整除的数 fizz+=3; } else if(i == buzz) { //能被5整除的数 ans.add("Buzz"); //同时，bizz+5,标记下一个能被5整除的数 buzz+=5; } else ans.add(Integer.toString(i)); } return ans; } }

解法三

时间复杂度：O(N)，空间复杂度：O(1)

//减少一次判断 class Solution { public List<String> fizzBuzz(int n) { List<String> ans = new ArrayList<String>(); for(int i=1;i<=n;i++) { //标记可以被3整除 boolean isMultiple3 = (i % 3 == 0); //标记可以被5整除 boolean isMultiple5 = (i % 5 == 0); //s记录这个数的整除结果对应的字符串 String s = ""; //如果能被3整除，就加入"Fizz" if(isMultiple3) { s+="Fizz"; } //如果能被5整除，就加入"Bizz" if(isMultiple5) { s+="Buzz"; } //如果此时s什么都没加入，说明这个数既不能被3整除，也不能被5整除 if(s == "") { s+=Integer.toString(i); } //将这个数对应的结果加入ans中 ans.add(s); } return ans; } }

解法四

时间复杂度：O(N)，空间复杂度：O(1)

//使用哈希表存放整除数（3、5）和其对应字符（"Fuzz"、"Buzz"）的键值对 //当这种映射关系很多时，可以试用哈希表。更好维护。 class Solution { public List<String> fizzBuzz(int n) { List<String> ans = new ArrayList<String>(); //使用哈希表来存放分别以3和5为key,"Fizz"和“Buzz”为value的键值对 HashMap<Integer,String> fizzbuzzDist = new HashMap<Integer,String>() { { put(3,"Fizz"); put(5,"Buzz"); } }; for(int i=1;i<=n;i++) { String s = ""; //对dist中的每个key进行判断，是否可以整除。如果可以则s加上其对应的value for(Integer key : fizzbuzzDist.keySet()) { if(i % key == 0) { s += fizzbuzzDist.get(key); } } if(s == "") { s += Integer.toString(i); } ans.add(s); } return ans; } }