გადაანაწილეთ ორობითი სტრიქონი, როგორც ალტერნატიული x და y მოვლენები


Რთული ტური საშუალო
ხშირად ეკითხებიან თანამოსაყრელი Cisco Citrix ლაშქრობა IBM ინფო ზღვარი Pinterest რობლოქსი Tesla
სიმებიანი

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

დავუშვათ, რომ მოგეცემათ ორობითი სიმებიანი, და ორი რიცხვი x და y. სტრიქონი მხოლოდ 0 და 1-ებისგან შედგება. პრობლემა "ორობითი სტრიქონის შეცვლა x და y ალტერნატიული მნიშვნელობებით" ითხოვს სტრიქონის გადაწყობას ისე, რომ 0 მოდის x ჯერ ⇒ 1 მოდის y ჯერ 0 ისევ 1 მოდის x ჯერ ⇒ 0 მოდის y ჯერ და ასე შემდეგ 1 ან XNUMX წლამდე დასრულებულია შემდეგ მიამაგრეთ სტრიქონის დარჩენილი ნაწილი და დაბეჭდე.

მაგალითი

str = “01101”,

x = 1

y = 1
01011

განმარტება

ჯერ 0 დაბეჭდილი x ჯერ, შემდეგ 1 დაბეჭდილი y ჯერ, შემდეგ 0 x ჯერ, შემდეგ კვლავ 1 y ჯერ, მაგრამ ახლა 0 დარჩა, ასე რომ, ჩვენ ვაკავშირებთ სტრიქონის დანარჩენ ნაწილს, რომელიც არის 1.

გადაანაწილეთ ორობითი სტრიქონი, როგორც ალტერნატიული x და y მოვლენები

 

ორობითი სტრიქონის შეცვლის ალგორითმი x და y ალტერნატიული მოვლენებით

1. Count the total number of 0s and 1s.
2. Make a loop till the count of either of zeros or ones will be 0.
  1. Traverse in an individual loop for zeroCount, till the value x is reached and till the zeroCount will not be 0, print the 0, and decrease the value of zeroCount by 1.
  2. Traverse in an individual loop for onesCount, till the value y is reached and till the onesCount will not be 0, print the 1, and decrease the value of onesCount by 1.

განმარტება

ორობითი სიმებიანი როგორც შეყვანილი ჩვენ. ეს ორობითი სტრიქონი მხოლოდ 0-სა და 1-ისგან შედგება, როგორც სახელი გვთავაზობს. ასევე მოცემულია ორი მნიშვნელობა x და y. ისეთი, რომ გამომავალი სტრიქონის x– ჯერ უნდა გავიმეოროთ 0 და გამომავალი სტრიქონის „y“ ზედიზედ 1 – ჯერ. და თუ დარჩა სტრიქონი, დარჩენილი სტრიქონი გააერთიანეთ ამ გამომავალი სტრიქით. ამისათვის ჩვენ არაფერს გამოვიყენებთ, გარდა უბრალო მრიცხველისა, როგორც zeroCount- ისა და onesCount- ისთვის, რომ შევინარჩუნოთ რიცხვი და ტრეკები როგორც ნულოვანი, ასევე ერთიანი.

ჩვენ ვაპირებთ სტრიქონის გადაკვეთას თითოეული ასო. თითოეული ასო იქნება 0 ან 1 სტრიქონის სახით. და ჩავთვლით რამდენია ნულოვანი და რამდენია მოცემულ სტრიქონში? ნულოვანი რიცხვების შენახვა მოხდება ნულოვანი ანგარიშში და პირობათა რაოდენობა ინახება ერთში. ეს ორი ცვლადი შეინარჩუნებს ნულებისა და ერთეულების რიცხვს ოპერაციების შესრულების შემდეგაც.

