在Java中,在O(1)中反转字符串?

好吧,您可以轻松地生成 CharSequence 它返回相同的长度,当要求特定字符时,返回一个 length-index-1 . toString() 变成O(N)当然…

创建 相反的 字符序列 将是O(1)-它所要做的就是存储对原始文件的引用 字符序列 毕竟。显然,遍历序列中的所有字符将是O(N)。

请注意,创建一个反转的 字符序列 (根据你的问题主体)是 不 与创建反向 String (根据 标题 你的问题)。实际上,生成字符串是o(n),必须是。

样本代码,大部分未测试:

public final class ReverseCharSequence implements CharSequence
{
    private final CharSequence original;

    public ReverseCharSequence(CharSequence original)
    {
        this.original = original;
    }

    public int length()
    {
        return original.length();
    }

    public char charAt(int index)
    {
        return original.charAt(original.length() - index - 1);
    }

    public CharSequence subSequence(int start, int end)
    {
        int originalEnd = original.length() - start;
        int originalStart = original.length() - end;
        return new ReverseCharSequence(
            original.subSequence(originalStart, originalEnd));
    }

    public String toString()
    {
        return new StringBuilder(this).toString();
    }
}

这是不可能的。要反转字符串,必须至少处理每个字符一次,因此,它必须至少是 O(n) .

string result = new StringBuffer(yourString).reverse().toString();

根据您在O(1)下理解的内容,似乎不可能,因为即使是读取字符串也需要O(n),其中n是字符串中的字符数。

StringBuffer具有反转: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/StringBuffer.html#reverse()

顺便说一句,我认为你的意思是O(n),因为O(1)(如其他人所说)显然是不可能的。

其他人是怎么写的,在O(1)时间里是不可能的,因为你至少要看一次每个字符。

但是,如果你想在O(1)空间中完成它,这里是:如果你想在O(1)空间中完成它,显然你不能分配一个相同长度的新字符串,但是你必须在适当的位置交换字符。

所以您所要做的就是从字符串的左到中迭代,同时从右到中迭代,交换元素。伪代码(约定:let string s 可在 n -th字符via s[n] . 如果 S 有长度 k 我们说它有元素 0 到 k-1 ):

for i=0; i<len(s)/2; ++i{
 char tmp = s[i]
 s[i] = s[len(s)-1-i]
 s[len(s)-1-i] = tmp
}

你看,你只需要一个辅助变量 tmp 包含用于交换的当前字符,因此可以在O(1)空间中进行交换。

乔恩·斯基特的解决方案可能是最有效的。但如果你只是想要一个快速和肮脏的,这应该做到,我不认为它会远远落后于性能。

StringBuffer reverse=new StringBuffer(original.toString()).reverse();

StringBuffer是一个CharSequence,所以如果您暗示结果必须是一个CharSequence,这就是。

如果您多次检查序列,这可能比skeet先生的解决方案更快,因为它消除了每次读取字符时查找正确字符位置的计算开销。每个角色只做一次。

如果我要做十亿个,也许我会做一个基准。

最好使用StringBuilder来反转,这是StringBuffer的非同步版本。

for (count = str.length()-1; count >= 0; count--) {
     tempStr = tempStr.concat(Character.toString(origStr.charAt(count)));
}

这里我有一个使用substring方法和o(n)的相同示例。我知道使用子字符串可以保存完整的字符串内存。

for(int i = 0; i < s.length(); i++)    {
    s = s.substring(1, s.length() - i) + s.charAt(0) + s.substring(s.length() - i);
    System.out.println(s);
}

这可能对你有帮助。如果我错了告诉我!!

//努力解决这个问题

public static String ReverseString(String s){
    if (s.length()>0){
        s=s.charAt(s.length()-1)+printString(s.substring(0,s.length()-1));
    }
    return s;
}