У меня есть строка. Мне нужно получить список или массив из всех заглавных букв английского алфавита. И чтобы буквы в списке не повторялись.
К примеру: str = "AvB^Cv(A^B)";
Должен получить: ["A", "B", "C"]
Раз стоит тег c++
, unordered_set
вам в руки! :) Хотя по мне - так проще сканировать строку и отмечать наличие букв в массиве из 26 bool
...
Вот вариант с bitset
:
string str = "csvCFCjgcgbcYcgmCUYGlhKBNJHulGCVcjgfD";
bitset<26> b;
for(auto c: str)
{
if ((c >= 'A') && (c <= 'Z')) b.set(c-'A');
}
vector<char> v;
for(size_t i = 0; i < b.size(); ++i)
{
if (b[i]) v.push_back('A'+i);
}
for(auto c: v)
{
cout << c;
}
Или
unordered_set<char> u;
for(auto c: str)
{
if ((c >= 'A') && (c <= 'Z')) u.insert(c);
}
for(auto c: u)
{
cout << c;
}
Тоже O(n)
в среднем.
Решение в лоб (c++11
):
std::set<char> result;
for (auto &c : str) {
if (tolower(c) != c) {
result.emplace(c);
}
}
bitset
, но просто не уверен, надо посмотреть - какова сложность вставки в unordered_set
. PS - посмотрел, в среднем вставка за O(1), так что тоже O(n)
Используя известные нам факты, что количество символов от 'A'
до 'Z'
меньше размера int
(в битах), а также, что числовые значения кодов этих символов в кодировке ASCII (кстати, и в Unicode тоже) идут подряд, можно написать очень простую программу, в которой целая переменная используется как множество найденных заглавных букв.
Просматриваем заданную строку и если код очередного символа оказывается в диапазоне от 'A'
до 'Z'
, устанавливаем в 1 соответствующий бит в предварительно обнуленной переменной типа int
(искомое множество).
Далее, просматриваем это множество и заносим находящиеся в нем буквы в массив, максимальный размер которого нам также заранее известен.
#include <stdio.h>
#include <stdlib.h>
int
main (int ac, char *av[])
{
char upc['Z' - 'A' + 2], // тут будет результат
*src = av[1] ? av[1]
: (char *)"AaBbcD...XyZ."; // исходная строка по умолчанию
unsigned int set = 0, // временное множество, будет уничтожено при производстве результата
i, // индекс для перебора множества
j; // индекс свободного места в результате (upc[])
for (; *src; src++)
if (*src >= 'A' && *src <= 'Z')
set |= (1 << (*src - 'A')); // это заглавная буква, добавим ее в наше множество
for (i = j = 0; set; i++, set >>= 1) // перебираем множество бит за битом, пока в нем еще что-то есть
if (set & 1)
upc[j++] = i + 'A'; // добавим очередную заглавную букву в результат
upc[j] = 0;
return puts(upc) == EOF;
}
Программку и gcc и g++ воспринимают как свою .
P.S.
Примерно это находится "под капотом" в программе на С++, например, из примера @Harry
UPDATE
Немного подумав над комментарием о том, что это печально, решил предложить вариант, сохраняющий накопленное множество и заодно оставляющий нетронутым указатель на исходные данные.
unsigned int set = 0, i, j;
for (i = j = 0; src[i]; i++)
if (src[i] >= 'A' && src[i] <= 'Z')
if (!(set & (1 << (src[i] - 'A')))) {
set |= (1 << (src[i] - 'A'));
upc[j++] = src[i];
}
upc[j] = 0;
Конечно, теперь заглавные буква выводятся не в алфавитном порядке.
A
до Z
после небольшой трансформации помещаются в int
. Речь о "понимании" компилятором этой трансформации. А вот насколько (и в каких ситуациях) высокоуровневые абстракции уменьшают количество ошибок -- это отдельный вопрос.
c++
. Ваш комментарий как будто бы говорит: С++ компилятор не обладает ... то ли дело C
. Но может быть я Вас неправильно понял. Кстати, хочу заметить, что в условиях 16-bit int, Ваш код потерпит фиаско.
Вариант с функциональным подходом:
#include <string>
#include <set>
#include <algorithm>
#include <cctype>
#include <iterator>
std::string s = "csvCFCjgcgbcYcgmCUYGlhKBNJHulGCVcjgfD";
std::set<char> r;
std::copy_if(begin(s), end(s), inserter(r, begin(r)), isupper);
Прочитал много всего, и в конце решил просто проверять каждый символ строки, str[i] >= 'Z' && str[i] <= 'A'
. И если условие тру, то пушу в сэт. А у него по дефолту свойство не пушить элементы, которые уже есть в нём.
Код в Qt Creator:
std::set<QString> letters;
for (int i = 0; i < str.length(); i++) {
if ((str[i] <= 'Z') && (str[i] >= 'A')) {
letters.insert(QString(str[i]));
}
}