Подтвердить что ты не робот

Обратить строку в Java, в O (1)?

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

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

Спасибо

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 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();
    }
}

Ответ 2

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

Ответ 3

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

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

Ответ 5

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

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

Итак, все, что вам нужно сделать, это перебрать слева направо на середину строки и одновременно с правой на середину и заменить элементы. Pseudocode (Conventions: пусть строка s доступна на n -ом символе через s[n]. Если s имеет длину k, мы говорим, что она имеет элементы 0 to 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, содержащая текущий char для ее замены, поэтому вы можете сделать это в O (1) пространстве.

Ответ 6

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

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

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

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

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

Ответ 10

//много работал, чтобы понять это.

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