# 2055 - Plates Between Candles

###### tags: `leetcode.binarySearch` `leetcode.medium`

[題目連結](https://leetcode.com/problems/plates-between-candles)

## intuision

- 因為字串中只包含'|'跟'\*'，所以可以直接這樣解:
- 對每個輸入query，找出距離query[0]最近，且比query[0] index還大的第一個'|'，令他為**X**；以及找出距離query[1]最近，且比query[1] index還小的第一個'|'，令他為**Y**
- e.g. s = " |\*|\*\*\*\|\|\*| " , query = [1,8]，則
- **X** = 第2根candle, **Y** = 第4根candle
- 找出**X**跟**Y**之後，直接計算**X**跟**Y**之間的\*數就好

## implementation

- Brute force ($O(n^2)$, TLE)
- 對每個query，擷取出他的子字串sub_str(範圍在query[0]~query[1])
- 在sub_str計算在第一次碰到'|'之後到最後一次'|'之前的\*數

            bool flag = 0;
            int acc = 0;
            int ret = 0;
            int i=0;
            for(i=0;i<sub_str.length() && sub_str[i] != '|'; i++){}
            for(;i<sub_str.length();i++){
                if(sub_str[i] == '|'){
                    ret += acc;
                    acc = 0;
                }
                else{
                    acc++;
                }
            }
            return ret;

- 每個子字串長度達n，有n個query，所以複雜度$O(n^2)$

- Binary search ($O(n\;log\;n)$)
- 首先跑一遍string，記錄所有'|'的index到candle_array中
- 分別用query[0]跟query[1]的值去對candle_array跑binary search (規則同intuition)，index即為intuition的**X**跟**Y**
- 中間的'\*'即為

> (Y-X) 的意涵是扣掉index之間，是"|"的數量



## 難點&心得

- 實作binary search的變種，該algorithm須滿足:
    - 找出距離target value最近的index，**target value有可能不存在array中**
    - 分成左值跟右值，左值要找>=target value的值；右值要找<= target value的值 (故需要分成兩個binary search function)
    - 如果左值target value大於最大的index，回傳-1 (該query應該回傳0)；右值亦然(target<最小的index)

- 基礎binary search，基本array長度應該是多少，變種後又應該是多少
    - array.size() < 多少，應該個別處理，而非使用binary search?

- 不用特別做special case(n<3特別處理等等)，BS可以直接用iterative的方式去做，當初的條件設錯...
- C++有提供upper_bound跟lower_bound兩種algorithm，分別回傳vector中「大於或等於」val的「最小值」的位置、vector中「大於」val的「最小值」的位置
    - 用自己的BS(註解掉的地方)會TLE，用C++的library就AC了...(汗)


## 程式碼

class Solution {
public:
vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
vector<int> candles;
vector<int> sol;
for(int i=0; i<s.length(); i++){
if(s[i]=='|'){
candles.push_back(i);
}
}

for(auto query:queries){

int i = lower_bound(candles.begin(), candles.end(), query[0]) - candles.begin();
int j = upper_bound(candles.begin(), candles.end(), query[1]) - candles.begin() - 1;
sol.push_back(i < j ? (candles[j] - candles[i]) - (j - i) : 0);

// int leftCandleIndex = findLeftCandle(query[0], candles);
// int rightCandleIndex = findRightCandle(query[1], candles);
// if(leftCandleIndex == -1 || rightCandleIndex == -1 || leftCandleIndex >= rightCandleIndex){
// sol.push_back(0);
// }
// else{
// sol.push_back( candles[rightCandleIndex]-candles[leftCandleIndex]-(rightCandleIndex-leftCandleIndex) );
// }
}
return sol;
}

private:
int findLeftCandle(int target, vector<int> candles){
int left = 0, right = candles.size()-1;
while(left<=right){
int mid = (left+right)/2;
if(candles[mid] > target){
right = mid-1;
}
else if(candles[mid] < target){
left = mid+1;
}
else{
return mid;
}
}
if(right<0){
return 0;
}
if(left>candles.size()-1){
return -1;
}
return left; //left is the bigger one
}

int findRightCandle(int target, vector<int> candles){
int left = 0, right = candles.size()-1;
while(left<=right){
int mid = (left+right)/2;
if(candles[mid] > target){
right = mid-1;
}
else if(candles[mid] < target){
left = mid+1;
}
else{
return mid;
}
}
if(right<0){
return -1;
}
if(left>candles.size()-1){
return candles.size()-1;
}
return right; //right is the smaller one
}

};