leetcode 困难题 761. Special Binary String 特殊的二进制序列

Problem: leetcode 困难题 761. Special Binary String 特殊的二进制序列

解题过程

这题目的描述有问题，下面注释掉的就是递归做的，这是我的理解：第一次交换以后的字符串接着做第二次交换，接着做第三次交换，每次递归的输入长度都是最开始输入的s.size()，而不是分片以后的长度，然后拿到最大的字符串

看了官方题解，感觉和题目的描述不太相同，官方题解使用了分片，也就是找到这个字符串所有的分片然后重排合并，并不是交换一次以后继续递归

Code

class Solution { public: string makeLargestSpecial(string s) { if(s.size() <= 2) return s; int cnt = 0, left = 0; vector<string> 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>()); string tmp; for(int i = 0; i < subs.size(); i++) { tmp += subs[i]; } return tmp; } }; /* class Solution { public: string ret; bool check(string tg) { int a = 0, z = 0; for(char& c : tg) { if(c=='1') a++; else z++; if(a < z) return false; } return true; } unordered_set<string> te; string makeLargestSpecial(string s) { for(int w = 0; w < s.size(); w++) { while(w < s.size() && s[w]=='0') w++; if(w>= s.size()) continue; int a = 0, z = 0; string s1, s2, t1, t2; for(int i = w; i < s.size(); i++) { if(s[i]=='1') a++; else z++; if(a == z) { int aa = 0, zz = 0, ww = i + 1; while(ww < s.size() && s[ww]=='0') ww++; if(ww < s.size()) { for(int j = ww; j < s.size(); j++) { if(s[j]=='1') aa++; else zz++; if(aa == zz) { t1 = s1 = s.substr(w, i - w + 1); t2 = s2 = s.substr(ww, j - ww + 1); if(s1.size()!=0 && s2.size()!=0 && s1!=s2 && check(t1) && check(t2)) { string prefix, tail, mid, now, rec; prefix = s.substr(0, w); if(j+1 < s.size()) tail = s.substr(j+1); if(i+1 < ww) mid = s.substr(i+1, ww - i - 1); if(s1.size() < s2.size()) { s1 += string(s2.size()-s1.size(), '0'); } else { s2 += string(s1.size() - s2.size(), '0'); } if(s1 < s2) { now = prefix + t2 + mid + t1 + tail; if(check(now)) { ret = max(ret, now); // if(now > s) { if(te.find(ret)== te.end()) { te.insert(ret); rec = makeLargestSpecial(ret); ret = max(ret, rec); } // } } } } } } } } } } return ret.size()==0? s:ret; } }; */