プログラムの効率向上

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！上記のコードは完全にうまく動作します。しかし、唯一の問題はランタイムです。

このプログラムの目的は、 "HELLO"（最終的に少なくともサイズインデックスの長さを持つ）から文字列を作成することです。これは、文字列を右に回転（ "HELLO" - > "HELLOOHELL"）し、元のStringと回転したバージョンを連結して行います。このプロセスは、プログラムが探しているインデックスが文字列。（したがって、この例では、文字列は二回のループを経て「HELLOOHELLLHELLOOHEL」になります）。

あなたたちは、ランタイムを改善するために、短縮/排除することができるものを参照していますか？

Answer 1

実際に文字列を作成せずにインデックスを計算する必要があります。複合文字列の右半分は回転していて、左の文字列は回転していません。文字列の左半分にインデックスがある場合は、右半分を捨てることができます。したがって、あなたは状況を単純化しました。右半分にインデックスがある場合、それを左半分のインデックスに変換することができます。右半分の文字列の回転を元に戻すだけです。したがって、インデックスを1文字左に回転します。今では、文字列の半分の足を引くことができます。文字列の左半分にインデックスがあります。この状況はすでに上で説明した通りです。だから、文字列を短くして最初からやり直してください。結局、あなたは結成されていないストリングで終わります。それは元の文字列です。今すぐ文字列の範囲内にあるように、インデックスを使用して文字を直接指定することができます。

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

私はあると思いますどのようなあなたはbuildStringで行っているストリング連結のすべてです。

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