Мінімальныя замены, каб зрабіць радкі раўнапраўнымі рашэннем Леткод


Узровень складанасці серада
Часта пытаюцца ў амазонка
Прагны Радок

Пастаноўка праблемы

Вам даюць два радкі s1 і s2 аднолькавай даўжыні, якія складаюцца толькі з літар "х" і "у". вы можаце памяняць любыя два сімвалы, якія належаць да розных радкоў,
ваша задача зрабіць роўнымі абодва радкі. вярнуць мінімальную колькасць свопаў, неабходных для роўнасці абедзвюх радкоў, альбо -1, калі немагчыма зрабіць абедзве радкі роўнымі.

Прыклад

#1

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

#2

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

Падыход (прагны)

Калі мы паглядзім на сімвалы абедзвюх радкоў у нейкім i-м індэксе, мы выявім, што існуе толькі 4 магчымыя пары {s1 [i], s2 [i]}: {"x", "x"}, {"y , "Y"}, {"x", "y"}, {"y", "x"}.
для першых двух тыпаў пар s1 [i] роўна s2 [i] (гэта тое, што мы хочам), колькасць патрэбных свопаў для такіх выпадкаў будзе роўна нулю.

для астатніх пар мы маем s1 [i] не роўна s2 [i], таму нам трэба выкарыстоўваць аперацыі свопу.

мы можам выкарыстаць гэта двума спосабамі:

(i) калі ў нас ёсць пара 3-га (альбо 4-га) тыпу па абодвух індэксах i і j (i не роўна 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, ”Х”}. зараз нам трэба памяняць 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 абедзве няцотныя, мы атрымаем па адной пары з кожнай неўрэгуляванай, таму мы можам выкарыстоўваць аперацыю тыпу (ii), якая патрабуе 2 свопаў для іх урэгулявання.
у адваротным выпадку, калі цотнасць 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

Аналіз складанасці для мінімальных абменаў, каб зрабіць радкі раўнапраўнымі рашэннем Leetcode

Складанасць часу

O (n): Дзе n - даўжыня радка. Паколькі мы ітэрыруем абедзве радкі толькі адзін раз, значыць, складанасць часу будзе O (n).

Касмічная складанасць

O (1): Мы не выкарыстоўваем лішняе месца.