Декодирование длины пробега на месте?

Question

Для заданной строки кодированной длины, скажем, «A3B1C2D1E1», декодируйте строку на месте. Ответ для закодированной строки - «AAABCCDE». Предположим, что кодированный массив достаточно велик, чтобы вместить декодированную строку, т. Е. Можно предположить, что размер массива = MAX [length (encodedstirng), length (decodedstring)].

Это не кажется тривиальным, поскольку простое декодирование A3 как «AAA» приведет к перезаписи «B» исходной строки.

Также нельзя предположить, что декодированная строка всегда больше кодированной строки. Например: кодированная строка - «A1B1», декодированная строка - «AB». Есть мысли?

И это всегда будет пара букв и цифр, т. Е. Вас не попросят преобразовать 0515 в 0000055555

Answer 1

Если мы еще не знаем, мы должны сначала просмотреть, сложив цифры, чтобы вычислить длину декодированной строки.

Это всегда будет пара букв и цифр, поэтому вы можете удалить 1 s из строки без путаницы.

A3B1C2D1E1

становится

A3BC2DE

Вот некоторый код на C ++ для удаления 1 s из строки (O (n) сложность).

// remove 1s
int i = 0; // read from here
int j = 0; // write to here
while(i < str.length) {
    assert(j <= i); // optional check
    if(str[i] != '1') {
        str[j] = str[i];
        ++ j;
    }
    ++ i;
}
str.resize(j); // to discard the extra space now that we've got our shorter string

Теперь эта строка гарантированно будет короче или равна той же длине, что и последняя декодированная строка. Мы не можем сделать это заявление об исходной строке, но мы можем сделать это об этой измененной строке.

(Необязательный, тривиальный шаг теперь заключается в замене каждого 2 предыдущей буквой. A3BCCDE, но нам не нужно этого делать).

Теперь мы можем начать работать с конца. Мы уже вычислили длину декодированной строки, и, следовательно, мы точно знаем, где будет последний символ. Мы можем просто скопировать символы из конца нашей короткой строки в их окончательное местоположение.

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

Answer 2

Следующее решение O(n) и на месте. Алгоритм не должен обращаться к памяти, он не должен, и читать, и писать. Я выполнил некоторую отладку, и это похоже на тестовые примеры, которые я давал.

---

Обзор высокого уровня:

• Определите закодированную длину.
• Определите декодированную длину, прочитав все числа и суммировав их.
• Конец буфера равен MAX (декодированная длина, кодированная длина).
• Расшифруйте строку, начиная с конца строки. Запись с конца буфера.
• Поскольку декодированная длина может быть больше кодированной длины, декодированная строка может не начинаться с начала буфера. Если необходимо, исправьте это, переместив строку в начало.

---

int isDigit (char c) {
    return '0' <= c && c <= '9';
}

unsigned int toDigit (char c) {
    return c - '0';
}

unsigned int intLen (char * str) {
    unsigned int n = 0;
    while (isDigit(*str++)) {
        ++n;
    }
    return n;
}

unsigned int forwardParseInt (char ** pStr) {
    unsigned int n = 0;
    char * pChar = *pStr;
    while (isDigit(*pChar)) {
        n = 10 * n + toDigit(*pChar);
        ++pChar;
    }
    *pStr = pChar;
    return n;
}

unsigned int backwardParseInt (char ** pStr, char * beginStr) {
    unsigned int len, n;
    char * pChar = *pStr;
    while (pChar != beginStr && isDigit(*pChar)) {
        --pChar;
    }
    ++pChar;
    len = intLen(pChar);
    n = forwardParseInt(&pChar);
    *pStr = pChar - 1 - len;
    return n;
}

unsigned int encodedSize (char * encoded) {
    int encodedLen = 0;
    while (*encoded++ != '\0') {
        ++encodedLen;
    }
    return encodedLen;
}

