Ходил недавно по собеседованиям, наткнулся на интересную задачу. Поменять порядок слов в строке, разделенной пробелами. Например из "one two three four" сделать "four three two one" за линейное время, не используя дополнительную память. В лучших традициях, на собеседовании до решения я не догадался. Хорошая мысль пришла мне уже дома:
#include <iostream> #include <string> void main() { std::string str = "one two three four"; for (size_t i = 0; i < str.length() / 2; ++i) { std::swap(str[i], str[str.length() - i - 1]); } auto inversePartOfString = [](std::string& str, size_t low, size_t high) { for (size_t j = low, k = 0; j < (low + high) / 2; ++j, ++k) { std::swap(str[j], str[high - k - 1]); } }; int lastFound = 0; size_t i = 0; for (; i < str.length(); ++i) { if (str[i] != ' ') { continue; } inversePartOfString(str, lastFound, i); lastFound = i + 1; } inversePartOfString(str, lastFound, i); std::cout << str << std::endl; }