可以做些什么来优化给定的代码

Question

给定代码的时间限制必须小于 1.824 秒。下面给定的代码超出了限制。我可以添加或替换什么以使代码得到优化并在时间限制内运行。以下代码通过从字符串中删除“空格”和特殊字符来检查给定的字符串是否为回文。删除特殊字符后，字符串 mus 仅包含字母。 示例： 输入： 2 I am :IronnorI Ma, i Ab?/Ba 输出： 是 是

代码：

public static void main (String[] args) throws IOException

{

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    int T=Integer.parseInt(br.readLine());

    while(T-->0)

    {

        String frog=br.readLine().replaceAll("\\s+","").replaceAll("[^\\w]","");

        String news="";

        char ch;

        for(int i=0;i<frog.length();i++)

        {

            ch=frog.charAt(i);

            news=ch+news;

        }

        if(news.equalsIgnoreCase(frog))

        System.out.println("YES");

        else

        System.out.println("NO");

    }

}

}

Answer 1

这似乎是一项家庭作业，所以我不会为您提供代码，我只会指导您如何改进您的方法。您的方法是相当线性的，您反转字符串，然后将反转字符串与原始字符串进行比较。虽然这是一种正确的做法，但您需要进行太多操作。假设字符串的长度为 N，另一种方法是简单地循环 N/2 次，每次将第 i 个字符与第 N 个字符进行比较。如果有任何字符不匹配，则打印 No 并中断，否则继续比较。如果所有字符都匹配，则打印 yes。Mead 的解决方案实际上与您的相同，尽管它减少了初始过滤操作。