Как Вы улучшили бы этот алгоритм? (реверсирование струны до)

std::reverse от <algorithm> работы для строк и char массивы:

string str = "Hello";
char chx[] = "Hello";

reverse(str.begin(), str.end());
reverse(chx, chx + strlen(chx));

cout << str << endl;
cout << chx << endl;

/ РЕДАКТИРОВАНИЕ: Это, конечно, изменяет исходную строку. Но STL к спасению. Следующее создает новую обратную строку. К сожалению(?), это не работает непосредственно над C char массивы, не создавая дополнительную (неявную) копию:

string reverse_string(string const& old) {
    return string(old.rbegin(), old.rend());
}

cout << reverse_string("Hello") << endl;

Выше для цикла имеет опечатку. Проверка переменной цикла, которой я должен быть <= вместо <иначе не приведет к сбою для нечетного никаких из элементов. для (интервал i = 0; я <= длина/2; ++ i)

.

char * reverse(const char * str)
{
  if (!str)
    return NULL;

  int length = strlen(str);
  char * reversed_string = new char[length+1];

  for(int i = 0; i < length/2; ++i)
  {
    reversed_string[i] = str[(length-1) - i];
    reversed_string[(length-1) - i] = str[i];
  }
  //need to null terminate the string
  reversed_string[length] = '\0';

  return reversed_string;

}

Половина времени, но той же сложности (примечание может быть выключено одной ошибкой),

Метод, для которого не нужны временные переменные

int length = strlen(string);
for(int i = 0; i < length/2; i++) {
  string[i] ^= string[length - i] ^= string[i] ^= string[length - i];
}

Если бы я делал интервьюирование, то я был бы немного более суетливым с качеством решения с точки зрения его устойчивости, не только это - производительность.

Все ответы, отправленные к настоящему времени, приведут к сбою, если передано нулевого указателя - большинство из них прыгает к непосредственному вызову strlen() на возможном нулевом указателе - который будет, вероятно, segfault Ваш процесс.

Многие ответы одержимы производительностью до такой степени, что они пропускают один из ключевых вопросов вопроса: реверс a const char *, т.е. необходимо сделать обратную копию, не обратную оперативной. Вы найдете трудным разделить на два количество повторений, если копия будет требоваться!

Это - вопрос об интервью, таким образом, мы хотим посмотреть на детали алгоритма, но в реальном мире это просто выделяет значение пользования стандартными библиотеками, когда это возможно.

Строка инвертируется на месте, никакая временная переменная.

static inline void
byteswap (char *a, char *b)
{
  *a = *a^*b;
  *b = *a^*b;
  *a = *a^*b;
}

void
reverse (char *string)
{
  char *end = string + strlen(string) - 1;

  while (string < end) {
    byteswap(string++, end--);
  }
}

При задавании этого вопроса как интервьюер я обращаюсь к чистому, понятному решению и могу спросить, как начальное решение могло быть сделано более эффективным. Я не интересуюсь 'умными' решениями.

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

К сожалению, как уже говорилось, слишком много людей не могут даже сделать этого.

Я решил бы его вид подобных это (мой c немного ржав, хотя, простите мне),

char *reverse( const char *source ) {
  int len = strlen( source );
  char *dest = new char[ len + 1 ];
  int i = 0;
  int j = len;
  while( j > 0 ) {
    dest[j--] = src[i++];
  }
  dest[i] = \0;
  return dest;
}

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

Потребовалось бы две передачи и стопка царапины, но я буду, вероятно, доверять мне больше, чтобы заставить это право в первый раз затем не делать не одной ошибкой как вышеупомянутое.

char* stringReverse(const char* sInput)
{
    std::size_t nLen = strlen(sInput);
    std::stack<char> charStack;
    for(std::size_t i = 0; i < nLen; ++i)
    {
        charStack.push(sInput[i]);
    }
    char * result = new char[nLen + 1];
    std::size_t counter = 0;
    while (!charStack.empty())
    {
        result[counter++] = charStack.top();
        charStack.pop();
    }
    result[counter] = '\0';
    return result;
}

WRT: "Теперь сделайте это без временной переменной содержания"... Что-то вроде этого, возможно (и сохраняющий индексацию массива на данный момент):

int length = strlen(string);
for(int i = 0; i < length/2; i++) {
  string[i] ^= string[length - i];
  string[length - i] ^= string[i];
  string[i] ^= string[length - i];
}

это работает приятно:

#include <algorithm>
#include <iostream>
#include <cstring>

void reverse_string(char *str) {    
    char *end = str + strlen(str) - 1;
    while (str < end) {
        std::iter_swap(str++, end--);
    }
}

int main() {
    char s[] = "this is a test";
    reverse_string(s);
    std::cout << "[" << s << "]" << std::endl;
}

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

@Konrad Rudolph: (извините у меня нет "опыта" добавить комментарий),

Я хочу указать, что STL предоставляет reverse_copy () алгоритм, подобный реверсу (). Вы не должны представлять временный файл путем, Вы сделали, просто выделяете новый символ * правильного размера.

if( string[0] )
{
    char *end = string + strlen(string)-1;
    while( start < end )
    {
        char temp = *string;
        *string++ = *end;
        *end-- = temp;
    }
}

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

Это - пример того, как получить его работающий с GCC.

/* 
 * reverse.c
 *
 * $20081020 23:33 fernando DOT miguelez AT gmail DOT com$
 */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_CHARS 10 * 1024 * 1024

