java a(n^2)时间复杂度a(n^2)时间复杂度O(n^2)

izkcnapc 于 2023-02-15 发布在 Java

关注(0)|答案(2)|浏览(157)

代码的功能是在任何索引找到回文子串.代码运行良好并且没有错误，但是主要问题是它花费的时间比它指定的多.我尝试了每一个可能的动作但是不能得到期望的执行时间

String palindrome(String s) throws Exception  {

        int x =0,y=0;
        
        int max=0;
      

        for (int i = 0,k=1; i < str.length() && k<=str.length();k++) {
                String s = str.substring(i,k);

                
                StringBuilder sb = new StringBuilder(s);
                sb.reverse();
                String reverse = sb.toString();

                if (s.equals(reverse)) {

                    if (s.length() > max) {

                        max = s.length();
                        x = i;
                    y = k;
                    }

                }

            if (k==str.length()) {
                ++i;
                k=i;
            }


            }

        return str.substring(x,y);
}

代码的功能是在任何索引找到回文子串.代码运行良好并且没有错误，但是主要问题是它花费的时间比它指定的多.我尝试了每一个可能的动作但是不能得到期望的执行时间

Java

来源：https://stackoverflow.com/questions/75424865/having-problem-on-a-code-it-took-time-more-than-it-required-on2-how-to-r

2条答案

按热度按时间

hgb9j2n61#

你可以通过记住小问题的解决方案来减少运行时间。我没有现成的Java代码给你，但我会给予你一个你可以使用的Python算法的大纲。把这个代码转换成Java是很简单的。

dp[i][j] = true if s[i:j+1] is a palindrome.
// Start from the end and decrement, since dp[start + 1]  must be known in order to calculate dp[start].
// Similarly, end is incremented since end - 1 must be known in order to calculate dp[start][end].
for start in range(n - 1, -1, -1):
    for end in range(start + 1, n):
        if s[start] == s[end]:
            palindrome_len = end - start + 1
            // Either it’s a 2-character palindrome or the remaining string is a palindrome.
            dp[start][end] = palindrome_len == 2 or dp[start + 1][end - 1]
            if dp[start][end]:
                count += 1

赞(0）回复(0）举报 2023-02-15

vwhgwdsa2#

你使用的是蛮力，这往往有一个时间限制的问题，因为它使用两个循环。如果有非常大的字符串，让我们说（10^6），它将在任何在线比赛或编辑器超时。
还有另一种方法来解决这个问题，你可以使用DP记忆。例如，当你计算（i，j）子串是回文或没有。你可以先计算较小的子串，这样你就知道是否（i-1，j-1）是回文或没有，如果他们是和s.charAt（i）==s.charAt（j）那么（i，j）也将是一个回文。
算法

开始挑选2个尺寸的子串
则使用已经存储的2大小的子串检查3。
直到size超过string的长度。

赞(0）回复(0）举报 2023-02-15

我来回答

java a(n^2)时间复杂度a(n^2)时间复杂度O(n^2)

2条答案

相关问题

热门标签

最新问答