Skip to content

Latest commit

 

History

History
795 lines (652 loc) · 19.4 KB

5.heap_leetcode.md

File metadata and controls

795 lines (652 loc) · 19.4 KB
Raw

Leetcode Heap 刷题

做题的时候 记住堆的性质：每次pop都能给我们最大/小值即可 不用关心什么数组 完全二叉树啥的

template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last ); (until C++20)
template< class RandomIt >
constexpr void pop_heap( RandomIt first, RandomIt last ); (since C++20) (2)	
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp ); (until C++20)
template< class RandomIt, class Compare >
constexpr void pop_heap( RandomIt first, RandomIt last, Compare comp );(since C++20)

由于c++并没有堆相关的容器（priority_queue不是哦，他无法返回vector，很不利于我们做题）

所以就用到了algorithm里的heap相关操作

时间复杂度

At most $2×log(N)$ comparisons where N=std::distance(first, last).

A new element can be added using std::push_heap, in $log(n)$ time. The first element can be removed using std::pop_heap, in $log(n)$ time.

#剑指 Offer 40 最小的k个数

找出数组中最小的k个数

思路：

假设有一个大小为k的集合

遍历数组

每次如果新元素比集合里最大的都大

就不让他进集合

如果没那个大，就交换最大的和新元素

因为要维护一个集合的最大值

所以要用到大顶堆

class Solution {
public:
    template<typename T>
    class Heap : public vector<T> {
    public :
        template<typename Func_T>
        Heap(Func_T cmp) : cmp(cmp) {}
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() { return this->at(0); } 
    private :
        std::function<bool(T, T)> cmp;
    };
	vector<int> getLeastNumbers(vector<int>& arr, int k) {
        Heap<int> h{less<int>()};
        // 传入<就是大顶堆
        // 谁大谁出去
        // 在push的时候就完成了排序的操作，都得益于前面的封装
        for (auto x : arr) {
            h.push(x);
            // 超过了k个 最大的就出去
            if (h.size() > k) h.pop();
        }
        return h;
    }  
};

当然用priority_queue也是可以的啦

值不多要进行一个队列转数组的操作

priority默认是大顶堆

 vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int> h;
        vector<int> ret;
        for (auto x : arr) {
            h.push(x);
            if (h.size() > k) h.pop();
        }
        // 队列转数组的操作
        for (int i = 0; i < k; i++) {
            ret.push_back(h.top());
            h.pop();
        }
        return ret;
    }

#1046 最后一块石头的重量

class Solution {
public:
    template<typename T>
    class Heap : public vector<T> {
    public :
        template<typename Func_T>
        Heap(Func_T cmp) : cmp(cmp) {}
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() { return this->at(0); } 
    private :
        std::function<bool(T, T)> cmp;
    };
    int lastStoneWeight(vector<int>& stones) {
        Heap<int> h{less<int>()};
        for (auto x : stones) {
            h.push(x);
        }
        while (h.size() > 1) {
            int y = h.top(); h.pop();
            int x = h.top(); h.pop();
            if (x == y) continue;
            h.push(y - x);
        }
        if (h.size() == 0) return 0;
        return h.top();
    }
};

学堆和学太极是类似的，忘掉他的那些虚的东西，就留着维护最值、最值、最值！

#剑指 Offer II 059 数据流的第K大元素

class KthLargest {
public:
    template<typename T>
    class Heap : public vector<T> {
    public :
        template<typename Func_T>
        Heap(Func_T cmp) : cmp(cmp) { }
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() { return this->at(0); }
    private :
        function<bool(T, T)> cmp;
        };
    
    Heap<int> h{greater<int>()};
    int k;
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (auto x : nums) {
            add(x);
        }
        return ;
    }
    
    int add(int val) {
        h.push(val);
        if (h.size() > k) h.pop();
        return h.top();
    }
};

#215 数组中的第K个最大元素

class Solution {
public:
    template<typename T>
    class Heap : public vector<T> {
    public :
        template<typename Func_T>
        Heap(Func_T cmp) : cmp(cmp) { }
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() { return this->at(0); }
    private :
        function<bool(T, T)> cmp;
    };
    int findKthLargest(vector<int>& nums, int k) {
        // 因为是K大的
        // 所以是小顶堆
        // 就是谁比top小，谁就别进来
        Heap<int> h{greater<int>()};
        for (auto x : nums) {
            h.push(x);
            if (h.size() > k) h.pop();
        }
        return h.top();      
    }
};

#373 查找和最小的 K 对数字

class Solution {
public:
    template<typename T>
    class Heap : public vector<T> {
    public :
        template<typename Func_T>
        Heap(Func_T cmp) : cmp(cmp) { }
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() { return this->at(0); }
    private :
        function<bool(T, T)> cmp;
    };
    struct CMP {
        bool operator()(vector<int> a, vector<int> b) {
            return a[0] + a[1] < b[0] + b[1];
        }
    };
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        CMP less_than;
        Heap<vector<int>> h{less_than};
        vector<int> temp(2);
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {
                temp[0] = nums1[i], temp[1] = nums2[j];
                // 利用nums1，2的有序性
                // nums2没必要全部遍历完
                // 如果遍历到一半 满足了k个
                // 终止就可以了
                if (h.size() < k || less_than(temp, h.top())) {
                    h.push(temp);
                    if (h.size() > k) h.pop();
                } else {
                    break;
                }
            }
        }
        return h;      
    }
};

