重庆建设安全管理网站,域名怎么和网站绑定,龙岗seo优化,在线资源搜索引擎文章目录1. 题目2. 解题1. 题目
给定一个01数组 arr 和 一个整数 k, 统计有多少区间符合如下条件:
区间的两个端点都为 0 (允许区间长度为1)区间内 1 的个数不多于 k
arr 的大小不超过 10^5
样例 1:
输入: arr [0, 0, 1, 0, 1, 1, 0], k 1
输出: 7
解释: [0, 0], [1, 1],…
文章目录1. 题目2. 解题1. 题目
给定一个01数组 arr 和 一个整数 k, 统计有多少区间符合如下条件:
区间的两个端点都为 0 (允许区间长度为1)区间内 1 的个数不多于 k
arr 的大小不超过 10^5
样例 1:
输入: arr [0, 0, 1, 0, 1, 1, 0], k 1
输出: 7
解释: [0, 0], [1, 1], [3, 3], [6, 6], [0, 1], [0, 3], [1, 3]
(区间 [ij] 表示下标 i包括和下标 j包括之间的元素)样例 2:
输入: arr [1, 1, 1, 0, 0, 1], k 2
输出: 3
解释: [3, 3], [4, 4], [3, 4]
(区间 [ij] 表示下标 i包括和下标 j包括之间的元素)https://tianchi.aliyun.com/oj/286606814880453210/327250187142763356
2. 解题
使用队列记录队列内的 和 s 维护 s k
class Solution {
public:/*** param arr: the 01 array* param k: the limit * return: the sum of the interval*/long long intervalStatistics(vectorint arr, int k) {// Write your code here.queueint q;int s 0;long long ans 0;for(int i 0; i arr.size(); i){q.push(i);if(arr[i])s;else//等于0以该0为右端点的区间{while(s k || arr[q.front()]1)//直到 s k 且 左端出现 0{if(arr[q.front()]1)s--;q.pop();}ans i-q.front()1 - s;//区间的长度 减去 和 s 就是零的个数}}return ans;}
};50ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
