მინიმალური სვოპები, რომ სტრიქონები გახდეს თანაბარი ლეეტკოდ ამოხსნისთვის


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon
ხარბ სიმებიანი

პრობლემის განცხადება

თქვენ გეძლევათ ორი სიმები თანაბარი სიგრძის s1 და s2 შედგება მხოლოდ ასოებისაგან "x" და "y". შეგიძლიათ შეცვალოთ ორი სიმბოლო, რომელიც ეკუთვნის სხვადასხვა სტრიქონს,
თქვენი ამოცანაა ორივე სტრიქონი ტოლი გახადოთ. დავაბრუნოთ სვოპების მინიმალური რაოდენობა, რაც საჭიროა ორივე სტრიქონის ტოლი ან -1, თუ შეუძლებელია ორივე სტრიქონის ტოლობა.

მაგალითი

#1

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

#2

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

მიდგომა (ხარბი)

თუ გადავხედავთ სიმების სიმბოლოებს რომელიმე ინდექსის მიხედვით, აღმოვაჩენთ, რომ არსებობს მხოლოდ 4 შესაძლო წყვილი {s1 [i], s2 [i]}: {“x”, ”x”}, {“y , ”Y”}, {“x”, ”y”}, {“y”, ”x”}.
პირველი ორი ტიპის წყვილი s1 [i] უდრის s2 [i] (ეს არის ის, რაც ჩვენ გვინდა), სვოპების რაოდენობა ნულის ტოლია ასეთი შემთხვევებისთვის.

დანარჩენი წყვილებისთვის, s1 [i] არ არის s2 [i] ტოლი, ამიტომ საჭიროა swap ოპერაციების გამოყენება.

ჩვენ შეგვიძლია ამის გამოყენება ორი გზით:

(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 ტიპის წყვილი ინდექსში და მე –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 ++ პროგრამა მინიმალური გაცვლებისთვის, რომ სიმები ტოლი იყოს Leetcode ამოხსნისთვის

#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 პროგრამა მინიმალური გაცვლებისთვის, რომ სტრიქონები გახდეს თანაბარი Leetcode ამოხსნისთვის

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): ჩვენ დამატებით ადგილს არ ვიყენებთ.