LeetCode-报数(java实现)

谁践踏了优雅 2022-05-11 02:16 157阅读 0赞

题目如下：

![70][]

当时看到这个题目，第一个想法就是使用递归，思考良久还是没有思路。然后网上看了好几个实现，最后都要带上一句这题很简单，算法萌新瑟瑟发抖......

ok，言归正传。先上代码

public String countAndSay(int n) {
            if(n == 1){
                return "1";
            }
            //递归调用，然后对字符串处理
            String str = countAndSay(n-1) + "*";//为了str末尾的标记，方便循环读数
            char[] c = str.toCharArray();
            int count = 1;
            StringBuilder s = new StringBuilder();
            for(int i = 0; i < c.length - 1;i++){
                if(c[i] == c[i+1]){
                    count++;//计数增加
                }else{
                    //s.append(s);
                    s.append("" + count + c[i]);//上面的*标记这里方便统一处理
                    count = 1;//初始化
                }
            }
            return s.toString();
        }

如果只数一次，那么结果就是“1”，这是特殊情况；如果要数的次数大于1就要进入递归了。对于字符串我们自然无法对其中的字符进行操作，所以需要把String转换成char数组。然后在for循环外面定义了一个count变量，主要作用是当出现连续的字符时进行累加，最后转换成字符，这是最关键的一环。

在做这个题目的过程中，刚开始用的是都是string，运行时间是30ms左右。后来把for循环中的string变量换成了Stringbuffer，执行用时骤降至8ms。这给我了很大的启示，不能再无脑的使用String，在适当的时候使用合适的变量类型可以带来很大的性能提升。

但是在提交之后，我看到了用时1ms的范例。简直是“投机取巧”的典型......因为测试用例就18个，所以switch cash写了18中情况。这真的是太聪明了！！！

![70 1][]

[70]: /images/20220511/778a7bd4e25841d3a1708a22b1ed5fbe.png
[70 1]: /images/20220511/01e3452dcf35421ea52635f4b14afb1c.png