Минималне замјене да би се жице изједначиле са рјешењем с кодовима


Ниво тешкоће Средњи
Често питани у амазонка
Похлепан низ

Изјава о проблему

Дато вам је двоје струне с1 и с2 једнаке дужине који се састоје само од слова „к“ и „и“. можете заменити било која два знака која припадају различитим жицама,
ваш задатак је да оба низа изједначите. врати минималан број замена потребан да би се оба низа изједначила или -1 ако је немогуће оба низа изједначити.

Пример

#1

s1 = "xx", s2 = "yy"
1

#2

s1 = "xy", s2 = "yx"
2

Приступ (похлепан)

Ако ликове у обе жице погледамо у неком и-ом индексу, открићемо да постоје само 4 могућа пара {с1 [и], с2 [и]}: {„к“, „к“}, {„и , "И"}, {"к", "и"}, {"и", "к"}.
за прва два типа парова с1 [и] је једнако с2 [и] (то је оно што желимо), број потребних замена за такве случајеве биће нула.

за остатак парова које имамо с1 [и] није једнако с2 [и], па морамо користити свап операције.

ово можемо користити на два начина:

(и) ако имамо пар 3. (или 4.) типа на оба индекса и и ј (и није једнако ј), ако заменимо с1 [и] са с2 [ј], тада ће с1 [и] постати једнако с2 [и] (тј. с [и] = с2 [и])
и с1 [ј] ће постати једнако с2 [ј] (тј. с1 [ј] = с2 [ј]), то значи да у једном потезу може направити с1 [и] = с2 [и] и с1 [ј] = с2 [ ј].

Минималне замјене да би се жице изједначиле са рјешењем с кодовима

 

(ии) ако имамо трећи тип пара код индекса и и четврти тип пара код неког индекса ј (или обрнуто): {„к“, „и“}, {„и“, „к“}. тако да се с3 [и] = с4 [и] и
с1 [ј] = с2 [ј] морамо двапут заменити, прво морамо с1 [и] заменити са с2 [и], сада ће парови изгледати као: {„и“, „к“}, {„и, "Икс"}. сада треба да заменимо с1 [и] са с2 [ј] и добићемо
с1 [и] = с2 [и] и с1 [ј] = с2 [ј].

 

Минималне замјене да би се жице изједначиле са рјешењем с кодовима

 

као што видимо да је за операцију типа (и) потребан само један потез да се измире два индекса, па ћемо покушати да извршимо (и) операције типа колико год можемо. лако можемо добити бројање свих
врсте парова. Рецимо да добијемо број парова {"к", "и"} = н1, број парова {"и", "к"} = н2.
можемо подмирити 2 пара типа 3 у једној замјени. тако да ће укупна замјена која нам треба да подмиримо н1 парова бити н1 / 2, ако је н1 непаран, један пар ће остати несређен.

Слично за н2. ако су н1 и н2 непарни, добићемо по један пар неуређених, тако да можемо да користимо (ии) операцију типа која захтева 2 замене за њихово решавање.
у супротном, ако паритет н1 и н2 није исти (тј. н1 је непаран, а н2 је паран), тада ћемо добити један пар који није измирен,
у том случају биће немогуће изједначити жице.

Имплементација

Ц ++ програм за минималне замјене како би се жице изједначиле са рјешењем Леетцоде

#include<bits/stdc++.h>
using namespace std;
int minimumSwap(string s1, string s2) 
{
    int xy_count=0,//count of {x,y} pairs
    yx_count=0,//count of {y,x} pairs
    n=s1.length();
    for(int i=0;i<n;i++)
    {
        if(s1[i]!=s2[i])
        {
            if(s1[i]=='x') xy_count++;
            else yx_count++;
        }
    }
    if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+(xy_count%2==1);//if parity of count of xy pair and yx pair is same 
    else return -1;
}

int main()
{
    string s1="xxxyy",s2="yyxxx";
    cout<<minimumSwap(s1,s2);
    return 0;
}
2

Јава програм за минималне замјене како би се гудаче изједначиле са рјешењем Леетцоде

class Rextester{
    
      public static int minimumSwap(String s1, String s2) 
      {
         
        int xy_count=0,//count of {x,y} pairs
        yx_count=0,//count of {y,x} pairs
        n=s1.length();
        for(int i=0;i<n;i++)
        {
            if(s1.charAt(i)!=s2.charAt(i))
            {
                if(s1.charAt(i)=='x') xy_count++;
                else yx_count++;
            }
        }

        //if parity of count of xy pair and yx pair is same 
        if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+((xy_count%2==1)?1:0);
        else return -1;
    }
    
    public static void main(String args[])
    {
       	String s1="xxxyy",s2="yyxxx";
        System.out.println(minimumSwap(s1,s2) );
    }
}
2

Анализа сложености за минималне замјене како би се жице изједначиле са рјешењем Леетцоде

Сложеност времена

На) : Где је н дужина низа. Како понављамо оба низа само једном, стога ће временска сложеност бити О (н).

Сложеност простора

О (1): Не користимо никакав додатни простор.