Блог

Я написал решение для вопроса о циклическом сдвиге на 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));
            }
        }


    }
}

 

Я попробовал быстрый ввод-вывод, это не помогло.

Пожалуйста, дайте мне оптимизированное решение.

Как и предполагал марака. Следующее решение действительно принимается.

 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));
            }
        }


    }
}

 

Строки неизменяемы в 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;
}