926. 将字符串翻转到单调递增

港控/mmm° 2023-02-27 05:54 29阅读 0赞

如果一个由 ‘0’ 和 ‘1’ 组成的字符串，是以一些 ‘0’（可能没有 ‘0’）后面跟着一些 ‘1’（也可能没有 ‘1’）的形式组成的，那么该字符串是单调递增的。

我们给出一个由字符 ‘0’ 和 ‘1’ 组成的字符串 S，我们可以将任何 ‘0’ 翻转为 ‘1’ 或者将 ‘1’ 翻转为 ‘0’。

返回使 S 单调递增的最小翻转次数。

来源：力扣（LeetCode）  
链接：[添加链接描述][Link 1]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]  
前缀和：

class Solution {
        
    public:
        int minFlipsMonoIncr(string S) {
        
            int n = S.size();
            if(n == 0) return 0;
            int p[n+1];
            p[0] = 0;
            for(int i = 1; i <= n; i++) {
        
                if(S[i-1] == '1') p[i] = p[i-1] + 1; //前面i位变成全0需要翻转的次数
                else p[i] = p[i-1];
            } 
    
            int ans = INT_MAX; 
            for(int i = 0; i <= n; i++){
        
                ans = min(ans, p[i] + n-i-(p[n]-p[i]));//前i位为0，后面全1
            }
            return ans;
        }
    };

动态规划：

class Solution {
        
    public:
        int minFlipsMonoIncr(string S) {
        
            int n = S.size();
            vector<vector<int> > dp(n, vector<int>(2, 0)); 
            //前i位排好序需要翻转的次数，分别记录结尾为0，1的两种情况
            if(n == 0) return 0;
            if(S[0] == '0') {
        
                dp[0][0] = 0;
                dp[0][1] = 1;
            }else {
        
                dp[0][0] = 1;
                dp[0][1] = 0;
            }
            for(int i = 1; i < S.size(); i++){
        
                if(S[i] == '0'){
        
                    dp[i][0] = dp[i-1][0];
                    dp[i][1] = min(dp[i-1][1], dp[i-1][0]) + 1;
                }else {
        
                    dp[i][0] = dp[i-1][0] + 1;
                    dp[i][1] = min(dp[i-1][0], dp[i-1][1]);
                }
            }
            return min(dp[n-1][0], dp[n-1][1]);
        }
    };

[Link 1]: https://leetcode-cn.com/problems/flip-string-to-monotone-increasing
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]: /images/20230209/62679779fd78415096d7b097c8b61c41.png