[1529]灯泡开关 IV

//房间中有 n 个灯泡，编号从 0 到 n-1 ，自左向右排成一行。最开始的时候，所有的灯泡都是 关 着的。 
//
// 请你设法使得灯泡的开关状态和 target 描述的状态一致，其中 target[i] 等于 1 第 i 个灯泡是开着的，等于 0 意味着第 i 个灯是关着
//的。 
//
// 有一个开关可以用于翻转灯泡的状态，翻转操作定义如下： 
//
// 
// 选择当前配置下的任意一个灯泡（下标为 i ） 
// 翻转下标从 i 到 n-1 的每个灯泡 
// 
//
// 翻转时，如果灯泡的状态为 0 就变为 1，为 1 就变为 0 。 
//
// 返回达成 target 描述的状态所需的 最少 翻转次数。 
//
// 
//
// 示例 1： 
//
// 输入：target = "10111"
//输出：3
//解释：初始配置 "00000".
//从第 3 个灯泡（下标为 2）开始翻转 "00000" -> "00111"
//从第 1 个灯泡（下标为 0）开始翻转 "00111" -> "11000"
//从第 2 个灯泡（下标为 1）开始翻转 "11000" -> "10111"
//至少需要翻转 3 次才能达成 target 描述的状态 
//
// 示例 2： 
//
// 输入：target = "101"
//输出：3
//解释："000" -> "111" -> "100" -> "101".
// 
//
// 示例 3： 
//
// 输入：target = "00000"
//输出：0
// 
//
// 示例 4： 
//
// 输入：target = "001011101"
//输出：5
// 
//
// 
//
// 提示： 
//
// 
// 1 <= target.length <= 10^5 
// target[i] == '0' 或者 target[i] == '1' 
// 
// Related Topics 字符串 
// 👍 20 👎 0

因为每次按开关所影响的都是该位置以后的灯泡， 所以只能从前向后的调整灯泡的开关。
因为如果调整到i位置，没法影响之前的灯泡。如果从后往前的调整，调整i+1后，再按动i，i+1就已经发生了改变。

模拟

可以建立一个数组，该数组长度和target相同，起始都是0，意味着一排灯泡最开始的状态。
从0开始，每次将i位置的灯泡调整成和target一样，然后向后维护这个数组，每次按动结果+1，最后返回结果。
要使用一个数组来保存现在的灯泡状态，空间复杂度O(n)。
从头遍历数组，每次遍历都会去向后调整后面数组的值，时间复杂度≈O(n )

分析

如果有多个相同的0或1连在一起，那么调整第一个的时候，后面紧挨着相同的字符是不需要去调整的。
因此可以将target进行压缩， 如 10111 调整次数和 101 是相同的。
那么问题就转化成了求一个01相间的字符要调整多少次。
因为是01相间，所以调整i后，一定要调整i+1位，也就是说，如果这个字符串是01相间的，那么一定会调整他的长度这么多次。
其中有一个例外，如果字符串的开头是0的话，是不需要调整第一次的。

class Solution {
    public int minFlips(String target) {
        char[] chars = target.toCharArray();
        int res = 0;
        // 如果字符串开头是0的话，第一次是不需要调整的
        if (chars[0] == '1'){
            res++;
        }
        for (int i = 1; i < chars.length; i++) {
            // 查找01相间的位置有多少个，每次字符发生改变的时候都需要按动一次按钮
            if (chars[i] != chars[i - 1]){
                res++;
            }
        }
        return res;
    }
}