Даны 2 строки S и W, составленныеиз прописных латинских букв. Составить программу, проверяющую, можно ли из букв, входящих в S, составить W. Каждую букву S можно использовать только один раз.
Косяк в том что не знаю как сделать чтоб буквы не повторялись
ТАК В БОШКЕ ЕСТЬ ИДЕЯ НО я ненавижу цыкл while
30 июня 2008 в 14:00
Завести массив 256 элементов (index=char) для W и S, занулить его, подсчитать в соответствующем элементе количество символов с кодом=индекс элемента, и смотреть, как бы в массиве для W соответствующие элементы не превысили соответствующие для S. Условие выполнено если — то W из S составить можно.
9 июня 2008 в 8:00
отсортировать и проверить что W\S!=0
итого два вызова std::sort и один вызов std::set_difference – сложность O(n*log n)
если std::sort заменить арифметической сортировкой – сложность O(n)
8 июня 2008 в 7:02
Я вот как то против кода, который сложно понять с первого раза и со второго тоже. Через пол года это будет такой головной болью.
8 июня 2008 в 0:02
по мне тоже проще посчитать все символы. как-нибудь так (не пинать, если ошибки есть. я уже года три не трогал этот язык):
int cnt[26];
for(char *p = s; *p; cnt[*p++ - 'A']++);
for(char *p = w; *p; cnt[*p++ - 'A']–);
for(int i=0; i < 26; i++) if cnt[i] < 0 break;
return i != 26;
возвращает 0, если можно составить W из букв из S.
7 июня 2008 в 21:03
Можно проще.
пусть s_cnt[i] – количество вхождений символа с номером i в S (0<=i<=25).
w_cnt[i] – количество вхождения символа с кодом i в W.
W может быть составлена из символов S с учетом числа вхождений каждого символа <=> для всех i=0..25s_cnt[i] >= w_cnt[i].
Вычисление s_cnt:
1. s_cnt[i] = 0 для всех i=0..25
2. для всех символов строки S (j = 0…m-1)
s_cnt[S[j] -'A']++;
Вычисление w_cnt аналогично.
7 июня 2008 в 21:00
а как узнать что она цыфра может лучше вообще знак удалить
7 июня 2008 в 21:00
можно и удалить
7 июня 2008 в 20:05
w[1] = q
s[1]=w[1]
заменяем s[1] на, допустим, 1
w="qwer"
s="1qqq"
переходим к w[2]=w
s[1] – цифра, не обрабатываем
s[2]!=w[2] и s[3]!=w[2] и s[4]!=w[2] значит нельзя собрать
7 июня 2008 в 20:05
что то простые задачи на ГОС
7 июня 2008 в 20:04
Может так:
Читаешь первый символ w, пытаешся найти его в s, если не находишь – значит нельзя составить, если находишь, то заменяешь его, например, на цифру, и так для всех символов w
7 июня 2008 в 20:04
да но тут косяк есль вот в чем
w="qwer"
s="qqqq"
будет работать правильно
хотя в принципе можно попробовать