/*
 * Borrowed from http://coding.derkeiler.com/Archive/Assembler/comp.lang.asm.x86/2007-03/msg00004.html
 * GNU Compiler syntax
 */
inline uint32_t bswap(uint32_t val)
{
    __asm__("bswap %0" : "=r" (val) : "0" (val));
    return val;
}

char * reverseAsm(const char * str)
{
    int i;
    int length = strlen(str);
    int dwordLength = length/4;

    if(length % 4 != 0)
    {
        printf("Error: Input string length must be multiple of 4: %d\n", length);       
        return NULL;
    }

    char * reversed_string = (char *) malloc(length+1);
    for(i = 0; i < dwordLength; i++)
    {
        *(((uint32_t *) reversed_string) + dwordLength - i - 1) = bswap(*(((uint32_t *) str) + i));
    }

    reversed_string[length] = '\0';

    return reversed_string;
}

char * reverse(const char * str)
{
    int i;
    int length = strlen(str);
    char * reversed_string = (char *) malloc(length+1);

    for(i = 0; i < length; ++i)
    {
        reversed_string[i] = str[(length-1) - i];
    }

        //need to null terminate the string

    reversed_string[length] = '\0';

    return reversed_string;
}

int main(void)
{
    int i;
    char *reversed_str, *reversed_str2;
    clock_t start, total;
    char *str = (char *) malloc(MAX_CHARS+1);

    str[MAX_CHARS] = '\0';

    srand(time(0));

    for(i = 0; i < MAX_CHARS; i++)
    {
        str[i] = 'A' + rand() % 26;     
    }

    start = clock();
    reversed_str = reverse(str);
    total = clock() - start;
    if(reversed_str != NULL)
    {
        printf("Total clock ticks to reverse %d chars with pure C method: %d\n", MAX_CHARS, total); 
        free(reversed_str);
    }
    start = clock();
    reversed_str2 = reverseAsm(str);
    total = clock() - start;
    if(reversed_str2 != NULL)
    {
        printf("Total clock ticks to reverse %d chars with ASM+C method: %d\n", MAX_CHARS, total); 
        free(reversed_str2);
    }

    free(str);

    return 0;
}

Результаты на моем старом компьютере под Cygwin:

fer@fernando /cygdrive/c/tmp$ ./reverse.exe
Total clock ticks to reverse 10485760 chars with pure C method: 221
Total clock ticks to reverse 10485760 chars with ASM+C method: 140

Мм? Никто не сделал это с указателями?

char *reverse(const char *s) {
    size_t n = strlen(s);
    char *dest = new char[n + 1];
    char *d = (dest + n - 1);

    dest[n] = 0;
    while (*s) {
        *d-- = *s++
    }

    return dest;
}

Надо надеяться, годы Java не разрушили мой C ;-)

Править: замененный все те strlen звонит с дополнительным var. Что strlen возвращает в эти дни? (Спасибо постамент).

Ваш код является прямым и неудивительным. Несколько вещей:

1. Используйте size_t вместо интервала для Вашего индекса цикла
2. В то время как Ваш компилятор, скорее всего, достаточно умен, чтобы выяснить, что (длина-1) является инвариантным, вероятно, не достаточно умно выяснить, что (длина 1)-i лучше всего заменяется другой переменной цикла, которая постепенно уменьшается в каждой передаче
3. Я использовал бы указатели вместо синтаксиса массива - это будет выглядеть более чистым мне, чтобы иметь *dst - = *src ++; в цикле.

Другими словами:

char *dst = reversed_string + length;
*dst-- = '\0';
while (*src) {
   *dst-- = *src++;
}

Мы использовали этот вопрос прежде - с удивительно результаты нахождения большого количества людей, которые не могут сделать этого (даже со значительным опытом C/C++!). Я предпочитаю оперативный вариант, так как он сохраняет немного служебные, и имеет добавленное скручивание только необходимости выполнить итерации по strlen (s)/2 символы.

Ваше решение в интервью было бы прекрасно. (Корректный!) решение с помощью указателя вместо синтаксиса массива оценило бы немного выше, так как это показывает больший уровень комфорта с указателями, которые так очень важны в программировании C/C++.

Незначительные критические анализы должны были бы указать, что strlen возвращает size_t не интервал, и необходимо использовать, удаляют [] на rev_str.

У меня был этот вопрос однажды. Это - первый ответ, который приходит на ум, но продолжение, "теперь сделайте это, не выделяя памяти".

int length = strlen(string);
for(int i = 0; i < length/2; i++) {
  char c = string[i];
  string[i] = string[length - i];
  string[length - i] = c;
}

Править: Некоторые люди выразили презрение к тому, что не использовались указатели. Это - крошечный более читаемый бит, хотя не абсолютно оптимальный. Другие ввели решение для указателя, таким образом, я не повторю его здесь.

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

string[i] = string[i] ^ string[length - i];
string[length - i] = string[i] ^ string[length - i];
string[i] = string[i] ^ string[length - i];

Но в целом, современные компиляторы могут оптимизировать локальную переменную наивной подкачки. Для получения дополнительной информации Посмотрите Википедию

Вы не можете (не должны) этого делать:

 string [i] ^ = строка [длина - i] ^ = строка [i] ^ = строка [длина - i];

От: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example

• * "Этот код имеет неопределенное поведение, поскольку он дважды изменяет lvalue x без промежуточной точки последовательности.