Самый быстрый способ вставить символ в начало строки на С++?
Итак, решая задачи на Leetcode, я столкнулся с этой проблемой. Чтобы нормально сгенерировать строку, я мог бы просто использовать str.push_back('a'). Но если я хочу сгенерировать строку в обратном порядке, я бы использовал тот же метод и перевернул строку в конце. Использование str.insert() привело к превышению лимита времени и str='a'+str; как и ожидалось, приведет к превышению предела памяти. Хотел узнать, есть ли простой способ вставить символ в начало строки в C++
И, пожалуйста, не используйте такие сайты для изучения программирования, C++ или информатики, эти сайты не для этого. Инвестируйте в несколько хороших книг по C++ и посещайте курсы информатики. Как только вы освоитесь с несколькими языками и всеми распространенными структурами данных и алгоритмами, вы можете использовать такие сайты как своего рода «кроссворд для программистов».
1. описание + ссылка на литкод задачи. 2. Покажите нам свой код. 3. ознакомьтесь с временной сложностью и O нотацией. 4. Я сомневаюсь, что проблема в том, о чем вы говорите.
ты хочешь add_char("abc",'d') == "dabc" или add_char("abc",'d') == "dcba" ?
Я хочу добавить_char("abc",d) = = "dcba"
И что потом делать add_char("dcba", "e") должен ли быть результат "eabcd"?
@AyushmanSinha. Пожалуйста, не используйте сокращения, такие как MLE, TLE и т. д. Объясните по-английски, что эти сокращения должны означать. Вопреки распространенному мнению, большинство программистов на C++ никогда не слышали об этих аббревиатурах и не посещают эти веб-сайты «конкурентного программирования», где существуют эти аббревиатуры и акронимы.
Ответы 1
Вы уже ответили на свой вопрос, сказав, что реверс. Просто используйте оператор += для добавления, а затем наоборот.
В качестве другого способа сначала поместите элементы в стек, а затем извлеките их, чтобы заполнить строку.
Если он по-прежнему медленный, разделите вывод на небольшие сегменты и конвейеризируйте части реверсирования + добавления, чтобы скрыть задержку, используя несколько потоков. Пока один поток реверсирует сегмент, другой поток может создать другой сегмент. Затем вы объединяете все потоки и объединяете их выходные сегменты, чтобы сделать единый массив символов для преобразования в строку. Если каждый сегмент имеет размер кеша L1, то реверс должен быть быстрым.
Если вы не можете использовать потоки, вы все равно можете выполнять реверсирование внутри регистров sse/avx, у них есть команды перемешивания, которые могут помочь вам использовать параллелизм на уровне инструкций, чтобы скрыть задержку, если только они не медленнее, чем доступ L1.
std::deque<char>, а затем push_front это другой способ.
Вставьте сзади, а затем используйте
std::reverse, чтобы перевернуть его?