Минимални размени за да ги направите жиците еднакви решенија за лет код  


Ниво на тешкотија Медиум
Често прашувано во Амазон
алгоритми кодирање Алчен интервју интервју подготви LeetCode LeetCodeSolutions Стринг

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

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

пример

#1

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

#2

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

Пристап (алчен)  

Ако ги погледнеме знаците во двата низа на некој ith Индекс, ќе откриеме дека има само 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 [ ј].

Видете исто така
К-ти најмал елемент во подредена матрица

Минимални размени за да ги направите жиците еднакви решенија за лет код

 

(ii) ако имаме 3-ти тип на парови на индексот i и 4-ти тип на парови на некој индекс j (или обратно): {“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].

 

Минимални размени за да ги направите жиците еднакви решенија за лет код

 

како што можеме да видиме операцијата од типот (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

Јава програма за минимални размени за да ги направите жиците еднакви решенија за лет код

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

Анализа на сложеност за минимални размени за да се направат низите еднакво решение на леткод  

Временска комплексност

На) : Каде n е должината на низата. Бидејќи ја повторуваме низата само еднаш, па оттука и сложеноста на времето ќе биде O (n).

Видете исто така
Најдобро време за купување и продавање на акции III решение за лек код

Комплексноста на просторот

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