🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1370. Increasing Decreasing String
Сложность: easy
Дана строка s. Переставьте символы строки, используя следующий алгоритм:
Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.
Верните результирующую строку после сортировки s с помощью этого алгоритма.
Пример:
Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.
👨💻 Алгоритм:
1⃣Инициализация и сортировка:
Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result.
2⃣Перебор и добавление символов:
Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре.
3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.
😎 Решение:
#include
#include
class Solution {
public:
std::string sortString(std::string s) {
std::vector charCount(26, 0);
for (char c : s) {
charCount[c - 'a']++;
}
std::string result;
while (result.size() < s.size()) {
for (char c = 'a'; c 0) {
result += c;
charCount[c - 'a']--;
}
}
for (char c = 'z'; c >= 'a'; c--) {
if (charCount[c - 'a'] > 0) {
result += c;
charCount[c - 'a']--;
}
}
}
return result;
}
};
Ставь 👍 и забирай 📚 Базу знаний
