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

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

力扣题目链接:https://leetcode.cn/problems/number-of-times-binary-string-is-prefix-aligned/

给你一个长度为 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$其他全是$0$,那么说明前$i$次操作正好翻转的前$i$个元素。

我们只需要记录一下最大的翻转下标即可,如果最大翻转下标等于当前翻转次数,就说明前$i$个全部翻转了,答案加一。

  • 时间复杂度$O(len(flips))$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int numTimesAllBlue(vector<int>& flips) {
int M = 0;
int ans = 0;
for (int i = 0; i < flips.size(); i++) {
M = max(flips[i], M);
ans += (M == i + 1);
}
return ans;
}
};

Python

1
2
3
4
5
6
7
8
9
10
# from typing import List

class Solution:
def numTimesAllBlue(self, flips: List[int]) -> int:
M = 0
ans = 0
for i in range(len(flips)):
M = max(M, flips[i])
ans += (M == i + 1)
return ans

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/131213418


1375.二进制字符串前缀一致的次数
https://blog.letmefly.xyz/2023/06/14/LeetCode 1375.二进制字符串前缀一致的次数/
作者
Tisfy
发布于
2023年6月14日
许可协议