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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

  • 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

    回到顶部