在Java中颠倒字符串，在O(1)中？
在标准的Java库中，有没有什么工具可以在给定CharSequence的情况下，在O(1)时间内产生相反的结果？
我想这很容易实现，只是想知道它是否已经存在。(我怀疑没有提供这个的原因是因为“简单”的方法实际上会破坏多字符代码点-但在许多情况下，我们知道我们不是在处理这些代码点)。
谢谢
更新嘿，这是有点有趣的是，大多数人认为这是“不可能的”，干得好！实际上，它(在概念上)是微不足道的--下面是伪make来说明这一点：
class MyReverseString extends String { //of course I can't extend String!
final String delegate;
MyReverseString(String delegate) { this.delegate = delegate; }
int length() { return delegate.length(); }
int charAt(int i) { return delegate.charAt(delegate.length() - 1 - i); }
}我将这个问题留到更多的时间，只是在极少数情况下，JDK中已经存在类似明显的解决方案(例如，参见Jon Skeet的解决方案)，并且有人知道它。(同样，由于这些令人讨厌的代码点，可能性极低)。
编辑可能是因为我的标题中有"string“(而不是String!)，而我只要求”CharSequence的反向“。如果你感到困惑，很抱歉。我原本希望O(1)部分能够清楚地说明所要求的是什么。
顺便说一下，this was the question that made me ask this one。(在这种情况下，从右到左运行正则表达式会更容易，而不是从左到右，因此即使对于简单/损坏的代码点实现，也可能有一些实用价值)
回答 10
Stack Overflow用户
发布于 2010-06-24 20:33:12
您可以很容易地生成一个返回相同长度的CharSequence实现，当被要求输入特定字符时，返回的是length-index-1中的字符。当然，toString()变成了O(n)。
创建反向CharSequence将是O(1) -毕竟它所要做的就是存储对原始CharSequence的引用。显然，迭代序列中的所有字符将是O(n)。
请注意，创建反向CharSequence (根据问题正文)与创建反向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();
}
}Stack Overflow用户
发布于 2010-06-24 20:33:01
这是不可能的。为了反转一个字符串，您必须至少处理一次每个字符，因此，它必须至少为O(n)。
Stack Overflow用户
发布于 2010-06-24 20:33:10
string result = new StringBuffer(yourString).reverse().toString();根据您在O(1)下的理解，这似乎是不可能的，因为即使读取字符串一次也需要O(n)，其中n是字符串中的字符数。
https://stackoverflow.com/questions/3109914
复制相似问题
腾讯云开发者
