Блог

Это вопрос для интервью. Я хотел знать, если вместо ‘a’ мы хотим заменить ‘xyz’, означает ли это, что мы должны создать 2 дополнительных пробела или я могу увеличить размер по этому конкретному индексу? Какова может быть его наиболее эффективная сложность с точки зрения времени выполнения.

Спасибо!

Чтобы сделать это эффективно, вы хотите сканировать вперед по строке, считая ‘a’, затем сканировать назад, копируя символы непосредственно в их правильное конечное положение, вводя ‘xyz ‘ по мере необходимости:

• перемещайте указатель по строке с начала, пока не найдете конец
  • по мере его перемещения подсчитывайте количество символов ‘a
• пока a_count значение не равно 0, переместите указатель назад по строке
  • если указатель не находится на ‘a’, скопируйте символ под указателем на адрес, a_count * 2 символы перед указателем
  • иначе (ваш указатель на ‘a’), скопируйте ‘xyz’ в адрес pointer --a_count * 2

Этот подход заключается в O (N), где N — количество символов в строке.

Сложность будет O(strlen(in)) , оптимизация будет сосредоточена на константе.

Я придумал простую, относительно эффективную реализацию. Обратите внимание, что, поскольку нам сказали создать результат на месте, мы ДОЛЖНЫ предположить, что исходный буфер достаточно велик, чтобы учесть рост.

Собираюсь протестировать его на ideone.

Готово: http://ideone.com/nAgej

Это довольно просто. Требуется всего 2 прохода и равно O (n).

1. Количество # ‘a’ в строке
2. Используя длину исходной строки и # ‘a’, вычислите пределы измененной строки
3. Выполните обратный переход к строке и замените ‘a’ на ‘xyz’

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

 #include <stdio.h>
#include <string.h>

int main() {
    char arr[1024];
    char search='a', *replace="xyz";

    fgets(arr,1023/strlen(replace),stdin);
    if (arr[strlen(arr)-1]=='n')
        arr[strlen(arr)-1]='';
    puts(arr);

    int i, j, k, offset, target;
    for (i=offset=0; i<strlen(arr);   i)
        if (arr[i]==search)
            offset =strlen(replace)-1;

    target = strlen(arr) offset;
    for (i=strlen(arr); i>=0; --i) {
        if (arr[i]!=search)
            arr[target--] = arr[i];
        else {
            target -= strlen(replace);
            strncpy(amp;arr[target 1],replace,strlen(replace));
        }
    }

    puts(arr);

    return 0;
}