761. 特殊的二进制序列(分治)

761. 特殊的二进制序列(分治)

761. 特殊的二进制序列(分治)

可等价为括号序列。

对于一个不可分割的括号序列显然 首位1和末位0不能操作。括号序列每个左括号唯一对应一个右括号。

因此我们可以对每一个原串的每个括号子串进行递归处理，处理到不可分割的括号序列之后就可以进行递归返回了，然后再对他们进行排序。

class Solution {public: string makeLargestSpecial(string s) { if (s.size() <= 2) { return s; } int cnt = 0, left = 0; vector subs; for (int i = 0; i < s.size(); ++i) { if (s[i] == '1') { ++cnt; } else { --cnt; if (cnt == 0) { subs.push_back("1" + makeLargestSpecial(s.substr(left + 1, i - left - 1)) + "0"); left = i + 1; } } } sort(subs.begin(), subs.end(), greater{}); string ans = accumulate(subs.begin(), subs.end(), ""s); return ans; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。