自己的网站怎么做的,网站建设兆金手指下拉,一句话宣传自己的产品,做网站有生意吗文章目录1. 题目2. 解题1. 题目
给你一个数组 arr #xff0c;该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串#xff0c;该字符串上的所有位最初都设置为 0 。
在从 1 到 n 的每个步骤 i 中#xff08;假设二进制字符串和 arr 都是从 1 开始索引的情…
文章目录1. 题目2. 解题1. 题目
给你一个数组 arr 该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串该字符串上的所有位最初都设置为 0 。
在从 1 到 n 的每个步骤 i 中假设二进制字符串和 arr 都是从 1 开始索引的情况下二进制字符串上位于位置 arr[i] 的位将会设为 1 。
给你一个整数 m 请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串且左右两边不再有可以延伸的 1 。
返回存在长度 恰好 为 m 的 一组 1 的最后步骤。如果不存在这样的步骤请返回 -1 。
示例 1
输入arr [3,5,1,2,4], m 1
输出4
解释
步骤 100100由 1 构成的组[1]
步骤 200101由 1 构成的组[1, 1]
步骤 310101由 1 构成的组[1, 1, 1]
步骤 411101由 1 构成的组[111, 1]
步骤 511111由 1 构成的组[11111]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。示例 2
输入arr [3,1,5,4,2], m 2
输出-1
解释
步骤 100100由 1 构成的组[1]
步骤 210100由 1 构成的组[1, 1]
步骤 310101由 1 构成的组[1, 1, 1]
步骤 410111由 1 构成的组[1, 111]
步骤 511111由 1 构成的组[11111]
不管是哪一步骤都无法形成长度为 2 的一组 1 。示例 3
输入arr [1], m 1
输出1示例 4
输入arr [2,1], m 2
输出2提示
n arr.length
1 n 10^5
1 arr[i] n
arr 中的所有整数 互不相同
1 m arr.length来源力扣LeetCode 链接https://leetcode-cn.com/problems/find-latest-group-of-size-m 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {
public:int findLatestStep(vectorint arr, int m) {int n arr.size(), i, ans -1;vectorvectorint pos(n2, vectorint(2, -1));//存储该组的左右端点位置vectorint len(n1, 0);//长度为x的有多少组int l1,r1,l2,r2,n1,n2,nall,l,r;for(i 0; i n; i){l r arr[i];nall 1;n1 n2 0;if(pos[l-1][0] ! -1)//左边存在{l1 pos[l-1][0];r1 pos[l-1][1];n1 r1-l11;}if(pos[l1][0] ! -1)//右边存在{l2 pos[l1][0];r2 pos[l1][1];n2 r2-l21;}if(n1){l min(l, l1);nall n1;len[n1]--;}if(n2){r max(r, r2);nall n2;len[n2]--;}len[nall];pos[l][0] l;pos[l][1] r;pos[r][0] l;pos[r][1] r;if(len[m])ans i1;}return ans;}
};648 ms 127.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
