Leetcode 362. 敲击计数器（DAY 178）---- 二分查找学习期

拼搏现实的明天。 2022-09-13 14:29 212阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解） ##

--------------------

class HitCounter { 
    public:
        vector<pair<int,int>> v;
        HitCounter(){ }
    
        int my_higher_bound(vector<pair<int,int>>& v,int target)
        { 
            int left = 0,right = v.size();
            while(left < right)
            { 
                int mid = (left + right)/2;
                if(v[mid].first > target)    right = mid;
                else left = mid+1;
            }
            return left;
        }
    
        void hit(int timestamp)
        { 
            if(v.size() && timestamp == v.back().first)
                ++v.back().second;
            else
            { 
                if(v.size()) v.emplace_back(timestamp,v.back().second + 1);
                else v.emplace_back(timestamp,1);
            }
        }
        
        int getHits(int timestamp) 
        { 
            int higher_pos = my_higher_bound(v,timestamp) - 1;
            int lower_pos = my_higher_bound(v,timestamp-300) - 1;
            if(higher_pos < 0)  return 0;
            int ret = v[higher_pos].second - ((lower_pos < 0) ? 0 : v[lower_pos].second);
            return ret;
        }
    };
    
    /** * Your HitCounter object will be instantiated and called as such: * HitCounter* obj = new HitCounter(); * obj->hit(timestamp); * int param_2 = obj->getHits(timestamp); */

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/21bbd6d1460945a1b01919a5254f16f6.png