题目地址：

https://www.lintcode.com/problem/digital-flip/description

给定一个$0-1$数组，每次可以将其中一个$1$变为$0$或$0$变为$1$。要求flip若干位置使得$0$的后面的数字必须是$0$。问至少要flip多少个位置。

可以看出，最后要达到的效果是，使得数组先连续若干个$1$，然后再若干个$0$（这里的”若干“可以是$0$个）。那么可以枚举分界点，如果分界点是$A[i]$的话（也就是如果$A[i]$是最后一个$1$的话），设$A$里一共有$x$个$1$，$A[0:i]$里$0$的个数是$a$，$A[i+1:l_A-1]$里$1$的个数是$b$，那么要flip的位置个数就是$a+b$。同时更新最小值即可。代码如下：

public class Solution { /** * @param nums: the array * @return: the minimum times to flip digit */ public int flipDigit(int[] nums) { // Write your code here // 先数一下一共多少个1 int count = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == 1) { count++; } } // 枚举所有数都flip成0的可能 int res = count; // 开两个变量记录A[0:i]有多少个0和1 int oneCount = 0, zeroCount = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) { zeroCount++; } else { oneCount++; } // A[0: i]的0的个数加上A[i + 1: n - 1]的1的个数 res = Math.min(res, zeroCount + count - oneCount); } return res; } }

时间复杂度$O(n)$，空间$O(1)$。