网上做网站网站代理赚钱吗,专业行业网站建站报价,做拼团网站,网上营业执照申请2055. 蜡烛之间的盘子
给你一个长桌子#xff0c;桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s #xff0c;它只包含字符 ‘’ 和 ‘|’ #xff0c;其中 ’ 表示一个 盘子 #xff0c;’|’ 表示一支 蜡烛 。
同时给你一个下标从 0 开始的二维整数数组 q…2055. 蜡烛之间的盘子
给你一个长桌子桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s 它只包含字符 ‘’ 和 ‘|’ 其中 ’ 表示一个 盘子 ’|’ 表示一支 蜡烛 。
同时给你一个下标从 0 开始的二维整数数组 queries 其中 queries[i] [lefti, righti] 表示 子字符串 s[lefti…righti] 包含左右端点的字符。对于每个查询你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛那么这个盘子满足在 两支蜡烛之间 。
比方说s “||||| 查询 [3, 8] 表示的是子字符串 ||**|” 。子字符串中在两支蜡烛之间的盘子数目为 2 子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。 请你返回一个整数数组 answer 其中 answer[i] 是第 i 个查询的答案。 示例 1:输入s **|**|***|, queries [[2,5],[5,9]]
输出[2,3]
解释
- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。示例 2:输入s ***|**|*****|**||**|*, queries [[1,17],[4,5],[14,17],[5,11],[15,16]]
输出[9,0,0,0,0]
解释
- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。
提示
3 s.length 10510^5105s 只包含字符 ‘*’ 和 ‘|’ 。1 queries.length 10510^5105queries[i].length 20 lefti righti s.length
解题思路
维护一个前缀和数组保存每根蜡烛的左边有多少个盘子并且用数组记录下所有蜡烛的下标因为我们是按序遍历数组所以下标数组的元素都是递增的对于每个查询queries[i] [lefti, righti]我们使用二分差值找出下标数组中lefti右边的第一根蜡烛下标以及righti左边的第一根蜡烛的下标利用前缀和数组就可以求出两根蜡烛间盘子的个数了
代码
class Solution {
public:vectorint platesBetweenCandles(string s, vectorvectorint queries) {int pre(0);mapint,int m;vectorint idx;for (int i 0; i s.size(); i) {if (s[i]*)pre;else {idx.push_back(i);m[i]pre;}}vectorint res;for (auto q:queries){int lbs(idx,q[0]),rbs(idx,q[1]);if (lr||q[0]q[1]) {res.push_back(0);continue;}int aidx.size();//末尾if(ra-1)ra-1;else r idx[r]q[1]?r:r-1;res.push_back(m[idx[r]]-m[idx[l]]);//res.push_back(m[bs(idx,q[1])]-m[bs(idx,q[0])]);}return res;}int bs(vectorint a,int tar){int l0,ra.size()-1;while (lr){int mid(r-l)/2l;if(a[mid]tar){rmid-1;}else if(a[mid]tar){lmid1;}else return mid;}return l;}
};
