讨论/《初级算法》 - 外观数列/
《初级算法》 - 外观数列

我有一个疑问,我硬是看了半天时间,最后还是没有明白:真的想搞清楚是为什么
问题:这个题执行用时分布图表中有一个1ms的例子(最后贴代码)它每一次读数都使用String来读,StringBuilder记录 然后toString返回;
我自始至终只是用了一个StringBuilder,我的代码在leetcode怎么跑都是 6ms

//执行1~20的运算
public void countAndSayTest2() {
        for (int i = 1; i < 20; i++) {
            countAndSay5(i);//修改不同的算法
        }
    }
 public void countAndSayTest() {
        //跑一百遍
        int count = 100;
        long startALl = System.nanoTime();
        for (int i = 0; i < count; i++) {
            countAndSayTest2();
        }
        long endAll = System.nanoTime() - startALl;
        System.out.println("外观数列(" + count + ")次耗时:" + endAll + "纳秒,平均:" + (endAll / count) + "纳秒");
 }

在我电脑上的执行结果是

它的结果:
//外观数列(100)次耗时:56473086纳秒,平均:564730纳秒
//外观数列(100)次耗时:88195298纳秒,平均:881952纳秒
//外观数列(100)次耗时:58068338纳秒,平均:580683纳秒
我的结果:
//外观数列(100)次耗时:68074962纳秒,平均:680749纳秒
//外观数列(100)次耗时:56756585纳秒,平均:567565纳秒
//外观数列(100)次耗时:69922979纳秒,平均:699229纳秒

怎么看我的算法也和他的差异不大呀,为什么我的算法在leecode执行结果和它差那么多呢

/*大佬1ms的算法
执行用时:1 ms, 在所有 Java 提交中击败了97.78%的用户
内存消耗:35.9 MB, 在所有 Java 提交中击败了87.11%的用户*/
    public String countAndSay5(int n) {
        String res = new String("");
        for (int i = 0; i < n; i++) {
            res = say(res);
        }
        return res;
    }

    private String say(String s) {
        if (s.equals("")) {
            return "1";
        }
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        int cnt = 1;
        char cur = s.charAt(0);
        for (int i = 1; i < n; i++) {
            if (cur == s.charAt(i)) {
                cnt++;
            } else {
                sb.append((char) ('0' + cnt));
                sb.append(cur);
                cur = s.charAt(i);
                cnt = 1;
            }
        }
        sb.append((char) ('0' + cnt));
        sb.append(cur);
        return sb.toString();
    }
/*我的算法
执行用时:6 ms, 在所有 Java 提交中击败了44.66%的用户
内存消耗:35.9 MB, 在所有 Java 提交中击败了87.51%的用户*/
    public static String countAndSay4(int n) {
        if (n == 1) {
            return "1";
        }
        int i = 2;
        StringBuilder buffer = new StringBuilder("1");
        int readStartIndex;
        int lastLength = 0;

        char c = 0;
        int count = 0;
        while (i <= n) {
            readStartIndex = lastLength;
            lastLength = buffer.length();
            for (int index = readStartIndex; index < lastLength; index++) {
                char ci = buffer.charAt(index);
                if (ci == c) {
                    count += 1;
                } else {
                    if (c != 0) {
                        buffer.append(count).append(c);
                    }
                    c = ci;
                    count = 1;
                }
            }
            buffer.append(count).append(c);

            count = 0;
            c = 0;
            i++;
        }
        return buffer.substring(lastLength);
    }
展开全部 32 讨论