İkili simli alternativ x və y hadisələri kimi yenidən düzəldin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Cisco Citrix Piyada çox yol qət eləmək IBM Məlumat kənarı Pinterest ROBLOX Tesla
SimBaxılıb 32

Problem bəyanat

Tutaq ki, sizə ikili verilmişdir sim, və iki rəqəm x və y. Simli yalnız 0 və 1-dən ibarətdir. Problem "İkili simli alternativ x və y hadisələri kimi yenidən düzəldin", simli yenidən düzəltməyi xahiş edir ki, 0 x dəfə gəlir ⇒ 1 y dəfə gəlir ⇒ yenidən 0 x dəfə gəlir ⇒ 1 y dəfə gəlir və s. 0s və ya 1s qədər bitdi. Sonra ipin qalan hissəsini birləşdirin və çap edin.

misal

str = “01101”,

x = 1

y = 1
01011

Izahat

Əvvəlcə 0 x dəfə, sonra 1 dəfə y, sonra 0 x dəfə, sonra yenidən 1 dəfə, ancaq 0 qalır, buna görə ipin qalan hissəsini 1-ə bağlayırıq.

İkili simli alternativ x və y hadisələri kimi yenidən düzəldinPin

 

İkili sətri alternativ x və y hadisələri kimi yenidən düzəltmək üçün alqoritm

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.

Izahat

İkili sim bir giriş olaraq verdik. Bu ikili sətir yalnız adından göründüyü kimi 0 və 1-dən ibarətdir. Bizə iki x və y dəyərləri verilir. Beləliklə, çıxış sətirindəki 0'ları x dəfə, çıxış sətrindəki 1ləri ardıcıl dəfə təkrarlamalıyıq. Və bir simli qalıbsa, qalan sətri bu çıxış sətri ilə birləşdirin. Bunun üçün həm sıfır həm də olanlar üçün sayını və parçaları saxlamaq üçün həm sıfır, həm də bir saymaq üçün sadə bir sayğacdan başqa bir şey istifadə etməyəcəyik.

Hər hərfdən ipi keçəcəyik. Hər bir hərf simvol şəklində ya 0, ya da 1 olacaqdır. Verilən sətirdə nə qədərinin sıfır, birinin neçə olduğunu hesablayacağıq? Sıfırların sayı zeroCount-da, birincilər isəCount-da saxlanacaq. Bu iki dəyişən əməliyyatlar etdikdən sonra da sıfır sayını və yenisini hesablayacaq.

Sıfırların sayı və simli olanların ümumi sayını aldıqdan sonra. Döngünün zeroCount və ya onesCount 0-a qədər davam edəcəyi bir şərtlə bir döngəyə başlayacağıq. Bu döngədə, sıfır və bir say, ayrı-ayrılıqda, döngənin x-ə qədər davam etməsi şərti ilə keçəcəyik. dəyər bir döngədə əldə edilir. Bu müddət ərzində '0' yazdıracağıq və zeroCount dəyərini azaldaraq x dəfə yazdıracağıq. Bundan sonra '1' y dəfə çap edəcək başqa bir döngə icra ediləcək. Sonra onesCount dəyərini azaltmağa davam edin. Bu qalan iplə təsirlənməyəcəyik və istənilən nəticəni əldə edəcəyik.

Kodu

İkili simli alternativ x və y hadisələri kimi yenidən təşkil etmək üçün C ++ kodu

#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

İkili simli alternativ x və y hadisələri kimi yenidən təşkil etmək üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara "N" ipin uzunluğudur. Burada ipin uzunluğuna bərabər döngə qaçdıq. Səbəbi müəyyən bir şəkildə yenidən düzəltməyimiz tələb olundu. Onu xətti zaman mürəkkəbliyində işlədən bütün simvolları çap etməli idik.

Kosmik Mürəkkəblik

O (1), çünki yeni simli saxlamırıq. Sadəcə yeni simli elementləri çap edirik. Yəni bu əməliyyat bizə heç bir yerə başa gəlmir. Və bu səbəbdən alqoritmin özü üçün kosmik mürəkkəblik sabitdir. Bütün proqram girişin saxlanılması üçün O (N) yer tələb edərkən.

Translate »