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 <= $10^5$
• s?只包含字符?‘*’ 和?‘|’?。
• 1 <= queries.length <= $10^5$
• queries[i].length == 2
• 0 <= lefti <= righti < s.length

解題思路

維護一個前綴和數組，保存每根蠟燭的左邊有多少個盤子，并且用數組記錄下所有蠟燭的下標，因為我們是按序遍歷數組，所以下標數組的元素都是遞增的，對于每個查詢queries[i] = [lefti, righti]，我們使用二分差值找出下標數組中lefti右邊的第一根蠟燭下標以及righti左邊的第一根蠟燭的下標，利用前綴和數組就可以求出兩根蠟燭間盤子的個數了

代碼

class Solution {
public:vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {int pre(0);map<int,int> m;vector<int> idx;for (int i = 0; i < s.size(); ++i) {if (s[i]=='*')pre++;else {idx.push_back(i);m[i]=pre;}}vector<int> res;for (auto q:queries){int l=bs(idx,q[0]),r=bs(idx,q[1]);if (l==r||q[0]==q[1]) {res.push_back(0);continue;}int a=idx.size();//末尾if(r>a-1)r=a-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(vector<int> &a,int tar){int l=0,r=a.size()-1;while (l<=r){int mid=(r-l)/2+l;if(a[mid]>tar){r=mid-1;}else if(a[mid]<tar){l=mid+1;}else return mid;}return l;}
};