我如何為CyclicShift優化此Java代碼（Hackerearth問題）？

我在 Hackerearth 上為回圈移位問題撰寫了一個解決方案。

你可以在 Hackerearth -> Codemonk -> Arrays & String -> Cyclic shift 上找到這個問題。

該解決方案為大型測驗用例提供了 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));
            }
        }


    }
}

uj5u.com熱心網友回復：

字串在 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;
}

標籤：爪哇 算法

上一篇：找出一個集合與集合集合中的所有其他集合的相似程度

下一篇：反之亦然編碼值及其變數