class Solution {
public:
int numTimesAllBlue(vector<int>& flips) {
}
};
1375. 二进制字符串前缀一致的次数
给你一个长度为 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.length1 <= n <= 5 * 104flips 是范围 [1, n] 中所有整数构成的一个排列原站题解
javascript 解法, 执行用时: 76 ms, 内存消耗: 45.9 MB, 提交时间: 2022-12-05 16:08:52
/**
* @param {number[]} light
* @return {number}
*/
var numTimesAllBlue = function(light) {
let count = 0 ,sum = 0
for(let i = 0 ;i<light.length;i++){
sum+=light[i]
let len = i+1,addSum = len*(len+1)/2
if(sum ==addSum){
count++
}
}
return count
};
python3 解法, 执行用时: 120 ms, 内存消耗: 20 MB, 提交时间: 2022-12-05 16:08:22
class Solution:
def numTimesAllBlue(self, flips: List[int]) -> int:
ans, _sum, cnt = 0, 0, 0
for flip in flips:
cnt += 1
_sum += flip
if _sum == (cnt + 1) * cnt // 2:
ans += 1
return ans
cpp 解法, 执行用时: 56 ms, 内存消耗: 37.6 MB, 提交时间: 2022-12-05 16:06:35
// 如果当前所有灯都是蓝色，那么亮灯的编号和必定等于1+2+...+亮灯数目，维护亮灯数目和亮灯编号和即可。
class Solution {
public:
int numTimesAllBlue(vector<int>& light) {
int ans=0;
long long sum=0,cnt=0;
for(auto v : light)
{
++cnt;
sum+=v;
if(sum==(cnt+1)*cnt/2)++ans;
}
return ans;
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 49.2 MB, 提交时间: 2022-12-05 16:04:11
/**
* 遍历数组，记录当前最大亮起来的灯，如果最大亮起来的灯等于遍历过的灯的数量，那么说明前面灯都亮了。
* 举个例子，[2,1,3]，当遍历到3的时候，最大的灯是3，等于当前已经亮起来的灯的个数，
* 因此3左侧的灯全部亮了，算一个可行解。
*/
class Solution {
public int numTimesAllBlue(int[] light) {
int ans = 0;
int curMax = 0;
for (int i = 0; i < light.length; i++) {
curMax = Math.max(curMax, light[i]);
if (curMax == i + 1) {
ans++;
}
}
return ans;
}
}