There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.
You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti...righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.
- For example,
s = "||**||**|*", and a query[3, 8]denotes the substring"*||**|". The number of plates between candles in this substring is2, as each of the two plates has at least one candle in the substring to its left and right.
Return an integer array answer where answer[i] is the answer to the ith query.
Example 1:
Input: s = "**|**|***|", queries = [[2,5],[5,9]] Output: [2,3] Explanation: - queries[0] has two plates between candles. - queries[1] has three plates between candles.
Example 2:
Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]] Output: [9,0,0,0,0] Explanation: - queries[0] has nine plates between candles. - The other queries have zero plates between candles.
Constraints:
3 <= s.length <= 105sconsists of'*'and'|'characters.1 <= queries.length <= 105queries[i].length == 20 <= lefti <= righti < s.length
Solution: Binary Search
Store the indices of all candles into an array idx.
For each query q:
1. Find the left most candle whose index is greater or equal to left as l.
2. Find the left most candle whose index is greater than right, choose the previous candle as r.
[idx[l], idx[r]] is the range that are elements between two candles , there are (idx[r] – idx[l] + 1) elements in total and there are (r – l + 1) candles in the range. So the number of plates is (idx[r] – idx[l] + 1) – (r – l + 1) or (idx[r] – idx[l]) – (r – l)
Time complexity: O(qlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: huahua class Solution { public: vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) { vector<int> idx; for (size_t i = 0; i < s.size(); ++i) if (s[i] == '|') idx.push_back(i); vector<int> ans; for (const auto& q : queries) { const int l = lower_bound(begin(idx), end(idx), q[0]) - begin(idx); const int r = upper_bound(begin(idx), end(idx), q[1]) - begin(idx) - 1; ans.push_back(l >= r ? 0 : (idx[r] - idx[l]) - (r - l)); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment