【每日一题Day237】LC1375二进制字符串前缀一致的次数 | 技巧题

简介: 【每日一题Day237】LC1375二进制字符串前缀一致的次数 | 技巧题

二进制字符串前缀一致的次数【LC1375】

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

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

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

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

技巧题,二十分钟想出来了

思路

由于每位只翻转一次,不存在0->1->0的情况,因此如果在第 i 步之后,在 闭 区间 [1, i] 内的所有位都是 1时,那么前i步翻转的位一定是[1, i] 内的所有位。因此可以记录截止第i步,翻转位的最大值,如果与i相等,那么代表前缀一致,次数+1

实现

class Solution {
    public int numTimesAllBlue(int[] flips) {
        int n = flips.length;
        int res = 0;
        int mx = 0;
        for (int i = 0; i < n; i++){
            mx = Math.max(mx, flips[i]);
            if (mx == i + 1){
                res++;
            }
        }
        return res;
    }
}

复杂度

  • 时间复杂度:O ( n )
  • 空间复杂度:O ( 1 )
目录
相关文章
|
6月前
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
39 0
|
3月前
|
C++
串应用- 计算一个串的最长的真前后缀
这篇文章提供了一个C++程序,用于找出给定字符串的最长真前后缀,并展示了如何通过计算每个子串的最长相同前后缀来实现这一功能。
|
6月前
|
算法
【算法学习--字符串】(不含KMP算法)
【算法学习--字符串】(不含KMP算法)
|
6月前
【每日一题Day203】LC1016子串能表示从 1 到 N 数字的二进制串 | 枚举 哈希表
【每日一题Day203】LC1016子串能表示从 1 到 N 数字的二进制串 | 枚举 哈希表
48 2
|
6月前
leetcode-1784:检查二进制字符串字段
leetcode-1784:检查二进制字符串字段
34 0
|
6月前
【每日一题Day233】LC1170比较字符串最小字母出现频次 | 前缀和
【每日一题Day233】LC1170比较字符串最小字母出现频次 | 前缀和
39 0
|
Java
NetEase网易 Java笔试题 给定一个字符串,请返回满足以下条件的最长字符串的长度:“a”、“b“、“c”、“x”、“y“、“z”在字符串中都恰好出现了偶数次(0也是偶数)
NetEase网易 Java笔试题 给定一个字符串,请返回满足以下条件的最长字符串的长度:“a”、“b“、“c”、“x”、“y“、“z”在字符串中都恰好出现了偶数次(0也是偶数)
115 0
|
算法 C++ Python
每日算法系列【LeetCode 424】替换后的最长重复字符
每日算法系列【LeetCode 424】替换后的最长重复字符
|
索引
【LC简单】387. 字符串中的第一个唯一字符
【LC简单】387. 字符串中的第一个唯一字符
80 0
【LC简单】387. 字符串中的第一个唯一字符
|
Java
【LC简单】434. 字符串中的单词数
【LC简单】434. 字符串中的单词数
70 0
【LC简单】434. 字符串中的单词数