Leetcode 926. Flip string to monotonically increasing [prefix and]

subject

Ideas

The property of the string we want to solve is , There is one located at s[i],s[i+1] Previous position , The characters to the left of this position are all 0, The characters on the right are all 1 . We can flip some values to construct a string that satisfies the above properties , So what we are looking for is such a position , Make it to the left 1 Plus the number on the right 0 Minimum number of .

Code

class Solution {
    
    private:
        int* pre;
    public:
        int minFlipsMonoIncr(string s) {
    
            pre = new int[s.size()+1];
            pre[0] = 0;
            for(int i = 0; i < s.size(); ++i) {
    
                pre[i+1] = pre[i]+s[i]-'0';
            }
            int _min = INT_MAX;
            for(int i = -1; i < (int)s.size(); ++i) {
      //  from -1 It starts because this position may precede all characters 
            										   //  because s.size() Returns an unsigned number , So you have to cast 
                int t = s.size()-(i+1);
                t -= (pre[s.size()]-pre[i+1]);
                _min = min(_min, pre[i+1]+t);
                /* printf("%d %d\n", pre[i+1], t); */
            }
            return _min;
        }
};

class Solution {
      //  Just found me sb 了 , There is no need to calculate the prefix and , The thought set is terrible 
    public:
        int minFlipsMonoIncr(string s) {
    
            int lo = 0, rz = 0;
            for(int i = 0; i < s.size(); ++i) {
    
                if(s[i]=='0') ++rz;
            }
            int _min = lo+rz;
            for(int i = 0; i < s.size(); ++i) {
    
                if(s[i]=='1') {
    
                    lo += 1;
                } else {
    
                    rz -= 1;
                }
                _min = min(lo+rz, _min);
            }
            return _min;
        }
};

Running results