C ++中的特殊二进制字符串

假设我们有一个空间二进制字符串。该字符串具有以下几个属性-

  • 0和1的数目相同

  • 二进制字符串中的每个前缀至少有1到0

现在假设我们有特殊的字符串S,实际上是选择两个连续的非空的特殊S子字符串,然后交换它们。

在任何数量的移动结束时,我们都必须找到按字典顺序排列的最大结果字符串。

因此,如果输入类似于11011000,则输出将为11100100,这是因为:子字符串“ 10”和“ 1100”被交换了。在几次移动后,这是字典上可能出现的最大字符串。

为了解决这个问题,我们将遵循以下步骤-

  • 定义一个函数makeLargestSpecial(),它将花费s,

  • ret:=空字符串

  • 定义字符串数组v

  • i:= 0

  • 对于初始化j:= 0,cnt:= 0,当j <s的大小时,更新(j增加1),-

    • 在v的末尾插入“ 1” + makeLargestSpecial(s的子字符串,从索引i +1到j-i-1)

    • i:= j + 1

    • (将cnt减1)

    • (将cnt增加1)

    • 如果s [j]与'1'相同,则-

    • 除此以外

    • 如果cnt与0相同,则-

    • 排序数组vr

    • 对于初始化i:= 0,当i <v的大小时,更新(将i增加1),执行-

      • ret:= ret + v [i]

    • 返回ret

    • 在主方法中,使用字符串调用makeLargestSpecial()。

    让我们看下面的实现以更好地理解-

    示例

    #include <bits/stdc++.h>

    using namespace std;

    class Solution {

       public:

       string makeLargestSpecial(string s) {

          string ret = "";

          vector<string> v;

          int i = 0;

          for (int j = 0, cnt = 0; j < s.size(); j++) {

             if (s[j] == '1') {

                cnt++;

             }

             else

             cnt--;

             if (cnt == 0) {

                v.push_back("1" + makeLargestSpecial(s.substr(i + 1,

                j - i - 1)) + "0");

                i = j + 1;

             }

          }

          sort(v.rbegin(), v.rend());

          for (int i = 0; i < v.size(); i++)

          ret += v[i];

          return ret;

       }

    };

    main(){

       Solution ob;

       cout << (ob.makeLargestSpecial("11011000"));

    }

    输入值

    11011000

    输出结果

    11100100

    以上是 C ++中的特殊二进制字符串 的全部内容, 来源链接: utcz.com/z/327243.html

    回到顶部