---
# System prepended metadata

title: 2055 - Plates Between Candles
tags: [leetcode.medium, leetcode.binarySearch]

---

# 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計算在第一次碰到'|'之後到最後一次'|'之前的\*數
    ```C++
            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**
    - 中間的'\*'即為
```( (candle_array[Y] - candle_array[X]) - (Y-X) );```

> (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了...(汗)


## 程式碼

```cpp=
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
    }
    
    
};
```


