Skip to main content

语法与函数

函数​

1.lower_bound()，upper_bound​

二分查找函数：

iteration::rstart lower_bound(iteration::start，iteration::end，key)；

lower_bound()返回值是一个迭代器,返回指向大于等于key的第一个值的位置

upper_bound()返回值是一个迭代器,返回指向大于key的第一个值的位置

找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

2563. 统计公平数对的数目

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        long long res = 0LL;
        for (auto it = nums.begin(); it != nums.end(); ++it) {
            int minNum = lower - *it;
            int maxNum = upper - *it;
            auto x = lower_bound(it + 1, nums.end(), minNum);
            auto y = upper_bound(x, nums.end(), maxNum);
            res += y - x;
        }
        return res;
    }
};

语法​

1.priority_queue 排序写法​

class cmp
{
    public:
    bool operator()(const pair<int,int> &a ,const pair<int,int> &b)
    {
        return a.second < b.second; //这种写法是大顶堆
    }
};
//自定义类型
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> que;
//原有类型
priority_queue<int,vector<int>,greater<int>> que; // 小顶堆
priority_queue<int,vector<int>,less<int>> que;// 大顶堆
priority_queue<int,vector<int>> que;// 大顶堆（默认）

2.map/set 排序写法​

class MyCompare 
{
public:
    bool operator()(int v1, int v2) {
        return v1 > v2;
    }
};
set<int,greater<int>> sets1; // 指定set从大到小排序
set<int,MyCompare> sets2; // 指定set从大到小排序

//注意：map是键值对，需要按照键排序，所以参数填的int
map<int,greater<int>> map1; // 指定map从大到小排序
map<int,MyCompare> map2; // 指定map从大到小排序