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

Question

Прорабатывая некоторые проблемы с собеседованием на программировании, которые я обнаружил в Интернете, мне пришлось написать алгоритм, чтобы обратить константный символ * и вернуть указатель на новый символ *. Я думаю, что у меня есть, но чтобы заставить его работать должным образом, я должен был сделать что-то непонятное - по сути, сам должен учитывать ноль-завершающий характер. Почему-то я чувствую, что это неправильно, но я в тупике, и мне было интересно, может ли кто-нибудь мне помочь:

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

  for(int 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(int argc, char * argv[])
{

  char * rev_str = reverse("Testing");

  cout << "Your string reversed is this: " << rev_str << endl;

  delete rev_str;
  rev_str = 0;

  return 0;
}

Answer 1

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

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

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

Answer 2

Задавая этот вопрос в качестве интервьюера, я ищу чистое, понятное решение и могу спросить, как сделать первоначальное решение более эффективным. Меня не интересуют «умные» решения.

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

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

Answer 3

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

Answer 4

.

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;

}

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

Answer 5

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

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

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

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

Answer 6

Метод, который не требует временных переменных

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

Answer 7

Строка перевернута на месте, без временной переменной

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

Answer 8

Я бы решил это примерно так (хотя мой 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;
}

Answer 9

это хорошо работает:

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

Answer 10

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

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

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