leetcode 926. Flip String to Monotone Increasing | 926. 将字符串翻转到单调递增（前缀和）

女爷i 2022-09-04 03:56 145阅读 0赞

## 题目 ##

[https://leetcode.com/problems/flip-string-to-monotone-increasing/][https_leetcode.com_problems_flip-string-to-monotone-increasing]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 方法1：前缀和 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

class Solution { 
        public int minFlipsMonoIncr(String s) { 
            int L = s.length();
            // i位置左边1的个数
            int[] leftOne = new int[L];
            for (int i = 0; i < L - 1; i++) { 
                if (s.charAt(i) == '1') leftOne[i + 1] = leftOne[i] + 1;
                else leftOne[i + 1] = leftOne[i];
            }
            // i位置右边0的个数
            int[] rightZero = new int[L];
            for (int i = L - 1; i > 0; i--) { 
                if (s.charAt(i) == '0') rightZero[i - 1] = rightZero[i] + 1;
                else rightZero[i - 1] = rightZero[i];
            }
            // 将i左边全变成1，i右边全变成0，总共需要改的个数
            int minSum = Integer.MAX_VALUE;
            for (int i = 0; i < L; i++) { 
                minSum = Math.min(minSum, leftOne[i] + rightZero[i]);
            }
            return minSum;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

#### 方法2：dp ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

int minFlipsMonoIncr(char *s) { 
        int z = *s == '0' ? 0 : 1;
        int o = *s == '0' ? 1 : 0;
        for (s++; *s; s++){ 
            if (*s == '0'){ 
                o = (z < o ? z : o) + 1;
            }else{ 
                o = (z < o ? z : o);
                z++;
            }
        }
        return z < o ? z : o;
    }

[https_leetcode.com_problems_flip-string-to-monotone-increasing]: https://leetcode.com/problems/flip-string-to-monotone-increasing/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/ff73080d9a194e5fa0fb298786253cf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/01084a284f904addaea44fe1ce5b5692.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/7124d8d6df524e53a7ba33a59dc4a165.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/b0c32a6c0d6f4ca1a0bd73eb5249e220.png