Verbesserung der Programm-Effizienz

Question

public class cowcode { 

public static void main(String[] args) { 

    long index = 1000000 
    String line = HELLO 

    boolean found = false; 
    if (index <= line.length()) 
     found = true; 

    while (!found) { 
     line += buildString(line); 
     if (index <= line.length()) 
      found = true; 
    } 

    if (found) 
     System.out.println("" + charAt(line, index-1)); 
} 

public static String buildString(String str){ 
    String temp = "" + str.charAt(str.length()-1); 

    for (int i = 0; i < str.length()-1; i ++){ 
     temp += str.charAt(i); 
    } 
    return temp; 
} 

public static String charAt(String line, long index){ 
    for (int i = 0; i < line.length(); i ++){ 
     if (i == index) 
      return line.charAt(i) + ""; 
    } 
    return ""; 
} 
} 

Hey! Der obige Code funktioniert einwandfrei. Das einzige Problem ist jedoch die Laufzeit.

Das Ziel dieses Programms ist es, eine Zeichenkette aus "HELLO" zu erstellen (die schließlich mindestens die Länge eines Größenindex haben wird). Dies geschieht, indem Sie den String nach rechts drehen ("HELLO" -> "HELLOOHELL") und den ursprünglichen String und die gedrehte Version miteinander verketten. Dieser Prozess wird nicht gestoppt, bis der Index, nach dem das Programm sucht, im String. (so in diesem Beispiel wird der String werden „HELLOOHELLLHELLOOHEL“ nach zweimal durch die Schleife zu gehen).

Haben Sie Jungs nichts sehen, die beseitigt werden könnte/verkürzte Laufzeit zu verbessern?

Answer 1

Sie müssen den Index berechnen, ohne die Zeichenfolge tatsächlich zu erstellen. Die rechte Hälfte der zusammengesetzten Saite wurde gedreht, die linke nicht. Wenn Sie einen Index in der linken Hälfte der Zeichenfolge haben, können Sie einfach die rechte Hälfte wegwerfen. Daher vereinfachtest du die Situation. Wenn Sie einen Index in der rechten Hälfte haben, können Sie ihn in der linken Hälfte in einen Index umwandeln. Sie müssen nur die Drehung der Saite in der rechten Hälfte rückgängig machen. So drehen Sie den Index um ein Zeichen nach links. Jetzt können Sie die Hälfte der Zeichenfolge subtrahieren und Sie haben Index in der linken Hälfte der Zeichenfolge. Diese Situation ist bereits oben beschrieben. Also verkürzst du die Saite und fängst wieder am Anfang an. Am Ende enden Sie mit der Zeichenfolge, die nicht zusammengesetzt ist. Es ist die ursprüngliche Zeichenfolge. Jetzt können Sie die Zeichen direkt mit dem Index adressieren, da er sich jetzt im Bereich der Zeichenfolge befindet.

index = 1000000 - 1; 
line = "HELLO"; 
int len = line.length(); 
long len2 = len; 
while (len2 <= index) { 
    len2 *= 2; 
} 
while (len2 > len) { 
    long lenhalf = len2/2; 
    if (index >= lenhalf) { 
     index -= lenhalf; 
     index -= 1; 
     if (index < 0) { 
      index += lenhalf; 
     } 
    } 
    len2 = lenhalf; 
} 

System.out.println(line.charAt((int)index)); 

Answer 2

Was ich denke, ist töten Sie ist all die String Verkettungen Sie in buildString tun sind, können Sie es schneiden diese nach unten.

public static String buildString(String str){ 
    return str.charAt(str.length()-1) + str.substring(0, str.length()-1); 
}