java - 为什么我的程序超出了时间限制？

Question

codechef 上有一个名为字符串交换的问题 ( https://www.codechef.com/problems/SSWAP ) 它说我的程序超出了时间限制。那么，我该如何改进我的程序呢？ 这是代码-

import java.io.*
class StringSwap {
    public static void main(String []args) throws IOException {
        BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
        byte t = Byte.parseByte(k.readLine());
        String s;
        int d, l;
        for (int i = 1; i <= t; ++i) {
            s = k.readLine();
            d = Integer.parseInt(k.readLine());
            l = s.length();
            for (int j = d - 1; j < l; ++j) System.out.print(s.charAt(j));
            for (int j = d - 2; j >= 0; --j) System.out.print(s.charAt(j));
            System.out.println("");
        }
    } // end of main
} // end of class

Answer 1

你的问题是你的解决方案的时间复杂度，它是 O(n ^ d)，这很糟糕。

如果分析重复操作的整体效果，可以在常数时间内解决这个问题，即 O(1)。

剧透解决方案:

String tail = str.substring(0, d); String result = str.substring(d - 1) + ((str.length() % d) % 2 == 0 ? new StringBuilder(tail).reverse() : tail);
_{免责声明:代码可能无法编译或无法工作，因为它是在我的手机上插入的(但有合理的机会它会工作)}