Перевернуть строку в Java, в O (1)?

Question

Есть ли в стандартных библиотеках Java какая-либо возможность, которая при наличии CharSequence производит обратное за O (1) время?

Полагаю, это "легко" реализовать, просто интересно, существует ли оно уже. (Я подозреваю, что причина, по которой это не предлагается, заключается в том, что «легкий» способ фактически сломал бы кодовые точки с несколькими символами - но во многих случаях мы знаем, что мы не имеем дело с ними). ​​

Спасибо

Обновление Хех, немного забавно, что большинство считает это «невозможным», хорошая работа, ребята! Ну, на самом деле это (концептуально) тривиально - псевдоява следует, чтобы прояснить:

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, и кто-то знает об этом. (Опять же, крайне маловероятно из-за этих неприятных кодов).

Редактировать Вероятно, путаница возникла из-за того, что в заголовке есть "строка" (но не строка!), Тогда как я прошу только "обратную последовательность CharSequence". Если вы были смущены, извините. Я надеялся, что часть O (1) точно прояснит, о чем идет речь.

И, кстати, этот вопрос заставил меня задать этот вопрос . (Это тот случай, когда было бы проще запустить регулярное выражение справа налево, а не слева направо, поэтому может быть какое-то практическое значение даже для реализации простых / неработающих кодовых точек)

Answer 1

Что ж, вы можете легко создать реализацию CharSequence, которая возвращает ту же длину, а при запросе конкретного символа возвращает символ в length-index-1.toString() становится O (n), конечно ...

Создание с обратным CharSequence будет O (1) - все, что нужно сделать, это сохранить ссылку на оригиналCharSequence, в конце концов.Итерирование по всем символам в последовательности будет O (n), хотя, очевидно.

Обратите внимание, что создание обратного CharSequence (согласно тексту вашего вопроса) - это , а не то же самое, что создание обратного String (согласно заголовку вашего вопроса).На самом деле для создания 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();
    }
}

Answer 2

Это невозможно.Чтобы перевернуть строку, вы должны обработать каждый символ хотя бы один раз, таким образом, он должен быть не менее O(n).

Answer 3

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

В зависимости от того, что вы понимаете под O (1), это кажется невозможным, поскольку даже для чтения строки один раз требуется O (n), где n - количество символов в строке.

Answer 4

StringBuffer имеет обратную сторону: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/StringBuffer.html#reverse()

Кстати, я предполагаю, что вы имели в виду O (n), потому что O (1) (как уже упоминали другие), очевидно, невозможно.

Answer 5

Как уже написали все остальные, это невозможно за O (1) раз, так как вам нужно хотя бы раз взглянуть на каждый символ.

Но если вы имели в виду, как сделать это в пространстве O (1), вот оно: если вы хотите сделать это в пространстве O (1), вы, очевидно, не можете выделить новую строку такой же длины, но у вас есть поменять местами символы.

Таким образом, все, что вам нужно сделать, это выполнить итерацию слева до середины строки и одновременно справа налево и по центру и поменять местами элементы. Псевдокод (условные обозначения: пусть строка s будет доступна для n -го символа через 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).

Answer 6

// упорно трудились, чтобы понять это

1002 *

Answer 7

Здесь у меня есть образец того же самого, используя метод подстроки и 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);
}

Это может помочь вам. Скажи мне, если я не прав !!

Answer 8

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

Answer 9

Еще лучше использовать StringBuilder для реверса, который является несинхронизированной версией StringBuffer.

Answer 10

Решение Джона Скита, вероятно, наиболее эффективно.Но если вы просто хотите быстро и грязно, это должно быть сделано, и я не думаю, что это будет сильно отставать в производительности.

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

StringBuffer - это CharSequence, так что, если вы намекаете, чторезультат должен быть CharSequence, это.

Ну, это может быть быстрее, чем решение г-на Скита, если вы проверяете последовательность несколько раз, так как это устраняет накладные расходы на вычисления, чтобы каждый раз находить правильную позицию символаВы читаете персонаж.Он собирается делать это только один раз для каждого персонажа.

Если бы я собирался сделать миллиард из них, возможно, я бы сделал тест.