每日一题（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开始则会超时。