Саптарды бирдей Leetcode чечимине айлантуу үчүн минималдуу алмашуулар


Кыйынчылык деңгээли орто
Көп суралган Amazon
ач көз аркан

Маселени билдирүү

Сизге экөө берилет саптар "x" жана "y" тамгаларынан турган бирдей узундуктагы s1 жана s2. ар кандай саптарга таандык каалаган эки белгини алмаштыра аласыз,
Сиздин милдетиңиз - бул сапты бирдей кылуу. эки сапты бирдей кылуу үчүн талап кылынган своптордун минималдуу санын же эгерде эки сапты тең кылуу мүмкүн болбосо, -1.

мисал

#1

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

#2

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

Мамиле (ач көз)

Эгерде кээ бир ith индексиндеги эки саптагы белгилерди карай турган болсок, анда болгону {s4 [i], s1 [i]} төрт жуп бар экендигин аныктайбыз: {"x", "x"}, {"y , "Y"}, {"x", "y"}, {"y", "x"}.
s1 [i] жуптарынын алгачкы эки түрү үчүн s2 [i] барабар (биз ушуну каалайбыз), мындай учурларда талап кылынган своптордун саны нөлгө барабар болот.

s1 [i] калган жуптар үчүн s2 [i] барабар эмес, ошондуктан биз своп операцияларын колдонушубуз керек.

биз муну эки жол менен колдонсок болот:

(i) i жана j индекстеринде 3 (же 4) типтеги жуп бар болсо, 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].

Саптарды бирдей Leetcode чечимине айлантуу үчүн минималдуу алмашуулар

 

(ii) эгерде бизде индексте 3-типтеги ж-да кандайдыр бир j индексте 4-түрдөгү жуптар болсо (же тескерисинче): {"x", "y"}, {"y", "x"}. Демек, s1 [i] = s2 [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].

 

Саптарды бирдей Leetcode чечимине айлантуу үчүн минималдуу алмашуулар

 

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

Окшош n2 үчүн. Эгерде n1 жана n2 экөө тең кызыксыз болсо, анда биз ар бир чечилбегенден бирден жуп алабыз, ошондуктан аларды жөнгө салуу үчүн 2 своп талап кылынган (ii) типтеги операцияны колдоно алабыз.
Болбосо, n1 жана n2 паритети бирдей болбосо (б.а. n1 так жана n2 жуп), анда чечилбеген бир жупту алабыз,
анда саптарды бирдей кылуу мүмкүн болбой калат.

ишке ашыруу

Сызыктарды бирдей Leetcode чечимине айлантуу үчүн минималдуу своптор үчүн 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

Саптарды бирдей Leetcode чечими үчүн минималдуу своп үчүн 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): Биз ашыкча орун колдонбой жатабыз.