Минимальные необходимые операции

Question

Я сталкивался с этим в недавнем интервью.

Нам даны два массива целых чисел, и нам нужно проверить, можно ли преобразовать 1-й массив во второй или нет.Единственная разрешенная операция заключается в следующем: выбрать любые 3 соседних элемента из 1-го массива и повернуть их вправо, т.е. {a, b, c} => {c, a, b}.Мы можем применить эту операцию любое количество раз.

Я пробовал с рекурсивным решением, но мне нужен лучший подход.В моем рекурсивном решении я попытался сделать 1-й элемент 2-го массива равным элементу 1-го массива, найдя его ближайшую позицию слева и выполнив необходимое количество операций.Итак, когда 1-й элемент совпадает, я делаю рекурсивный вызов для остальной части массива.т.е. пусть a = {1,2,3,4} и b = {4,1,3,2}.Нам нужно преобразовать массив a в b.Итак, {1,2,3,4} => {1,4,2,3} => {2,1,4,3} => {4,2,1,3} и как [1]= b [1], сделать рекурсивный вызов от 2 до n.

Как решить такую ​​проблему?Заранее спасибо.

Answer 1

Мы можем применить эту операцию любое количество раз.

Но ваш заголовок говорит что-то другое.

Итак, учитывая две строки S1 и S2 размера Nгде количество разных алфавитов в строке одинаково, тогда только мы можем думать о преобразовании.
мы можем сопоставить все символы от 1 до N-2 в обеих строках во всех случаях.Каждый раз, когда мы выбираем символ из первой строки, движение этого символа может быть
-2+1-2+1-2+1..............
Мы можем переместить выбранный символ в эти места обратно в строку
-2,-1,-3,-2,-4,-3....
После сопоставления N-2 символа
Если последние два символа были сопоставлены, то мы преобразовали нашу строку, но они не были автоматически сопоставлены, тогда мы не можем ничего сделать дальше.
Таким образом, проблема заключается в том, что последние два символа мы не можем сделатьчто-нибудь с движением двух персонажей.

Например,
S1 = abdc
S2 = abcd
мы не можем изменить abdc на abcd здесь, потому что из abdc мы можем перейти только к 12 перестановкам из 24:
abdc, dabc, acbd, bdac, dcab, bacd, adcb, bcda, dbca, cbad, cadb, cdba

Оптимально быстрый ответ Подсчет инверсий

В глубине это связано с количеством инверсий в строке
Если инверсии в обеих строках четные или нечетныеru Возможно только преобразование.

Поиск инверсий в строке

int invcount=0,charcount[26]={0};
for(i=0;i<s.size();i++)
{
   for(j=s[i];j<='z';j++)
   invcount+=charcount[j-s[i]];
   charcount[s[i]-'a']++;
}
cout<<invcount;