淘先锋技术网

首页 1 2 3 4 5 6 7

2023-06-14每日一题

一、题目编号

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

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

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

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

提示:

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

四、解题代码

class Solution {
public:
    int numTimesAllBlue(vector<int>& flips) {
        int n = flips.size();
        int max_flag = 0;
        int cnt = 0;
        for(int i = 0; i < n; ++i){
            max_flag = max(flips[i], max_flag);
            if(i + 1 == max_flag){
                ++cnt;
            }
        }
    return cnt;
    }
};

五、解题思路

(1) 我们所要遍历的就是flips的数组,每次翻转的是将0变成1.我们要判断1~i全是1,只需要判断是否最高翻转的位置是否是等于总的遍历的数目。

(2) 举一个flips = [3,2,4,1,5]。一开始是00000。
翻转1个字符后,翻转的最高位是3
翻转2个字符后,翻转的最高位是3
翻转3个字符后,翻转的最高位是4
翻转4个字符后,翻转的最高位是4 此时4等于4,那么就++cnt
翻转5个字符后,翻转的最高位是5,此时5等于5,那么就++cnt
最终cnt = 2。

(3) 我们按照上述所举的例子,便可以轻易的取得解决问题的放,那就是找到翻转的最高位max_flag,找到翻转的字符数目,只需要两者相等,最终结果+1即可。