1375. 二进制字符串前缀一致的次数

LC每日一题，参考1375. 二进制字符串前缀一致的次数，难度分1439。

题目

给你一个长度为 n 、下标从 1 开始的二进制字符串，所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位（即，将 0 变为 1）。

给你一个下标从 1 开始的整数数组 flips ，其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。

二进制字符串 前缀一致 需满足：在第 i 步之后，在 闭 区间 [1, i] 内的所有位都是 1 ，而其他位都是 0 。

返回二进制字符串在翻转过程中 前缀一致 的次数。

输入：flips = [3,2,4,1,5]
输出：2
解释：二进制字符串最开始是 "00000" 。
执行第 1 步：字符串变为 "00100" ，不属于前缀一致的情况。
执行第 2 步：字符串变为 "01100" ，不属于前缀一致的情况。
执行第 3 步：字符串变为 "01110" ，不属于前缀一致的情况。
执行第 4 步：字符串变为 "11110" ，属于前缀一致的情况。
执行第 5 步：字符串变为 "11111" ，属于前缀一致的情况。
在翻转过程中，前缀一致的次数为 2 ，所以返回 2 。
输入：flips = [4,1,2,3]
输出：1
解释：二进制字符串最开始是 "0000" 。
执行第 1 步：字符串变为 "0001" ，不属于前缀一致的情况。
执行第 2 步：字符串变为 "1001" ，不属于前缀一致的情况。
执行第 3 步：字符串变为 "1101" ，不属于前缀一致的情况。
执行第 4 步：字符串变为 "1111" ，属于前缀一致的情况。
在翻转过程中，前缀一致的次数为 1 ，所以返回 1 。

解题思路

• 枚举：根据题意,可知前缀一致条件,枚举判断。
• 树状数组：根据树状数组前缀和判断(普通数组求前缀和n^2超时)。

枚举

class Solution {
    public int numTimesAllBlue(int[] flips) {
        //要想前缀一致 需要保证当前flips的值连续如[3214][123][312]等最大值=长度
        int ans = 0,n = flips.length,max = 0;
        for(int i = 0; i < flips.length; i++){
            max = Math.max(max,flips[i]);
            if(max == i+1) ans ++;
            /*else if(max == n) {//此时除了i=n-1之后都不满足退出循环
                ans++;
                break;
            }*/
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，遍历一次。
• 空间复杂度：O(1)。

树状数组

class Solution {
    int[] tree;
    public int numTimesAllBlue(int[] flips) {
        int n = flips.length;
        tree = new int[n + 1]; // 树状数组 默认为0 表示熄灭
        int res = 0, max = 0; 
        for (int i : flips) {
            set(i);
            max = Math.max(max, i);
            if (sum(max) == max) res++;//根据前缀和判断
        }
        return res;
    }
    //标记为1 表示点亮
    void set(int index) {
        while (index < tree.length) {
            tree[index] += 1;
            index += lowBit(index);
        }
    }
    //前缀和
    int sum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lowBit(index);
        }
        return sum;
    }

    int lowBit(int x) {
        return x & (-x);
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，遍历一次n,树状数组logn。
• 空间复杂度：O(n)。