一道简单的LeetCode题的优化，从优于14%到99%

我到现在已经刷了一百多道leetcode的题目了，这里用一道简单的leetcode题来说明一下，写一个优秀的代码有多重要。题目的是
Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"
Example 2:

Input: 4
Output: "1211"

题目的意思是给一个int n的，输出这个序列的第n的数字，这个序列的规则的把上一个数字读法当做当前数字，
比如第一个1，英语读one 1（一个1），第二个数字就是11，英语读two 1s（2个1），第三个数字就是21，英语读作one 2 ，then one 1，第四个数字就是1211……以此类推。
博主的思路是以不同的数字为界，然后计算每一组数字的个数。把每组数字个数放在前面，数字本身放在后面，然后拼接起来。

   class Solution {
    public String countAndSay(int n) {
        String cur = "1";
        String pre = "";

        for(int i =1;i<n;i++){//循环n-1次，得到第n个数字
            pre=cur;//缓存上一个数字，用来遍历
            cur="";//用来存放新的数字
            char c = pre.charAt(0);
            int count=0;
            for(int j =0;j<pre.length();j++){//遍历所有数字，得到新的数字
                if(c==pre.charAt(j))
                    count++;
                if(j==pre.length()-1 || c!=pre.charAt(j+1)){//当到末尾或者不等于下一个字符时候将数字加到cur里面
                    cur+=String.valueOf(count)+String.valueOf(c);
                    count=0;//重新计数
                    if(j==pre.length()-1)//当是末尾时候，跳出循环
                        break;
                    c = pre.charAt(j+1);//c等于下一个字符
                }

            }

        }
        return cur;

    }
}

然后提交代码

发现，耗时30ms，优于14%的代码，毫无疑问，这是比较差的解决方案。
接下来我们修改一下，我们将String 改成StringBuilder，因为，String是不可变的对象,我们在修改String的时候，其实是重新生成了一个新的String对象，当有大量字符串修改的时候，性能会比较差，而StringBuilder不同，在修改的时候只是修改了对象中的值。

    public String countAndSay(int n) {
        StringBuilder sb = new StringBuilder();
        String s = "1";
        int count=1;
        for(int i =1;i<n;i++){
            sb = new StringBuilder();
            for(int j=0;j<s.length();j++){
                if(j+1<s.length()&&s.charAt(j+1)==s.charAt(j)) count++;
                else {
                    if(count!=0)
                        sb.append(count).append(s.charAt(j));
                    count=1;
                }

            }
            s=sb.toString();
        }

        return s;

    }

速度是7ms，所以在有大量字符串修改的地方，使用StringBuilder会大大提升效率，这里快了将近500%，这个提升不可忽视啊。

当你把循环里的代码变成函数时，你会发现一个很神奇的事，

public String countAndSay(int n) {
        StringBuilder sb = new StringBuilder();
        String s = "1";
        for(int i =1;i<n;i++){
            s=getStr(s);
        }
        return s;
    }

    public String getStr(String s){
        int count=1;
        StringBuilder sb = new StringBuilder();
        for(int j=0;j<s.length();j++){
            if(j+1<s.length()&&s.charAt(j+1)==s.charAt(j)) count++;
            else {
                if(count!=0)
                    sb.append(count).append(s.charAt(j));
                count=1;
            }

        }
        return sb.toString();

    }

速度变成了4ms，这里不知道为什么会这样子，逻辑一样，抽出方法后，速度会变快。知道为什么的朋友请留言告诉我一下，谢谢！

最后我告诉大家最快的方法是下面这个，预先就把值计算好，有需要时就直接返回结果。（缓存）

public String countAndSay(int n) {

        switch(n){
        case 1: return "1";
        case 2: return "11";
        case 3: return "21";
        case 4: return "1211";
        case 5: return "111221";
        case 6: return "312211";
        case 7: return "13112221";
        case 8: return "1113213211";
        case 9: return "31131211131221";
        case 10: return "13211311123113112211";
        case 11: return "11131221133112132113212221";
        case 12: return "3113112221232112111312211312113211";
        case 13: return "1321132132111213122112311311222113111221131221";
        case 14: return "11131221131211131231121113112221121321132132211331222113112211";
        case 15: return "311311222113111231131112132112311321322112111312211312111322212311322113212221";
        case 20: return "11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211";
        case 25: return "132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221";
        case 30: return "3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211";
        default: return "";
        }
    }

在很多情况下，我们需要用到算法，有时候是用时间换空间，有时候用空间换时间，然后一些平时不注意的细节会造成大量不必要的开销，就比如用String还是StringBuilder，缓存是提升速度非常有效的方法，但是过多的缓存会浪费空间，所以要权衡好如何使用缓存。在平时的开发中也是如此。