java - 我如何针对 CyclicShift 优化此 Java 代码(Hackerearth 问题)？

Question

我已经为 Hackerearth 上的循环移位问题编写了一个解决方案。

您可以在 Hackerearth -> Codemonk -> 数组和字符串 -> 循环移位上找到这个问题。

该解决方案为大型测试用例提供了 TLE。我如何优化这段代码。

Java 似乎不能有效地处理字符串。 Python 中的相同代码被接受。

import java.io.*;
import java.util.*;
class TestClass
{


    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int N; int K;
            N = sc.nextInt();
            K = sc.nextInt();
            String input = sc.next();
            String B = "";
            String inter = input;
            int d = 0;
            int period = -1;
            for(int i = 0; i < N;i++){
                

                if (B.compareTo(inter) < 0){
                    B = inter;
                    d = i;
                    
                }else if (B.compareTo(inter) == 0){
                    period = i - d;
                    break;
                }
                inter = inter.substring(1, inter.length()) + inter.substring(0, 1);
            }
            if(period == -1){
                System.out.println(d + (K - 1L ) * N);
            }else{
                System.out.println(d + ((K - 1L) * period));
            }
        }


    }
}

我尝试了快速 IO，但没有帮助。

请给我优化的解决方案。

按照马拉卡的建议。以下解决方案确实被接受。

import java.io.*;
import java.util.*;
class TestClass
{

    static int compare(LinkedList<Character> A, LinkedList<Character> B){
        Iterator<Character> i = A.iterator();
        Iterator<Character> j = B.iterator();
        if(A.size() == 0){ return -1;}
        while (i.hasNext()) { // we know they have same length
            char c = i.next();
            char d = j.next();
            if (c < d)
                return -1;
            else if (c > d)
                return 1;
        }
        return 0;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int N; int K;
            N = sc.nextInt();
            K = sc.nextInt();
            String input = sc.next();
            LinkedList<Character> B = new LinkedList<>();
            
            int d = 0;
            int period = -1;
            LinkedList<Character> inter = new LinkedList<>();
            for(char c: input.toCharArray()){inter.add(c);}

            for(int i = 0; i < N;i++){
                if (compare(B, inter) < 0){
                    B = new LinkedList<>(inter);
                    d = i;
                    
                }else if (compare(B, inter) == 0){
                    period = i - d;
                    break;
                }
                inter.add(inter.removeFirst());
            }
            if(period == -1){
                System.out.println(d + (K - 1L ) * N);
            }else{
                System.out.println(d + ((K - 1L) * period));
            }
        }


    }
}

Answer 1

Java 中的字符串是不可变的。您可以尝试使用LinkedList:

LinkdedList<Character> inter = new LinkedList<>(Arrays.stream(inter)
    .boxed()
    .collect(Collectors.toList()));

或者:

LinkdedList<Character> inter = new LinkedList<>();
for (char c : input.toCharArray())
    inter.add(c);

然后转变变成:

inter.add(inter.removeFirst());

比较可以如下进行:

private int compare(List<Character> a, List<Character> b) {
    Iterator<Character> i = a.iterator();
    Iterator<Character> j = b.iterator();
    while (i.hasNext()) { // we know they have same length
        char c = i.next();
        char d = j.next();
        if (c < d)
            return -1;
        else if (c > d)
            return 1;
    }
    return 0;
}