unsigned int decodedSize (char * encoded) {
    int decodedLen = 0;
    while (*encoded++ != '\0') {
        decodedLen += forwardParseInt(&encoded);
    }
    return decodedLen;
}

void shift (char * str, int n) {
    do {
        str[n] = *str;
    } while (*str++ != '\0');
}

unsigned int max (unsigned int x, unsigned int y) {
    return x > y ? x : y;
}

void decode (char * encodedBegin) {
    int shiftAmount;
    unsigned int eSize = encodedSize(encodedBegin);
    unsigned int dSize = decodedSize(encodedBegin);
    int writeOverflowed = 0;
    char * read = encodedBegin + eSize - 1;
    char * write = encodedBegin + max(eSize, dSize);
    *write-- = '\0';
    while (read != encodedBegin) {
        unsigned int i;
        unsigned int n = backwardParseInt(&read, encodedBegin);
        char c = *read;
        for (i = 0; i < n; ++i) {
            *write = c;
            if (write != encodedBegin) {
                write--;
            }
            else {
                writeOverflowed = 1;
            }
        }
        if (read != encodedBegin) {
            read--;
        }
    }
    if (!writeOverflowed) {
        write++;
    }
    shiftAmount = encodedBegin - write;
    if (write != encodedBegin) {
        shift(write, shiftAmount);
    }
    return;
}

int main (int argc, char ** argv) {
    //char buff[256] = { "!!!A33B1C2D1E1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" };
    char buff[256] = { "!!!A2B12C1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" };
    //char buff[256] = { "!!!A1B1C1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" };
    char * str = buff + 3;
    //char buff[256] = { "A1B1" };
    //char * str = buff;
    decode(str);
    return 0;
}

Answer 3

Далее следует еще одно решение O (n ^ 2).

Учитывая, что на сложность ответа нет ограничений, это простое решение, похоже, отлично работает.

while ( there is an expandable element ):
    expand that element
    adjust (shift) all of the elements on the right side of the expanded element

Где:

• Размер свободного пространства - это количество пустых элементов в массиве.

• Расширяемый элемент - это элемент, который:

  expanded size - encoded size <= free space size
  

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

Answer 4

Это очень расплывчатый вопрос, хотя это не особенно сложно, если подумать. Как вы говорите, декодирование A3 как AAA и просто запись его на место перезапишут символы B и 1, так почему бы не просто сначала переместить их дальше по массиву?

Например, когда вы прочитали A3, вы знаете, что вам нужно освободить место для одного дополнительного символа, если это было A4, вам понадобится два, и так далее. Для этого вы должны найти конец строки в массиве (сделайте это заранее и сохраните его индекс).

Затем выполните цикл, перемещая персонажей в их новые слоты:

Для начала: A|3|B|1|C|2||||||| Имейте переменную с именем end, хранящую индекс 5, то есть последнюю непустую запись.

Вы прочитали бы в первой паре, используя переменную с именем cursor, чтобы сохранить текущую позицию - поэтому после чтения в A и 3 она будет установлена ​​в 1 (слот с 3 ).

Псевдокод для хода:

var n = array [cursor] - 2; // n = 1, 3 от A3, а затем минус 2, чтобы учесть пару.

для (i = end; i> курсор; i ++) { массив [i + n] = массив [i]; }

Это оставило бы вас с:

A|3|A|3|B|1|C|2|||||

Теперь A уже существует, так что теперь вы хотите написать n + 1 A, начиная с индекса, хранящегося в cursor:

for(i = cursor; i < cursor + n + 1; i++)
{
  array[i] = array[cursor - 1];
}

// increment the cursor afterwards!
cursor += n + 1;

Предоставление:

A|A|A|A|B|1|C|2|||||

Затем вы указываете на начало следующей пары значений, готовых к повторению. Я понимаю, что в этом ответе есть некоторые пробелы, хотя это намеренно, поскольку это вопрос интервью! Например, в крайних случаях, которые вы указали A1B1, вам понадобится другой цикл для перемещения последующих символов назад, а не вперед.