重新排列二進製字符串作為x和y的交替出現


難度級別
經常問 ol石 思科 思傑 遠足 IBM 信息邊緣 Pinterest Roblox 特斯拉

問題陳述

假設您得到了一個二進製文件 ,以及兩個數字x和y。 該字符串僅包含0和1。 問題“將二進製字符串重新排列為x和y的交替出現”要求重新排列字符串,以使0到達x次⇒1到達y次⇒再次0到達x次⇒1 y次,依此類推,直到0s或1s完成。 然後連接字符串的其餘部分並打印。

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兩個值。 這樣我們就必須連續重複輸出字符串0中的1倍和“ y”字符串中的XNUMX倍。 如果還剩下一個字符串,則將剩下的字符串與此輸出字符串連接起來。 為此,我們將只對zeroCount和onesCount使用簡單的計數器,以保留數字和零和XNUMX的軌跡。

我們將遍歷字符串中的每個字母。 每個字母將以字符串形式為0或1。 我們將計算給定字符串中有多少個零,以及有多少個零? 零的數量將存儲在zeroCount中,而XNUMX的數量將存儲在oneCount中。 即使執行操作後,這兩個變量也將保持零和一的計數。

得到一個字符串中的零和一的總數後的計數。 我們將開始一個循環,條件是循環將一直持續到zeroCount或onesCount為0。在該循環中,我們將遍歷一個zeroCount和一個CountsCount,並且條件是循環將一直持續到x循環達到值。 在此期間,我們將打印'0',並將減少zeroCount的值並將其打印x次。 然後,將執行另一個循環,該循環將打印y 1次。 然後繼續減小onesCount的值。 使用此字符串的其餘部分將不會受到影響,我們將獲得所需的輸出。

推薦碼

用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

Java代碼將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) 哪裡 “ n” 是字符串的長度。 在這裡,我們運行的循環等於字符串的長度。 因為我們被要求以特定的方式重新排列字符串。 我們必須打印所有使它以線性時間複雜度運行的字符。

空間複雜度

O(1), 因為我們不存儲新字符串。 我們只是在打印新字符串的元素。 因此,此操作不會花費我們任何空間。 因此,算法本身的空間複雜度是恆定的。 雖然整個程序需要O(N)空間來存儲輸入。