在 Java 中反转一个字符串，在 O（1）中？

string java

2022-09-02 05:33:02

在标准 Java 库中，是否有任何工具在给定 CharSequence 的情况下，在 O（1）时间内产生相反的结果？

我想这是“容易”实现的，只是想知道它是否已经存在。（我怀疑没有提供这个的原因是因为“简单”的方法实际上会破坏多字符代码点 - 但在许多情况下，我们知道我们没有处理这些）。

谢谢

更新呵呵，有点好笑的是，大多数人认为这是“不可能的”，干得好的人！好吧，实际上它（概念上）是微不足道的 - 伪java如下以使其清晰：

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

我将这个问题留待更多，只是在极少数情况下，像明显的解决方案（例如，参见Jon Skeet的解决方案）已经存在于JDK中并且有人知道它。（同样，由于那些令人讨厌的代码点，极不可能）。

编辑可能混淆来自我在标题中有“字符串”（但不是字符串！），而我只要求“字符序列的反向”。如果您感到困惑，对不起。我本来希望O（1）部分能够清楚地说明所要求的内容。

顺便说一句，这是让我问这个问题的问题。（在这种情况下，从右到左而不是从左到右运行正则表达式会更容易，因此即使对于简单/断开的代码点实现，也可能有一些实际价值）

答案 1

好吧，您可以轻松生成一个返回相同长度的实现，并且当要求特定字符时，返回位于的实现。当然，变成O（n）...CharSequencelength-index-1toString()

创建反转的将是O（1） - 它所要做的就是存储对原始的引用，毕竟。显然，迭代序列中的所有字符将是O（n）。CharSequenceCharSequence

请注意，创建反向（根据问题的正文）与创建反向（根据问题的标题）不同。实际产生字符串是O（n），并且必须是。CharSequenceString

示例代码，大部分未经测试：

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

答案 2

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

在 Java 中反转一个字符串，在 O（1） 中？

在 Java 中反转一个字符串，在 O（1）中？