Жолдарды тең парақ кодының шешіміне теңестіру үшін минималды своптар


Күрделілік дәрежесі орта
Жиі кіреді Amazon
Ашкөздік String

Проблемалық мәлімдеме

Сізге екі беріледі жолдар тек «х» және «у» әріптерінен тұратын бірдей ұзындықтағы s1 және s2. кез-келген екі таңбаны әртүрлі жолдарға ауыстыруға болады,
Сіздің міндетіңіз - жолдың екеуін тең ету. екі жолды тең ету үшін қажет своптардың минималды санын қайтару немесе егер екі жолды тең ету мүмкін болмаса, -1.

мысал

#1

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

#2

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

Тәсіл (ашкөздік)

Егер ith индексіндегі екі жолдағы таңбаларды қарастыратын болсақ, онда тек {s4 [i], s1 [i]} мүмкін болатын 2 жұп бар екенін анықтаймыз: {«x», «x»}, {«y , «Y»}, {«x», «y»}, {«y», «x»}.
s1 [i] жұптарының алғашқы екі типі s2 [i] -ге тең (біз мұны қалаймыз), мұндай жағдайлар үшін своптардың саны нөлге тең болады.

s1 [i] қалған жұптар үшін s2 [i] тең емес, сондықтан своп операцияларын қолдану керек.

біз мұны екі жолмен қолдана аламыз:

(i) егер бізде i және j екі индексінде 3 (немесе 4-ші) типті жұп болса, (s j [-ке] тең емес), егер s1 [i] -ді s2 [j] -ге ауыстырсақ, онда s1 [i] s2-ге тең болады [i] (яғни s [i] = s2 [i])
және s1 [j] s2 [j] -ге тең болады (яғни s1 [j] = s2 [j]), демек, бір жүрісте s1 [i] = s2 [i] және s1 [j] = s2 [жасай алады] j].

Жолдарды тең парақ кодының шешіміне теңестіру үшін минималды своптар

 

(ii) егер i индексінде жұптың үшінші түрі болса және кейбір j индексінде жұптың төртінші түрі болса (немесе керісінше): {«x», «y»}, {«y», «x»}. s3 [i] = s4 [i] және жасау үшін
s1 [j] = s2 [j] екі рет ауыстыру керек, алдымен s1 [i] -ді s2 [i] -мен ауыстыру керек, енді жұптар келесідей болады: {“y”, ”x”}, {“y, ”X”}. енді бізге s1 [i] -ді s2 [j] -мен ауыстыру керек, ал біз аламыз
s1 [i] = s2 [i] және s1 [j] = s2 [j].

 

Жолдарды тең парақ кодының шешіміне теңестіру үшін минималды своптар

 

Көріп отырғанымыздай, (i) типті операция екі индексті есептеу үшін 1 ғана қадам жасайды, сондықтан біз (i) типті амалдарды қолдан келгенше жасауға тырысамыз. біз бәрін оңай санап аламыз
жұп түрлері. {«X», «y»} жұптары = n1, {«y», «x»} жұптары = n2 саны алынады делік.
біз бір свопқа 2 типті 3 жұпты орналастыра аламыз. сондықтан n1 жұпты реттеу керек жалпы своп n1 / 2 болады, егер n1 тақ болса, бір жұп шешілмеген болып қалады.

N2 үшін де. егер n1 және n2 екеуі де тақ болса, біз әрқайсысының шешілмеген бір жұбын аламыз, сондықтан оларды орналастыру үшін 2 свопты қажет ететін (ii) типті операцияны қолдана аламыз.
әйтпесе, егер n1 мен n2 паритеті бірдей болмаса (яғни n1 тақ, ал n2 жұп болса), онда біз шешілмеген бір жұпты аламыз,
бұл жағдайда жолдарды теңестіру мүмкін болмайды.

Іске асыру

Жолдарды тең парақ кодының шешіміне тең ететін минималды своптарға арналған C ++ бағдарламасы

#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

Жолдарды тең парақ кодын шешу үшін минималды своптарға арналған Java бағдарламасы

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

Жолдарды тең парақ кодының шешіміне тең ету үшін минималды своптардың күрделілігін талдау

Уақыттың күрделілігі

O (n): Мұндағы n - жолдың ұзындығы. Екі жолды да бір рет қайталайтын болғандықтан, уақыттың күрделілігі O (n) болады.

Ғарыштың күрделілігі

O (1): Біз артық орынды қолданбаймыз.