Java编程任务效率

Question

我正在努力学习如何编写更高效的代码。你们中的一些天才开发人员有没有可能帮助我，让我知道我的代码出了什么问题？怎样才能使它更有效率？

我刚刚在Codility.com上完成了一个任务，并且通过了所有的测试，但是当更大的字符串被传入时，我的代码不够高效。

任务说明：

字符串S的前缀是S的任何前导连续部分，例如，"c“和"cod”是字符串“cod”的前缀。为了简单起见，我们要求前缀是非空的。字符串S的前缀P的乘积是P的出现次数乘以P的长度，更准确地说，如果前缀P由K个字符组成，而P在S中恰好发生T次，则乘积等于K*T。

例如，S= "abababa“有以下前缀：

A，其乘积等于1*4= 4， "ab"，其乘积等于2*3= 6， "aba"，其产品等于3*3= 9， "abab"，其乘积等于4*2= 8， 其产品等于5*2= 10， "ababab"，其乘积等于6*1= 6， "abababa"，其乘积等于7 *1=7。

最长的前缀与原始字符串相同。目标是选择这样一个前缀，使产品的价值最大化。在上面的例子中，最大乘积是10。

在这个问题中，我们只考虑由小写英文字母(A)组成的字符串。

写函数

class Solution { public int solution(String S); }

给定一个由N个字符组成的字符串S，返回给定字符串的任何前缀的最大乘积。如果产品大于1,000,000,000，函数应返回1,000,000,000。

例如，对于字符串：

S= "abababa“函数应该返回10，如前所述， S= "aaa“函数应该返回4，因为前缀"aa”的乘积是最大的。

假设：

N是1.300,000范围内的整数； 字符串S仅由小写字母(A)组成.

复杂性：

最坏情况下的时间复杂度为O(N)；

最坏情况下的空间复杂度是O(N) (不包括输入参数所需的存储)。

以下是我失败的结果：

easy_morphism a -> a?a 2.150 s.超时运行时间：>2.15秒.large_random_string循环+随机字符串1.180 s.超时运行时间：>1.18秒. large_cyclic大循环测试2.170 s.超时运行时间：>2.17秒. single_letter_with_some_tweaks 2.170 s.超时运行时间：>2.17秒. same_small_pattern_with_small_tweaks 2.160 s.超时运行时间：>2.16秒. same_big_pattern_with_small_tweaks 4.660 s.超时运行时间：>4.66秒. small_pattern_with_tweaks_in_one_place 4.700 s.超时运行时间：>4.70秒.

任何帮助或暗示都会很方便！

public class test {

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        System.out.println("solution: " + solution("abababa"));
        long endTime = System.nanoTime();

        long duration = endTime - startTime;
        System.out.println("duration: " + duration/1000000.0 + " seconds");
    }

    public static int solution(String S) {
        int solution = 0, N = S.length();
        String P;
        for (int K = 1; K <= N; K++) {
            P = S.substring(0, K);

            int T = calculateT(P, S);

            int tmpSolution = K * T;
            if (tmpSolution > solution) {
                solution = tmpSolution;
            }
        }

        return solution;
    }

    public static int calculateT(String P, String S) {
        int T = 0, indexOfStart = 0;

        while (indexOfStart > -1) {
            T++;
            indexOfStart = S.indexOf(P, indexOfStart+1);
        }

        return T;
    }
}

Answer 1

经过一番探索，我终于找到了几个解决方案。谢谢您的建议，@ for 5分钟。

我还推荐阅读Z-算法：http://codeforces.com/blog/entry/3107

还有KMP算法：algorithm

我认为我需要学习的与效率有关的主要事情不是嵌套循环。如果代码进入一个循环，然后进入另一个循环，那么它突然消耗了更多的时间，并且在扩展方面变得效率低下。

我需要开始思考我的算法的方式是，可以遍历一些东西几次，以获得最终的结果。这样做比在循环中嵌套循环要好得多。