資料結構
網路
關係資料庫管理系統
作業系統
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+ 瀏覽量
廣告