Перестановка слов предложения в C++

Объяснение 4 различных методов, которые не являются единственным способом сделать это.

Таким образом, перестановка слов в данном предложении — популярный вопрос в более свежих интервью, и я виноват в том, что не смог сделать это во время моего самого первого интервью. Поскольку я выбрал C++ в качестве объектно-ориентированного языка, на котором должен был проводить собеседование, меня попросили реализовать все вышеперечисленное на C++. Честно говоря, я думал, что меня попросили перевернуть данную строку, например, для строки "CPP is awesome" ответ будет "gnizama si PPC". Объясняя мой подход, интервьюер понял, что я не обратил внимания на вопрос, и использовал приведенный выше пример и сказал, что правильный ответ был "удивительно - это CPP". Так что на случай, если вы не поняли моего объяснения проблемы и не хотите связываться со мной, я надеюсь, что вы усвоили небольшой урок из моего опыта. Внимательно слушайте, какой вопрос задают в интервью, и если вы не поняли его с первого раза, попросите повторить.

Первый подход:-

Итак, при правильном понимании этого вопроса, я полагаю, вы можете иметь в виду подход. Моя заключалась в том, чтобы хранить слова в массиве, а затем распечатывать их в обратном порядке. Символы пробела будут разделять слова, и как только вы подсчитаете количество слов, вы сможете создать массив строк необходимого размера. Просто, верно? Что ж, давайте посмотрим на код, делающий именно это.

Алгоритм выглядит так: -

1. Получить нужную строку от пользователя. Я использовал функцию getline, так как она принимает строку с пробелами. (строки 14–17)
2. Затем мы анализируем данное предложение и считаем нет. слов, основанных на пробелах, так что слово считается только тогда, когда после него встречается пробел. Я предполагаю, что после последнего слова не будет пробела, поэтому я увеличил счетчик один раз после завершения цикла. В случае, если пробел является последним символом в предложении, мы должны его игнорировать. (строки 19–24)
3. Теперь, когда мы знаем нет. слов, мы можем создать массив строк и хранить слова по отдельности в каждом индексе массива. Память выделяется во время выполнения в зависимости от длины предложения, заданного пользователем. Я использовал класс stringstream, который представляет собой буфер, в котором строки хранятся одна за другой. Создавая объект stringstream «ss» и инициализируя его заданным предложением, конструктор последовательно сохраняет слова, удаляя символы пробела. (строки 26–28)
4. Разделенные слова сохраняются в ранее созданном массиве строк из объекта stringstream ‘ss’. (строки 30–32)
5. Наконец, сохраненные слова печатаются в обратном порядке. Мы начинаем с последней позиции индекса к первой и вводим символы пробела между ними. (строки 34–36)

Что ж, мы получили желаемый результат, но, честно говоря, я увидел, что есть много возможностей для улучшения, и внес следующие изменения.

Улучшенная версия: -

По возможности лучше избегать выделения памяти во время выполнения. Хотя код, написанный в first_appreach.cpp, будет работать, его строка №. 21 будет отображаться как проблема в Visual Studio Code IDE. Таким образом, мы заменим массив строк новой строкой. Кроме того, вместо того, чтобы сохранять слова в массиве и затем обращаться к ним в обратном порядке, мы можем хранить слова в самой строке в обратном порядке и просто печатать их. Давайте посмотрим на код, реализующий это.

Код такой же, как и в first_approach.cpp до строки №. 24. Изменения в улучшенной версии:

1. Мы собираемся сохранить результат непосредственно в строке «revSentence» вместо использования массива строк и, таким образом, объявить его. Мы также разделили и сохранили слова предложения в буфере, как это было сделано ранее в файле first_appreach.cpp. (строки 26–27)
2. Используя цикл for, основанный на количестве слов в предложении, мы получаем каждое слово, хранящееся в объекте строкового потока «ss», одно за другим в том же порядке, что и данное предложение. Используя временную строковую переменную word, мы получаем слово из «ss» и вставляем их в начало строки «revSentence». Это делается с помощью функции insert() библиотеки String, где первый параметр указывает позицию вводимой строки, а второй параметр — сама строка. Добавляем пробелы между словами, кроме последнего слова. Если этого не сделать, результирующая строка будет начинаться с пробела, а нам это не нужно. (строки 29–35)
3. Наконец, мы можем напечатать новую строку «revSentence». (строка 37)

Предположим, что вам не нравится использование stringstream и вы хотите увидеть, как мы можем отделить слова от предложения, а также хотите сделать все это в одном цикле, чтобы уменьшить временную сложность. У меня есть для вас другой алгоритм. Имейте в виду, это мой фаворит.

Мой любимый подход: -

Итак, в этом методе перестановки слов предложения я буду использовать только один цикл, а также покажу, как мы можем получить отдельные слова из предложения. В этом подходе используются две функции библиотеки строк: insert() и substr(). Слова берутся из предложения и одновременно добавляются в новую переменную revSentence. Давайте посмотрим, как это сделать.

Этапы этого подхода:

1. Возьмите входное предложение от пользователя
2. Создайте переменную «revSentence» для хранения предложения с перевернутыми словами и инициализируйте переменные «start» и «length» равными 0. Переменная start указывает на начальную позицию слова, а переменная length указывает длину слова.
3. Проходим по предложению буква за буквой, пока не встретим пробел или последний символ предложения, используя цикл for.
4. При встрече с символом пробела переменная длины обновляется до (i-start) и функция substr() используется для получения подстроки слова из предложения. Функция substr() имеет 2 параметра, где первый параметр должен быть индексом, откуда берется подстрока, а второй параметр — длиной этой подстроки. Итак, для первого слова «CPP» символ пробела встречается при i = 3, поэтому длина будет i-start = 3–0 = 3. Слово «CPP» будет скопировано в строковую переменную «word». Начальная переменная будет обновлена ​​до i+1 = 4, чтобы указать, с чего начинается следующее слово. В начале строки «revSentence» сначала будет добавлено «CPP», а затем перед ним добавлен пробел. Эти вышеуказанные шаги будут выполняться до тех пор, пока не перестанут встречаться символы пробела.
5. При просмотре последнего символа переменная длины обновляется до (i-start+1), поскольку значение индекса «i» берется из последнего символа слова, а не из значения после него. В начале не добавляется пробел, так как это не является желаемой характеристикой нашей конечной строки.
6. Теперь мы выводим результирующую строку «revSentence».

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

Волшебный трюк: -

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

Вспомните "gnizama si PPC" из начала этого поста. Что ж, магический трюк как-то связан с этой фразой. Найдите минутку, чтобы понаблюдать и посмотреть, сможете ли вы это понять.

Все, что вам нужно сделать, это поменять местами отдельные слова, и вы получите требуемый ответ, то есть «удивительно — это CPP». Итак, давайте посмотрим на окончательный код, используя этот трюк.

В этом методе все операции выполняются над одной и той же переменной предложения. Последующие шаги можно объяснить следующим образом:

1. Определите функцию, которая переворачивает заданную строку из начальной в конечную точку. Я использовал оператор ссылки «&», чтобы операция обращения строки, выполненная в функции, отражалась в самой данной переменной «предложение». Символьная переменная «temp» используется для выполнения операции подкачки до тех пор, пока не будет достигнут центр начальной и конечной позиций индекса.
2. Возьмите входное предложение от пользователя
3. Вызовите функцию reverseString() для всего предложения, чтобы поменять местами все символы в нем.
4. При анализе предложения вызывайте функцию reverseString() для каждого слова, включая последнее слово.
5. В конце концов, мы можем напечатать перевернутое предложение.

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