Хоёртын мөрийг ээлжлэн x ба y давтамжтайгаар дахин зохион байгуул


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accolite Cisco Citrix явган аялал IBM Мэдээллийн ирмэг Pinterest Roblox Tesla
String

Асуудлын мэдэгдэл

Танд хоёртын файл өгсөн гэж бодъё мөр, ба x ба y гэсэн хоёр тоо. Мөр нь зөвхөн 0 ба 1-ээс бүрдэнэ. "Хоёртын мөрийг ээлжлэн x ба y тохиолдлууд болгон дахин тохируулах" гэсэн асуудал нь мөрийг 0-д x удаа ирдэг comes 1 удаа y дахин ирдэг 0 дахин 1 удаа x удаа ирдэг ⇒ 0 y удаа ирдэг гэх мэтчилэн 1s эсвэл XNUMXs хүртэл болтол дахин тохируулахыг хүсдэг. дууссан. Дараа нь мөрний үлдсэн хэсгийг холбоод хэвлэ.

Жишээ нь

str = “01101”,

x = 1

y = 1
01011

Тайлбар

Эхлээд 0 удаа x удаа, дараа нь 1 удаа y удаа, дараа нь 0 удаа, дараа нь 1 удаа 0 удаа хэвлүүлээд одоо 1 үлдсэн тул мөрний үлдсэн хэсгийг XNUMX болгон хавсаргана.

Хоёртын мөрийг ээлжлэн 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 гэсэн хоёр утгыг өгдөг. Ингэснээр бид гаралтын мөрөнд 0-ийг x удаа, гаралтын мөрөнд 1-ийг дараалан "y" давтах ёстой. Хэрэв мөр үлдсэн бол үлдсэн мөрийг энэ гаралтын мөрөөр холбоно уу. Үүний тулд бид тэг ба нэгийн аль алиных нь тоо, трекийг хадгалахын тулд ердөө л zeroCount ба onesCount хоёуланд нь энгийн тоолуур ашиглахгүй.

Бид үсэг бүрийг мөрөөр туулах гэж байна. Үсэг бүр нь мөр хэлбэрээр 0 эсвэл 1 байх болно. Өгөгдсөн мөрөнд хичнээн нь тэг, хэд нь байгааг тоолох вэ? Тэгүүдийн тоог zeroCount-д, нэгийн тоог onesCount-д хадгалах болно. Эдгээр хоёр хувьсагчууд нь үйлдлийг гүйцэтгэсний дараа ч гэсэн тэг ба нэгийг тоолох болно.

Нийт тэг ба нэг мөрөнд байгаа тоог тоолсны дараа. Бид zeroCount эсвэл onesCount 0 болтол давталт үргэлжилнэ гэсэн нөхцлөөр циклийг эхлүүлэх болно. Энэ циклд бид zeroCount ба onesCount-ийг тус тусад нь туулах бөгөөд давталт x хүртэл үргэлжилнэ. утгыг давталтаар олж авна. Энэ хугацаанд бид '0' -г хэвлэх бөгөөд тэгCount-ийн утгыг бууруулж x удаа хэвлэнэ. Үүний дараа '1' y удаа хэвлэх өөр нэг давталт хийгдэх болно. Дараа нь onesCount-ийн утгыг бууруулж байгаарай. Энэ үлдсэн мөрөнд нөлөөлөхгүй бөгөөд бид хүссэн үр дүнг авах болно.

код

Хоёртын мөрийг өөр x ба y тохиолдлоор дахин тохируулах C ++ код

#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 давтамжтайгаар дахин тохируулах Java код

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) хаана "N" гэдэг нь мөрний урт юм. Энд бид мөрний урттай тэнцэх гогцоог ажиллуулав. Шалтгаан нь бид мөрийг тодорхой хэлбэрээр өөрчлөхийг шаардсан. Бид үүнийг шугаман хугацааны нарийн төвөгтэй байдалд оруулсан бүх тэмдэгтүүдийг хэвлэх ёстой байв.

Сансрын нарийн төвөгтэй байдал

O (1), Учир нь бид шинэ мөрийг хадгалахгүй байна. Бид шинэ мөрийн элементүүдийг хэвлэж байна. Тиймээс энэ ажиллагаа бидэнд ямар ч зай шаардагдахгүй. Тиймээс алгоритмын хувьд орон зайн нарийн төвөгтэй байдал нь тогтмол байдаг. Бүх програм нь оролтыг хадгалахын тулд O (N) зай шаарддаг.