Учитывая последовательность красных и синих шаров, найдите минимальное количество обменов, чтобы объединить цвета

Question

Нам дана строка вида: RBBR, где R - красный, а B - синий.

Нам необходимо найти минимальное количество свопов, необходимое для объединения цветов. В приведенном выше случае ответом будет 1, чтобы получить RRBB или BBRR.

Мне кажется, что алгоритм сортировки частично отсортированного массива был бы здесь полезен, поскольку простая сортировка дает нам число обменов, но нам нужно minimum число обменов.

Есть идеи?

Это, как утверждается, вопрос об интервью Microsoft в соответствии с this .

Answer 1

Сделайте один проход над строкой и посчитайте количество красных (#R) и количество синих (#B). Затем сделайте второй проход, подсчитав количество красных в первых шарах #R (#r) и количество синих шаров в первых шарах #B (#b). Меньшее из (#R - #r) и (#B - #b) будет минимальным количеством необходимых перестановок.

Answer 2

Нам дана строка S, которую мы должны преобразовать в окончательную строку F = R ^ a B ^ b или B ^ b R ^ a. Количество различий между S и F должно быть четным, потому что для каждого неуместного R будет дополнительный неуместный B. Так почему бы не найти минимальное количество различий между S и обоими возможными F и поделить это на 2?

Например, вам дано S = RBRRBRBR, которое следует преобразовать в RRRRRBBB
или же BBBRRRRR

Сравнивая различия между S и F для каждого символа для каждой возможности, для каждой возможной конечной строки есть 4 различия, поэтому независимо от минимального значения - 2 перестановки.

Answer 3

Это не технический ответ, но я посмотрел на это более интуитивно.

RRBBBBR может быть уменьшено до RBR, так как группа R может быть перемещена как один блок.Это означает, что массив на самом деле представляет собой просто N наборов RB.

Единственное, что имеет значение, это количество N наборов блоков RB (включая неполные блоки для последнего).

• RBR -> 1 своп для получения RRB (2 набора блоков RB, RB и R)
• RBRB-> 1 своп для получения RRBB (2 полных набора блоков RB)
• RBRBRB-> 2 свопа, чтобы добраться до RRRBBB (3 полных набора блоков RB)
• RBRBRBRB -> 4 набора RB = 3 свопа

Итак, обобщив это,количество необходимых свопов = N наборов блоков RB (включая неполные блоки) и вычесть 1.

Answer 4

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

Answer 5

Начните с двух индексов одновременно с правого и левого конца строки. Продвигайте левый указатель, пока не найдете R. Продвигайте правый указатель назад, пока не найдете B. Поменяйте их местами. Повторяйте, пока левый индекс не встретится с правым индексом, и посчитайте свопы Затем сделайте то же самое, но посмотрите на B слева и R справа. Минимум - это меньшее из двух значений свопов.

Answer 6

Давайте посмотрим на ваш пример.Вы знаете, что конечное состояние будет RRBB или BBRR.Другими словами, конечное состояние всегда равно nRmB или mBnR, где n - это число R, а m - это число B в вашей строке.Поскольку конечное состояние определено, может быть, какой-то алгоритм поиска пути будет хорошим подходом для этого?Как насчет того, чтобы рассматривать каждый своп как изменение состояния и думать об эвристической функции для приблизительного количества оставшихся свопов, необходимых.Я просто подбрасываю идею, но надеюсь, что это поможет.