Это единственная проблема повышенной сложности в разделе Жадные алгоритмы набора задач для подготовки к собеседованию Hackerrank. Ссылка здесь.
Эта проблема была сложной, и ей пришлось прибегать к помощи других пользователей. Хочу поделиться своими мыслями.
Проблема заключается в том, что вам дана строка s, которая является результатом следующих операций над некоторой строкой A. s = merge(reverse(A) ), shuffle(A))
Операции определяются следующим образом:
- Слияние (A, B): объединяет две строки в одну, сохраняя при этом относительный порядок символов каждой строки.
- Реверс (A): переворачивает струну A.
- Перемешать (A): перемешивает символы A или оставляет их нетронутыми.
Нам нужно найти лексикографически наименьший A. Это означает, что A с наименьшим алфавитным порядком.
Решение
Ключ к этому в том, что, поскольку Merge сохраняет относительный порядок обеих строк. Наша строка A спрятана между повторяющимися символами в обратном порядке.
Псевдокод
- Для начала нам нужно подсчитать появление символов.
- Затем мы делаем копии вхождений, называя их пригодными для использования символами.
- Затем мы половину вхождений и называем это нужными символами
- Затем мы производим пустой счет для нашего решения.
- И пустая строка для нашего решения
- Справа налево в строке
s - - Если персонаж требуется
- - - мы отступаем, если можем, и улучшаем наше решение
- - - добавляем иероглиф в раствор
- - - добавляем к количеству решений
- - - уменьшаем количество полезного использования
- - еще
- - - мы игнорируем и сокращаем количество используемых
- вернуть наше решение
Он должен следовать этой логике:
s=eggegg
we iterate s right to left
- G is required We add G Sol:{g_0}
- G is required We add G Sol:{g_0, g_1}
- E is required We add E Sol:{e_0}
- we backtrack pop g_1, pop g_0
- G is required We add G Sol:{e_0, g_1}
- G is required We add G Sol:{e_0, g_1, g_2}
- E is not required Sol:{e_0, g_1, g_2}
return Sol
Труднее всего знать, когда и сколько раз мы возвращаемся. Вот где полезно вести подсчет решения и используемых символов. Счетчик решения - это то, сколько символов будет в нашем решении. Подсчет используемых символов - это то, сколько символов можно использовать. Перед возвратом мы задаемся вопросом: смогу ли я создать требуемые символы, если уменьшу количество имеющихся у меня на единицу с учетом того, что осталось увидеть. Например, когда в примере мы вернулись к E. У нас было 2 g в решении, но мы еще не увидели 2 g, а требуемые g равны 2., поэтому мы спрашиваем.
Будет ли у меня 2 g минус один, который я собираюсь игнорировать, плюс те, которые я еще не видел, позволят мне сделать требуемые 2 g? Мы задаем один и тот же вопрос каждый раз, когда рассматриваем возможность возврата.
Как правило, мы возвращаемся назад, пока следующий символ лучше, чем последний выбранный, и мы сможем компенсировать проигнорированный символ.
Код
static int wrd_count[26]={};
static int rem_count[26]={};
static int sol_count[26]={};
static char sol[10001];
string reverseShuffleMerge(string s){
int n = s.size();
int j = 0;
const char* s_chars = s.c_str();
for(int i = 0; i < n ; i++)
wrd_count[s[i]-'a']++;
memcpy(rem_count, wrd_count,26*(sizeof(int)) );
for(int i = 0; i < 26 ; i++)
wrd_count[i]/=2;
char l_char;
int l_char_indx;
for(int i = n-1; i >= 0; i--){
l_char = s_chars[i];
l_char_indx = l_char - 'a';
if(i == n-1){
sol[j] = l_char;
j++;
rem_count[l_char_indx]--;
sol_count[l_char_indx]++;
continue;
}
if(sol_count[ l_char_indx ] < wrd_count[l_char_indx]){
if( l_char >= sol[j-1] ){
sol[j] = l_char;
j++;
rem_count[l_char_indx]--;
sol_count[l_char_indx]++;
}else{
while( j>0 && (l_char < sol[j-1]) && sol_count[sol[j-1]-'a']-1+ rem_count[sol[j-1]-'a'] >= (wrd_count[sol[j-1]-'a'])){
sol_count[sol[--j]-'a']--;
}
sol[j] = l_char;
j++;
rem_count[l_char_indx]--;
sol_count[l_char_indx]++;
}
}else{
rem_count[l_char_indx]--;
}
}
sol[j] = '\0';
string sol_str(sol);
return sol_str;
}
