Shepherd's Blog

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

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

  • n == flips.length
  • 1 <= n <= 5 * 104
  • flips 是范围 [1, n] 中所有整数构成的一个排列

方法一：前 n 项和

既然要求前缀一致，那么当第 n 项满足前缀一致时，一定有 1…n 项均以反转，所以我们可以不用关心反转的顺序，只要在第 n 项反转时保证前 n 项的和等于以 n 为末项、步长为 1 的等差数列和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numTimesAllBlue(int[] flips) {
        long i = 1;
        long sum = 0; // 极大值时 sum 可能超过 int 范围
        int result = 0;
        for (int flip : flips) {
            sum += flip;
            if (sum == ((1 + i) * i) / 2) {
                result ++;
            }
            i ++;
        }
        return result;
    }
}

方法二：记录翻转位置的最大值

当第 n 项翻转过后满足前缀一致，那么一定存在前 n 次翻转过程中，翻转的最大值为 n。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numTimesAllBlue(int[] flips) {
        int curmax = 1;
        int result = 0;
        for (int i = 0; i < flips.length; i++) {
            curmax = Math.max(flips[i], curmax);
            if (curmax == i + 1) {
                result ++;
            }
        }
        return result;
    }
}
0%