JuniorКодОчень частоЕщё не отвечали
Реализуйте реверс строки
Разверните строку «на месте» (in-place) — измените переданную строку так, чтобы её символы шли в обратном порядке.
Требования:
- O(n) время, O(1) доп. память (меняйте местами к центру; не выделяйте новый буфер).
- Обработайте пустую строку и строку из одного символа.
#include <string>
void reverseString(std::string& s) {
// ваш код здесь
}Допишите реализацию.
Используйте два индекса (или итератора) с обоих концов и меняйте символы местами к центру. O(n) времени, O(1) памяти in-place. std::reverse из <algorithm> делает то же в одну строку.
- ✗Возвращать новую обращённую строку, когда требуется in-place (тратит O(n) памяти)
- ✗Не обрабатывать крайние случаи: пустая строка или строка из одного символа
- ✗Наивный реверс UTF-8 строк — нужно работать с codepoints, а не байтами
- →Как перевернуть слова в предложении, не переворачивая символы внутри каждого слова?
- →Как правильно обратить строку в кодировке UTF-8?
Оглавление
Задача
Реализуйте in-place реверс строки.
Решение
#include <string>
#include <algorithm>
#include <cassert>
// In-place, два указателя — O(n) время, O(1) память
void reverseString(std::string& s) {
int left = 0;
int right = static_cast<int>(s.size()) - 1;
while (left < right) {
std::swap(s[left], s[right]);
++left;
--right;
}
}
// Однострочный вариант через STL
void reverseStringStl(std::string& s) {
std::reverse(s.begin(), s.end());
}
// Возврат нового значения (без изменения оригинала)
std::string reversed(std::string s) { // принимаем по значению
reverseString(s);
return s;
}
int main() {
std::string s = "hello";
reverseString(s);
assert(s == "olleh");
std::string t = "";
reverseString(t);
assert(t == "");
std::string u = "a";
reverseString(u);
assert(u == "a");
assert(reversed("abcde") == "edcba");
}Ключевые моменты
- Два указателя: O(n) время, O(1) память — оптимально.
std::reverse(s.begin(), s.end())— идиоматичное решение на C++.- Для Unicode строк (UTF-8) наивный побайтовый реверс некорректен.
Оглавление
