Swaps ขั้นต่ำเพื่อสร้าง Strings Equal Leetcode Solution


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน
โลภ เชือก

คำชี้แจงปัญหา

คุณจะได้รับสอง เงื่อนไข 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] ดังนั้นเราจึงต้องใช้การดำเนินการสลับ

เราสามารถใช้สิ่งนี้ได้สองวิธี:

(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 [ ญ].

Swaps ขั้นต่ำเพื่อสร้าง Strings Equal Leetcode Solution

 

(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]

 

Swaps ขั้นต่ำเพื่อสร้าง Strings Equal Leetcode Solution

 

ดังที่เราเห็นการดำเนินการประเภท (i) ใช้เวลาเพียง 1 ครั้งในการกำหนดดัชนีสองดัชนีดังนั้นเราจะพยายามทำให้ (i) พิมพ์การดำเนินการให้มากที่สุดเท่าที่จะทำได้ เราสามารถนับทั้งหมดได้อย่างง่ายดาย
ประเภทของคู่ สมมติว่าเราได้จำนวนคู่ {“ x”,” y”} = n1, จำนวน {“ y”,” x”} คู่ = n2
เราสามารถชำระ 2 คู่ของประเภท 3 ในการแลกเปลี่ยนครั้งเดียว ดังนั้นการแลกเปลี่ยนทั้งหมดที่เราต้องใช้ในการกำหนดคู่ n1 จะเป็น n1 / 2 หาก n1 เป็นคี่หนึ่งคู่จะยังคงค้างอยู่

ในทำนองเดียวกันสำหรับ n2 หาก n1 และ n2 ทั้งคู่เป็นเลขคี่เราจะได้คู่หนึ่งคู่ของแต่ละคู่ที่ไม่ได้ตั้งค่าดังนั้นเราจึงสามารถใช้การดำเนินการประเภท (ii) ที่ต้องใช้ 2 swaps เพื่อชำระ
มิฉะนั้นถ้าความเท่าเทียมกันของ n1 และ n2 ไม่เหมือนกัน (เช่น n1 เป็นเลขคี่และ n2 เป็นเลขคู่) เราจะได้คู่หนึ่งที่ไม่ได้ตัดสิน
ในกรณีนี้จะไม่สามารถทำให้สตริงเท่ากันได้

การดำเนินงาน

โปรแกรม C ++ สำหรับ Swaps ขั้นต่ำเพื่อสร้าง Strings Equal Leetcode Solution

#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 สำหรับ Swaps ขั้นต่ำเพื่อสร้าง Strings Equal Leetcode Solution

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

การวิเคราะห์ความซับซ้อนสำหรับ Swaps ขั้นต่ำเพื่อสร้าง Strings Equal Leetcode Solution

ความซับซ้อนของเวลา

บน) : โดยที่ n คือความยาวของสตริง ในขณะที่เราทำซ้ำทั้งสองสตริงเพียงครั้งเดียวดังนั้นความซับซ้อนของเวลาจะเป็น O (n)

ความซับซ้อนของอวกาศ

O (1): เราไม่ได้ใช้พื้นที่พิเศษใด ๆ