სტრიქონში ნულებისა და ერთეულების მთლიანი რაოდენობის დათვლის შემდეგ. ჩვენ დავიწყებთ მარყუჟს იმ პირობით, რომ მარყუჟი გაგრძელდება zeroCount– ზე ან 0C იქნება 0 – ით. ამ მარყუჟში ჩვენ გავდივართ ნულოვანი და ერთიანი ანგარიშისთვის ინდივიდუალურად, იმ პირობით, რომ მარყუჟი გაგრძელდება x– მდე მნიშვნელობა მიიღწევა მარყუჟში. ამ დროის განმავლობაში ჩვენ ვბეჭდავთ "1" -ს და შევამცირებთ zeroCount- ის მნიშვნელობას და დავბეჭდავთ მას x- ჯერ. ამის შემდეგ შესრულდება კიდევ ერთი ციკლი, რომელიც იბეჭდება 'XNUMX' y ჯერ. შემდეგ გააგრძელეთ yekCount- ის მნიშვნელობის შემცირება. ამ დანარჩენი სტრიქონი არ იმოქმედებს და მივიღებთ სასურველ გამომავალს.

კოდი

C ++ კოდი ორობითი სტრიქონის მოსაწყობად x და y ალტერნატიული მნიშვნელობებით

#include<iostream>

using namespace std;

void arrangeZeroesAndOnes(string str, int x, int y)
{
    int zeroCount = 0;
    int onesCount = 0;
    int len = str.length();

    for (int i = 0; i < len; i++)
    {
        if (str[i] == '0')
            zeroCount++;
        else
            onesCount++;
    }
    while (zeroCount > 0 || onesCount > 0)
    {
        for (int j = 0; j < x && zeroCount > 0; j++)
        {
            if (zeroCount > 0)
            {
                cout << "0";
                zeroCount--;
            }
        }
        for (int j = 0; j < y && onesCount > 0; j++)
        {
            if (onesCount > 0)
            {
                cout << "1";
                onesCount--;
            }
        }
    }
}
int main()
{
    string str = "01101";
    int x = 1;
    int y = 1;
    arrangeZeroesAndOnes(str, x, y);
    return 0;
}
01011

ჯავის კოდი ორობითი სტრიქონის შესაწყობად, როგორც ალტერნატიული x და y მოვლენები

class arrangeBinaryString
{
    static void arrangeZeroesAndOnes(String str, int x, int y)
    {
        int zeroCount = 0;
        int onesCount = 0;
        int len = str.length();

        for (int i = 0; i < len; i++)
        {
            if (str.charAt(i) == '0')
                zeroCount++;
            else
                onesCount++;
        }

        while (zeroCount > 0 || onesCount > 0)
        {
            for (int j = 0; j < x && zeroCount > 0; j++)
            {
                if (zeroCount > 0)
                {
                    System.out.print ("0");
                    zeroCount--;
                }
            }
            for (int j = 0; j < y && onesCount > 0; j++)
            {
                if (onesCount > 0)
                {
                    System.out.print("1");
                    onesCount--;
                }
            }
        }
        System.out.println();
    }
    public static void main (String[] args)
    {
        String str = "01101";
        int x = 1;
        int y = 1;
        arrangeZeroesAndOnes(str, x, y);

    }
}
01011

სირთულის ანალიზი

დროის სირთულე

O (n) სადაც "ნ" სიმების სიგრძეა. აქ ჩვენ გავუშვით მარყუჟი სიმების სიგრძის ტოლი. იმის გამო, რომ ჩვენ მოგვმართეს სიმების კონკრეტული წესით გადალაგება. ჩვენ უნდა დავბეჭდოთ ყველა სიმბოლო, რამაც ის ხაზოვანი დროის სირთულეში აჩვენა.

სივრცის სირთულე

O (1), რადგან ჩვენ არ ვინახავთ ახალ სტრიქონს. ჩვენ უბრალოდ ვბეჭდავთ ახალი სტრიქონის ელემენტებს. ასე რომ, ეს ოპერაცია ჩვენთვის არ ღირს რაიმე ფართი. ამრიგად, ალგორითმისთვის სივრცის სირთულე მუდმივია. მიუხედავად იმისა, რომ მთელი პროგრამა მოითხოვს O (N) ადგილს შეყვანის შესანახად.