[LeetCode] Problem 412. Fizz Buzz (Solution in 3 ms)

最近開始練習刷一下LeetCode，
新手村先從難度簡單的開始。

選了這題非常容易的Fizz Buzz，題目連結如下：
url -> https://leetcode.com/problems/fizz-buzz/

----------------------------------------------------------------------------

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

簡單啊，就是寫個for 迴圈檢查每個數字是3的倍數或是5的倍數，然後把結果存下來。

Okay, that is easy. I will write a for loop, checking each element to see if it's multiple of three or five, and then store the string into the List.

Here comes my first version of solution:

Solution Ver. 1

public class Solution {
    public List<String> fizzBuzz(int n) {
        // Straightforward solution
        List<String> result = new ArrayList<String>();

        for (int i = 1; i <= n; i++) {
            String str = "";
            if (i % 3 == 0) {
                str += "Fizz";
            }
            if (i % 5 == 0) {
                str += "Buzz";
            }
            if (str.isEmpty()) {
                str += Integer.toString(i);
            }
            result.add(str);
        }
        return result;
    }
}

!!!!!
也太慢了吧!! Blooding slow!!! 前面96%的人是怎麼寫的?!

好吧，看看還有哪裡可以改進，邏輯來說應該是沒有更快的做法了，
來看看是不是有哪些函數的操作比較耗時......
..........
..........
..........
喔！List的add可能比較花時間！
反正output的大小是固定的，會等於input的n值，那麼改成先用一個String array儲存結果，再轉換成String List。
The action "List.add" might spend too much time. Since the output size is fixed and equals to input number "n", we could use a string array and transform it to List format later.

Solution Ver. 2

public class Solution {
    public List<String> fizzBuzz(int n) {
        // Faster solution with String array.
        String[] arr = new String[n]; 
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 == 0) {
                arr[i-1] = "FizzBuzz";
            } else if (i % 3 == 0) {
                arr[i-1] = "Fizz";
            } else if (i % 5 == 0) {
                arr[i-1] = "Buzz";
            } else {
                arr[i-1] = Integer.toString(i);
            }
        }
        return Arrays.asList(arr);
    }}

Boom!!! 效能暴增!!!

不過其實這裏面還有一個大躍進的修改，就是將原本的三個if敘述合併成if-else區塊，否則其實效能不會有很明顯的改進。

In fact, I also change the three if statements to one is-else block. If not, the performance won't improve this much.

不過還是覺得不夠，稍微搜尋了一下，發現%這個運算可以利用counter取代，能夠節省一點時間(雖然程式的可讀性會變差......)

I found that the "% mode" operation could be replaced with counters. Despite the pitfall that the readability will be worse, the overall time spending would be less.

Solution Ver. 3

public class Solution {

    public List<String> fizzBuzz(int n) {

        // The solution with String array and counters.

        

        String[] arr = new String[n];

        for (int i = 1, counter_three = 1, counter_five = 1; i <= n; i++, counter_three++, counter_five++) {

            if (counter_five == 5 && counter_three == 3) {

                arr[i-1] = "FizzBuzz";

                counter_three = 0;

                counter_five = 0;

            } else if (counter_three == 3) {

                arr[i-1] = "Fizz";

                counter_three = 0;

            } else if (counter_five == 5) {

                arr[i-1] = "Buzz";

                counter_five = 0;

            } else {

                arr[i-1] = Integer.toString(i);

            }

        }

        return Arrays.asList(arr);

    }

}

okay, nothing changes...

看來不需要追求無謂的速度降低程式可讀性！

[The end]