第二种方法和上一个思路是反着的

因为stl中的优先队列不是vector

所以需要构建一个小顶堆

每次弹一个，再入一个

因为是有序的，所以从最小的开始

弹k个出来就够了

class Solution {
public:
    // 三元组存放
    // sum和两个下标
    struct triple {
        int sum;
        int first_ind;
        int second_ind;

        // 重载 < 变成 > 这样实现小顶堆
        bool operator<(const triple &a) const {
            return this->sum > a.sum;
        }
    };
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        
        vector<vector<int>> ret;
        priority_queue<triple> q;
        // 我们用1的每一位去匹配2的0
        for (int i = 0; i < nums1.size(); i++) {
            q.push(triple{nums1[i] + nums2[0], i, 0});
        }
        // 现在堆中有了i个元素
        // 谁比我小谁就出堆 出k个就ok了
        while (!q.empty() && k--) {
            auto get = q.top();
            q.pop();
            ret.push_back(vector<int>{nums1[get.first_ind], nums2[get.second_ind]});
            // 如果2没全都进来，就继续进
            if (get.second_ind < nums2.size() - 1) {
                q.push(triple{nums1[get.first_ind] + nums2[get.second_ind + 1], get.first_ind, get.second_ind + 1});
            }
        }
        return ret;
    }
};

reference

#347 前 K 个高频元素

下面三个题都是一样的类型

需要自行建立一个映射 从数据到数据数量的映射

所以实现的方法都大同小异

class Solution {
public:
    template<typename T>
    class Heap : public vector<T> {
    public :
        template<typename Func_T>
        Heap(Func_T cmp) : cmp(cmp) { }
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() { return this->at(0); }
    private :
        function<bool(T, T)> cmp;
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        for (auto x : nums) {
            m[x] += 1;
        }
        auto cmp = [&m](int a, int b) -> bool { 
            // 小顶堆 因为我想留下最大值
            return m[a] > m[b];
        };
        Heap<int> h{cmp};
        for (auto x : m) {
            h.push(x.first);
            if (h.size() > k) h.pop();
        }
        return h;
    }
};

#451 根据字符出现频率排序

这个最后还要弹堆组成一个新的序列

堆的大小没有限制

class Solution {
public:
    template<typename T>
    class Heap : public vector<T> {
    public :
        template<typename Func_T>
        Heap(Func_T cmp) : cmp(cmp) {}
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() { return this->at(0); }
    private :
        function<bool(T, T)> cmp;
    };
    string frequencySort(string s) {
        unordered_map<char, int> freq;
        for (auto x : s) freq[x] += 1;
        auto cmp = [&freq](char a, char b) -> bool {
            if (a - b) return freq[a] < freq[b];
            return a < b;
        };
        Heap<char> h{cmp};
        for (auto x : freq) {
            h.push(x.first);
        }
        string ret;
        while (!h.empty()) {
            while(freq[h.top()]--) {
                ret.push_back(h.top());
            }
            h.pop();
        }
        return ret;
    }
};

#692 前K个高频单词

class Solution {
public:
    // 转化成求K大数字
    // 即统计各个单词的频率
    // 频率入小顶堆
    template <typename T>
    class Heap : public vector<T> {
    public :
        template<typename Func_T>
        Heap(Func_T cmp) : cmp(cmp) {}
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() { return this->at(0); }
    private :
        function<bool(T, T)> cmp;
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        // freq是一个词频统计的数组
        // 这个数组中单词是没有重复的
        // 单词->词频的唯一映射
        unordered_map<string, int> freq;
        for (auto x : words) freq[x] += 1;
        auto cmp = [&freq](string a, string b) -> bool {
            // 比较顺序：首先按频次高的来
            // 频次一样按字典序来
            if (freq[a] - freq[b]) return freq[a] > freq[b];
            return a < b;
        };
        Heap<string> h{cmp};
        // 所以遍历的时候要遍历freq数组
        // words数组是有重复的！
        for (auto x : freq) {
            h.push(x.first);
            if (h.size() > k) h.pop();
        }
        // 最后按照词频 + 字典序列再次排序
        sort(h.begin(), h.end(), cmp);
        return h;
    }
};

#295 数据流的中位数

维护中位数

中间这个数，可以看到后半段的最小值（后半段是小顶堆）

可以看到前半段的最大值（前半段是大顶堆）

然后如果任意一段元素多了，就挪动元素到另一段

从而达到两段长度类似的效果

思考思路的时候不要考虑程序的细节

然后这种结构叫对顶堆

