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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

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

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

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

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

示例 1：

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

示例 2：

**输入：** 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] 中所有整数构成的一个排列

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

思路与算法

在第 i 次翻转之后，我们希望 [1, i] 内的所有位都是 1，这等价于「前 i 次翻转中下标的最大值等于 i」。

因此，我们对数组 flip 进行遍历，同时记录翻转下标的最大值。当遍历到位置 i 时，如果最大值恰好等于 i，那么答案加 1。

需要注意数组的下标是从 0 开始的，因此在实际的代码编写中，判断的值为 i+1。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numTimesAllBlue(vector<int>& flips) {
        int n = flips.size();
        int ans = 0, right = 0;
        for (int i = 0; i < n; ++i) {
            right = max(right, flips[i]);
            if (right == i + 1) {
                ++ans;
            }
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numTimesAllBlue(int[] flips) {
        int n = flips.length;
        int ans = 0, right = 0;
        for (int i = 0; i < n; ++i) {
            right = Math.max(right, flips[i]);
            if (right == i + 1) {
                ++ans;
            }
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int NumTimesAllBlue(int[] flips) {
        int n = flips.Length;
        int ans = 0, right = 0;
        for (int i = 0; i < n; ++i) {
            right = Math.Max(right, flips[i]);
            if (right == i + 1) {
                ++ans;
            }
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        ans = right = 0
        for i, flip in enumerate(flips):
            right = max(right, flips[i])
            if right == i + 1:
                ans += 1
        return ans
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
func numTimesAllBlue(flips []int) int {
    n, ans, right := len(flips), 0, 0
    for i := 0; i < n; i++ {
        if flips[i] > right {
            right = flips[i]
        }
        if right == i + 1 {
            ans++
        }
    }
    return ans
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
var numTimesAllBlue = function(flips) {
    const n = flips.length;
    let ans = 0, right = 0;
    for (let i = 0; i < n; ++i) {
        right = Math.max(right, flips[i]);
        if (right === i + 1) {
            ++ans;
        }
    }
    return ans;
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
int numTimesAllBlue(int* flips, int flipsSize) {
    int n = flipsSize;
    int ans = 0, right = 0;
    for (int i = 0; i < n; ++i) {
        right = fmax(right, flips[i]);
        if (right == i + 1) {
            ++ans;
        }
    }
    return ans;
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 flips 的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
1375-二进制字符串前缀一致的次数