Реверснуть

А слабо по-русски?

Проходишь строку вперёд, каждое найденное слово переставляешь в начало строки. Не забудь корректировать индекс/итератор.

тут два цикла получается все равно

Пример входных данных и ожидаемого результата можно ?

'ABC DZT XVR'
'XVR DZT ABC'

Что, собеседование не прошёл?

да, пацаны на раЁне собеседовали

Откуда два?

собеседование

Собеседование?

тут два цикла получается все равно

Зачем?

а цикл внутри memcpy считается циклом?

тут два цикла получается все равно

Не два, а 1 + количество слов. Не обращай внимания. Условия задачи изначально тупые, очевидно что цикл при переброске слова не считается, т.к. его «не видно».

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

http://stackoverflow.com/a/27960063

не, аноним, не то
без стандартных функций надо

tags: c++

	std::stringstream input("ABC DZT XVR"), output;
	std::list<std::string> words;
	for(std::string word; input >> word; words.push_front(word));
	std::copy(words.begin(), words.end(), std::ostream_iterator<std::string>(output, " "));
	std::cout << output.str() << "\n";

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

а как эти два цикла сделать одним? а сделать переменную cyclenumber и один бесконечный цикл в котором стоит проверка чему равно cyclenumber. если 0 то рубим первый цикл, вместо выхода из него инкрементируем cyclenumber. если 1 рубим второй цикл.

не то, на С надо, без всяких либовских фич

У тебя ведь задача не за один цикл сделать, а за O(N)?

Split, for each reverse, concat.

Например так:

std::string reverseWords(const std::string &input) {   
    std::list<char> result{};
    
    auto insertIt = result.end();
    for (auto i = input.size() ; i > 0; --i) {
        const char c = input[i - 1];
        if (c != ' ') {
            insertIt = result.insert(insertIt, c);
        } else {
            result.push_back(c);
            insertIt = result.end();
        }
    }

    return std::string(result.begin(), result.end());
}

https://wandbox.org/permlink/WtFAymxRti187uAM

Можно конечно сразу использовать std::string вместо std::list, но будет куча копирований/перемещений. (или как в оригинале — std::deque тоже опция)

не то, на С надо,

Какого дідька у тебя с++ в тегах тогда?

не за один цикл сделать, а за O(N)?

Интересно, а как можно сделать больше чем за O(N)?

Интересно, а как можно сделать больше чем за O(N)?

Усложнить алгоритм обычно не проблема.

Если забыть о memcpy-оптимизациях, а просто алгоритмически смотреть на задачу, я пока не увидел варианта «настоящего» O(n), только что-то вроде O(2n).

Если забыть о memcpy-оптимизациях, а просто алгоритмически смотреть на задачу,

Чисто алгоритмически мой вариант O(n). Это если не приводить требования к виду результата (напр. то, что он должен быть std::string), иными словами std::list<char> можно вполне себе распечатать на stdout без использования std::string.

Да, верно, если сделать допущение, что результат не важен.

ЗЫ. Когда я гонял подобные задачки, насколько помню обычно требовалась in-place модификация. Но, какие есть условия и ограничения у ТС, мы можем только догадываться :)

не увидел варианта «настоящего» O(n), только что-то вроде O(2n).

Вообще-то О означает, что время вычисления будет расти не быстрее чем функция в скобках. 2n и n абсолютно одинаковы в этом смысле, т.е. если увеличить размер в 10 раз, время вычислений увеличится тоже в 10 раз, хоть O(2n), хоть O(1000n) - это одно и тоже.

можно вполне себе распечатать на stdout

Это само по себе отдельный цикл. Т.е ещё один O(n).

Ну так я потому и взял в кавычки, не? И тем не менее O(n) отличают от O(Xn), потому что для одного и того же n первое примерно в X раз лучше второго.

Не, ну если распечатывать, то всех: и строку, и список. Как промежуточный вариант кмк вполне на O(n) тянет.

какие есть условия и ограничения у ТС, мы можем только догадываться

Ограничение только одно - код должен до точки совпадать с тем, что в голове у того, кто задал эту задачку. Других ответов на задачи, оторванные от реальности, просто нет.

И тем не менее O(n) отличают от O(Xn)

Отличают O(n) и k*O(n), конечно - 1 вычисление O(n) и k вычислений O(n).

Распечатывать придется в любом случае.

Как промежуточный вариант кмк вполне на O(n) тянет.

Ну так то тут все варианты тянут, если не считать реализацию результата (сборка строки, распечатка и т.д.). Я ж говорю, задача оторвана от реальности, зачем нужен результат не знает даже сам автор. Поэтому и не понятно, нужно ли собирать строку, или просто распечатать, а может список слов потянет сам как результат. Тупняк, а не задача.

"открываешь стек"

пока есть слово на входе
   пихаешь слово на стек

пока стек не пуст 
   выпихиваешь слово из стека в выходную строку

есть конечно вариант из Жемчужин программирования Бентли

1. идёшь по строке и каждое встреченное слово вращаешь

2. твой строка весь вращал.

в этого получаешь то же самое

O(n), только что-то вроде O(2n).

а ведь ты не шутишь

какого из?

за один проход цикла

лунного!

короче лови

один проход по строке «и ни каких разрывов» с помещением в стек границ разрывов в словах, а точнее [) полуоткрытых интервалов.

второй проход извлекая из стека координаты краёв слов их выпихивание в лицо собеседующих тебя.

/кончил

Можно конечно сразу использовать std::string

Не можно.

Условие у тебя работает до:

return std::string(result.begin(), result.end());

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

Ну и эксплуатация не си-строки. С таким условием требуется только определить длину строки, которая получается strchr(), а далее просто копировать в конец, либо с конца.

Но крестовики такие крестовики - ничего кроме тормозящего дерьма родить не могут. Ну бывает - ты не расстраивайся.

Неоптимизированная пятиминутка:

#include <stdio.h>

static int word_count;

int push_back(char *p)
{
        char *prev = p;

        while(*p) {
                if(*p == ' ') {
                        *p++ = '\0';
                        if(*p != '\0') {
                                push_back(p);
                                continue;
                        } else {
                                break;
                        }
                }
                p++;
        }
        if(word_count)
                putchar(' ');
        word_count++;
        printf("%s", prev);
}

int main(int argc, char **argv)
{
        char *p;

        if(argc != 2) {
                fprintf(stderr, "Usage %s string\n", argv[0]);
                return 1;
        }
        push_back(argv[1]);
        if(word_count)
                putchar('\n');
        return 0;
}

Условие у тебя работает до:

И что? Думаешь я не понимаю?

Три абзаца словесного поноса только чтоб показать, что тред не читал. Заодно еще какашками покидать в причастных. Красавчик.