class MedianFinder {
public:
    template<typename T>
    class heap : public vector<T> {
    public :
        template<typename Func_T>
        heap(Func_T cmp) : cmp(cmp) { }
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        T pop() {
            T ret = this->top();
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ret;
        }
        T &top() { return this->at(0); }
    private :
        function<bool(T, T)> cmp;
    };
    heap<int> h1, h2;
    MedianFinder() : h1{less<int>()}, h2{greater<int>()} { }
    
    void addNum(int num) {
        if (h1.size() == 0 || num <= h1.top()) {
            h1.push(num);
        } else {
            h2.push(num);
        }
        // 我们是假设h1 = h2 + 1或者h1 == h2
        // 打破这个关系就要变
        if (h2.size() > h1.size()) {
            h1.push(h2.pop());
        }
        if (h1.size() == h2.size() + 2) {
            h2.push(h1.pop());
        }
        return ;
    }
    
    double findMedian() {
        int n = h1.size() + h2.size();
        if (n % 2 == 1) return h1.top();
        return (h1.top() + h2.top()) * 1.0 / 2;
    }
};

#264 丑数 II

丑数 就是只包含质因数 2、3 和/或 5 的正整数

class Solution {
public:
    template<typename T>
    class heap : public vector<T> {
    public :
        template<typename Func_T>
        heap(Func_T cmp) : cmp(cmp) {}
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() { return this->at(0); }
    private :
        function<bool(T, T)> cmp;
    };
    int nthUglyNumber(int n) {
        heap<int64_t> h{greater<int64_t>()};
        int64_t ans = 0;
        h.push(1);
        while (n--) {
            ans = h.top();
            h.pop();
            // 每次用最小的值
            // 并且都乘它最大的素因子
            // 这个思想很接近素数筛
            // 然后循环n次不就是第n个了吗
            // 但是这样堆内其他的元素就没用了
            if (ans % 5 == 0) {
                h.push(ans * 5);
            } else if (ans % 3 == 0) {
                h.push(ans * 5);
                h.push(ans * 3);
            } else {
                h.push(ans * 5);
                h.push(ans * 3);
                h.push(ans * 2);
            }
        }
        return ans;
    }
};

当然我们知道这样做的效率是比较低的

肯定是用三指针比较快

class Solution {
public:
    int64_t nthSuperUglyNumber(int n, vector<int>& primes) {
        // 设置n个指针 
        vector<int> p(primes.size());
        vector<int64_t> data;
        data.push_back(1);
        int64_t ans = 1;
        while (data.size() != n) {
            ans = primes[0] * data[p[0]];
            for (int i = 0; i < primes.size(); i++) {
                ans = min(ans, primes[i] * data[p[i]]);
            }
            for (int i = 0; i < primes.size(); i++) {
                if (primes[i] * data[p[i]] == ans) p[i]++;
            }
            data.push_back(ans);
        }
        return ans;
    }
};

#1801 积压订单中的订单总数

class Solution {
public:
    template<typename T>
    class Heap : public vector<T> {
    public :
        template<typename Func_T>
        Heap(Func_T cmp) : cmp(cmp) {}
        void push(const T &a) {
            this->push_back(a);
            push_heap(this->begin(), this->end(), cmp);
            return ;
        }
        void pop() {
            pop_heap(this->begin(), this->end(), cmp);
            this->pop_back();
            return ;
        }
        T &top() {
            return this->at(0);
        }
    private :
        function<bool(T, T)> cmp;
    };
    struct CMP1 {
        bool operator()(vector<int> a, vector<int> b) {
            return a[0] < b[0];
        }
    };
    struct CMP2 {
        bool operator()(vector<int> a, vector<int> b) {
            return a[0] > b[0];
        }
    };
    nt getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        Heap<vector<int>> buy{CMP1()}, sell{CMP2()};
        vector<int> temp(2);
        for (auto x : orders) {
            //  为购买订单
            if (x[2] == 0) {
                // 购买数量不为0，有销售订单，并且销售价格小于购买价格
                while (x[1] != 0 && sell.size() && sell[0][0] <= x[0]) {
                    // 当前订单还剩下多少单，销售订单还剩多少单
                    int cnt = min(x[1], sell[0][1]);
                    x[1] -= cnt;
                    sell[0][1] -= cnt;
                    if (sell[0][1] == 0) sell.pop();
                }
                if (x[1] != 0) buy.push(x);
            } else {
                while (x[1] != 0 && buy.size() && buy[0][0] >= x[0]) {
                    // 当前订单还剩下多少单，销售订单还剩多少单
                    int cnt = min(x[1], buy[0][1]);
                    x[1] -= cnt;
                    buy[0][1] -= cnt;
                    if (buy[0][1] == 0) buy.pop();
                }
                if (x[1] != 0) sell.push(x);
            }
        }
        int sum = 0;
        int mod = 1e9 + 7;
        for (auto x : buy) {
            sum = (sum + x[1]) % mod;
        }
        for (auto x : sell) {
            sum = (sum + x[1]) % mod;
        }
        return sum;

    }
};