提高程序效率

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

嘿！上面的代码工作得很好。然而唯一的问题是运行时间。

这个程序的objective是从"HELLO"构建一个字符串（它最终将具有至少size index的长度）。这是通过将 String 向右旋转 ("HELLO" --> "HELLOOHELL"，并将原始 String 和旋转后的版本连接在一起来完成的。这个过程直到程序正在寻找的索引才会停止在字符串中找到。（所以在这个例子中，经过两次循环后，字符串将变为"HELLOOHELLLHELLOOHEL"）。

你们有没有看到任何可以eliminated/shortened改善运行时间的东西？

Answer 1

我猜你在 buildString 中所做的所有字符串连接都会杀死你。您可以将其缩减为：

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

Answer 2

您需要在不实际构建字符串的情况下计算索引。它旋转了复合字符串的右半部分，左半部分没有。如果你在字符串的左半部分有索引，你可以扔掉右半部分。因此，您简化了情况。如果右半部分有索引，则可以将其转换为左半部分的索引。您只需要撤消右半部分字符串的旋转。所以你将索引向左旋转一个字符。现在你可以减去一半字符串的长度并且你在字符串的左半部分有索引。上面已经描述了这种情况。所以你缩短字符串并从头开始。最后，您得到的是未组成的字符串。它是原始字符串。现在您可以直接使用索引寻址字符，因为它现在在字符串的范围内。

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

提高程序效率

Improving Program Efficiency

java

performance

runtime