在O（1）中用Java反转一个字符串？ [英] Reverse a string in Java, in O(1)?

问题描述

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

Is there any facility in the standard Java libraries that, given a CharSequence, produces the reverse in O(1) time?

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

I guess this is "easy" to implement, just wondering whether it already exists. (I suspect the reason this is not offered is because the "easy" way would actually break multi-char code-points - but in many cases we know we are not dealing with those).

谢谢

更新
嘿，大多数人认为这个不可能，好工作的家伙有点有趣！好吧，实际上它（概念上）是微不足道的 - 伪随之而来是明确的：

Update Heh, it's a bit amusing that most thought this "impossible", good work guys! Well, actually it is (conceptually) trivial - pseudojava follows to make it clear:

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的解决方案）并且有人知道它。 （同样，由于那些令人讨厌的代码点，这种情况极不可能）。

I'm leaving the question open for some more, just in the rare event that something like the obvious solution (e.g. see Jon Skeet's one) already exists in the JDK and someone knows about it. (Again, highly unlikely due to those nasty code points).

编辑可能混淆来自于我在标题中有字符串（但不是String！），而我只要求CharSequence的反向。如果你感到困惑，抱歉。我希望O（1）部分能够清楚地说明要求的内容。

Edit Probably the confusion came from me having "string" in the title (but not String!), whereas I only ask for "the reverse of a CharSequence". If you were confused, sorry. I would have hoped the O(1) part would make exactly clear what was being asked for.

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

And by the way, this was the question that made me ask this one. (That's a case where it would be easier to run a regex from right-to-left, not left-to-right, so there may be some practical value even for the simple/broken-codepoints implementation)

推荐答案

好吧，你可以很容易地生成 CharSequence 的实现，返回相同的长度，当要求特定字符返回 length-index-1 中的字符。 toString（）当然是O（n）...

Well, you can easily produce an implementation of CharSequence which returns the same length, and when asked for a particular character returns the one at length-index-1. toString() becomes O(n) of course...

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

Creating that reversed CharSequence would be O(1) - all it's got to do is store a reference to the original CharSequence, after all. Iterating over all the characters within the sequence is going to be O(n) though, obviously.

注意创建反转的 CharSequence （根据您的问题正文）不与创建反向字符串相同（根据标题你的问题）。实际上生成字符串是O（n），必须是。

Note that creating a reversed CharSequence (as per the body of your question) is not the same as creating a reversed String (as per the title of your question). Actually producing the String is O(n), and has to be.

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

Sample code, mostly untested:

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（1）中用Java反转一个字符串？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！