每日一题（leetcode1702）：修改后的最大二进制字符串--思维

找到第一个0之后，对于后面的子串（包括那个0），所有的0都能调上来，然后一一转化为10，因此从找到的第一个0的位置开始，接下来是（后半部分子串0的个数-1）个1，然后是一个0，接着剩下的都是1.

class Solution {
public:string maximumBinaryString(string binary) {int n=binary.size();int count=0;int index=0;for(int i=0;i<n;i++){if(binary[i]=='0'){index=i;break;}}for(int i=index;i<n;i++){if(binary[i]=='0'){count++;}}for(int j=index;j<n;j++){if(count>1){binary[j]='1';}else if(count==1){binary[j]='0';}else if(count<1){binary[j]='1';}count--;}return binary;}
};

也可以利用贪心算法，显示具体的操作过程：

class Solution {
public:string maximumBinaryString(string binary) {int n = binary.size();int j = 0;for (int i = 0; i < n; i++) {if (binary[i] == '0') {while (j <= i || (j < n && binary[j] == '1')) {j++;}if (j < n) {binary[j] = '1';binary[i] = '1';binary[i + 1] = '0';}}}return binary;}
};

注意代码中的j处于一直递增状态，如果每次从0开始则会超时。