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

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

文章目录

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

原题题目

在这里插入图片描述

代码实现（首刷自解）

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); */