数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的特殊二进制字符串
假设我们有一个特殊的二进制字符串。此字符串具有以下几个属性：
0 和 1 的数量相同
二进制字符串中的每个前缀至少包含与 0 相同数量的 1
现在假设我们有一个特殊的字符串 S，一个移动实际上是选择 S 的两个连续的、非空的、特殊的子字符串，并交换它们。
我们需要找到最终可能得到的字典序最大的字符串，无论经过多少次移动。
因此，如果输入类似于 11011000，则输出将为 11100100，这是因为：子字符串“10”和“1100”被交换。这是经过几次移动后可能得到的字典序最大的字符串。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 makeLargestSpecial()，它将接收 s，
ret := 空字符串
定义一个字符串数组 v
i := 0
对于初始化 j := 0，cnt := 0，当 j < s 的大小，更新（将 j 增加 1），执行：
如果 s[j] 等于 '1'，则：
（将 cnt 增加 1）
否则
（将 cnt 减 1）
如果 cnt 等于 0，则：
在 v 的末尾插入 "1" + makeLargestSpecial(从索引 i + 1 到 j - i - 1 的 s 的子字符串)
i := j + 1
对数组 v 进行逆序排序。
对于初始化 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
更新于: 2020-06-08
2K+ 浏览量
广告