精华内容
下载资源
问答
  • leetcode 优先队列

    2019-10-06 19:32:11
    leetcode347 前k个高频元素 给定一个非空整数数组,返回其中出现频率前k高的元素 在外设置比较器,定义自己的比较方法,然后传给PriorityQueue private class Freq { public int e,freq; public Freq(int e,int...

    leetcode347 前k个高频元素

    给定一个非空整数数组,返回其中出现频率前k高的元素

    在外设置比较器,定义自己的比较方法,然后传给PriorityQueue

     private class Freq {
            public int e,freq;
            
            public Freq(int e,int freq){ //构造函数
                this.e=e;
                this.freq=freq;
            }
            
            
          // public int compareTo(Freq another){
          //       if(this.freq<another.freq)
          //           return -1;
          //       else if(this.freq > another.freq)
          //           return 1;
          //       else
          //           return 0;
          //   }
           
        }
        
        
        private class FreqComparator implements Comparator<Freq>{//实现接口
            public int compare(Freq a,Freq b){
                return a.freq - b.freq; //逻辑和上面的一样 谁的频率小让谁靠前
            }    
        }
        
        public List<Integer> topKFrequent(int[] nums, int k) {
            
            TreeMap<Integer,Integer> map=new TreeMap<>();
            for(int num:nums){ 
                if(map.containsKey(num))
                    map.put(num,map.get(num)+1);
                else
                    map.put(num,1); //这样map中就包含了每个元素和每个元素出现的频次
            }
            
            PriorityQueue<Freq> pq = new PriorityQueue<>(new FreqComparator());
            for(int key:map.keySet()){//用优先队列求出前k个元素
                if(pq.size()<k)
                    pq.add(new Freq(key,map.get(key)));
                else if(map.get(key)>pq.peek().freq){
                    pq.remove();
                    pq.add(new Freq(key,map.get(key)));
                    
                }
            }
            LinkedList<Integer> res = new LinkedList<>();
            while(!pq.isEmpty())
                res.add(pq.remove().e);
            return res;
            
        }
    

    以上专门给比较器做了一个类,用匿名类改变java内置的类型

      PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
                public int compare(Integer a, Integer b){
                   return map.get(a) - map.get(b);  //看的是a对应的频率和b对应频率的大小
                }
    

    java8以上内部类已经改变书写格式

     PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a,b)->map.get(a)-map.get(b)
    );
    

    最后的代码简化为

    class Solution {
        
    //     private class Freq {
    //         public int e,freq;
            
    //         public Freq(int e,int freq){ //构造函数
    //             this.e=e;
    //             this.freq=freq;
    //         }
            
            
          // public int compareTo(Freq another){
          //       if(this.freq<another.freq)
          //           return -1;
          //       else if(this.freq > another.freq)
          //           return 1;
          //       else
          //           return 0;
          //   }
           
       // }
        
        
        // private class FreqComparator implements Comparator<Freq>{//实现接口
        //     public int compare(Freq a,Freq b){
        //         return a.freq - b.freq; //逻辑和上面的一样 谁的频率小让谁靠前
        //     }    
        // }
        
        public List<Integer> topKFrequent(int[] nums, int k) {
            
            TreeMap<Integer,Integer> map=new TreeMap<>();
            for(int num:nums){ 
                if(map.containsKey(num))
                    map.put(num,map.get(num)+1);
                else
                    map.put(num,1); //这样map中就包含了每个元素和每个元素出现的频次
            }
            PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a,b)->map.get(a)-map.get(b)
            );
            
            for(int key:map.keySet()){//用优先队列求出前k个元素
                if(pq.size()<k)
                    pq.add(key);
                else if(map.get(key)>map.get(pq.peek())){
                    pq.remove();
                    pq.add(key);
                    
                }
            }
            
            LinkedList<Integer> res = new LinkedList<>();
            while(!pq.isEmpty())
                res.add(pq.remove());
            return res;  
        }
    }
    
    展开全文
  • 优先队列一、java内置优先队列的API二、LeetCode1.23. 合并K个升序链表2.215. 数组中的第K个最大元素总结 一、java内置优先队列的API 刷题时直接用java内置的优先级队列进行刷题 代码1:小根堆API public class ...


    一、java内置优先队列的API

    刷题时直接用java内置的优先级队列进行刷题

    代码1:小根堆API

    public class PriorityQueueTest {
        public static void main(String[] args) {
            PriorityQueue pq = new PriorityQueue(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });
            pq.add(13);
            pq.add(10);
            pq.add(12);
            System.out.println(pq.remove());//10
        }
    }
    

    Lambda表达式写法(推荐使用)

    PriorityQueue<Integer> pq = new PriorityQueue<>((o1 , o2) -> o1 - o2);//小跟堆
    PriorityQueue<Integer> pq = new PriorityQueue<>((o1 , o2) -> o2 - o1);//大根堆
    

    二、LeetCode

    1.23. 合并K个升序链表

    23. 合并K个升序链表

    代码如下:

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            //小顶堆
            PriorityQueue<ListNode> pq = new PriorityQueue<>((o1,o2) -> o1.val - o2.val);
            for(ListNode node : lists){
                if(node != null)
                    pq.add(node);
            }
            ListNode dummyNode = new ListNode(-1);
            ListNode curr = dummyNode;
            while(!pq.isEmpty()){
                ListNode minNode = pq.remove();
                curr.next = minNode;
                curr = curr.next;
                if(minNode.next != null){
                    pq.add(minNode.next);
                }
            }
            return dummyNode.next;
        }
    }
    

    2.215. 数组中的第K个最大元素

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

    代码如下(示例):

    class Solution {
        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> pq = new PriorityQueue<>(k);
            for(int i = 0 ; i < nums.length ; i++){
                if(pq.size() < k)   pq.add(nums[i]);
                else if(pq.size() == k){
                    if(pq.peek() < nums[i]){
                        pq.remove();
                        pq.add(nums[i]);
                    }
                }
            }
            return pq.peek();
        }
    }
    

    3.703. 数据流中的第 K 大元素

    703. 数据流中的第 K 大元素

    class KthLargest {
        private PriorityQueue<Integer> minHeap;
        private int k;
    
        public KthLargest(int k, int[] nums) {
            this.minHeap = new PriorityQueue<>();
            this.k = k;
            for(int i = 0 ; i < nums.length ; i++){
                if(minHeap.size() < k){
                    minHeap.add(nums[i]);
                }else if(minHeap.size() == k && nums[i] > minHeap.peek()){
                    minHeap.remove();
                    minHeap.add(nums[i]);
                }
            }
        }
        
        public int add(int val) {
            if(minHeap.size() < k){
                minHeap.add(val);
            }else if(minHeap.size() == k && val > minHeap.peek()){
                    minHeap.remove();
                    minHeap.add(val);
            }
            return minHeap.peek();
        }
    }
    

    4.295. 数据流的中位数

    295. 数据流的中位数

    class MedianFinder {
    
        private PriorityQueue<Integer> minHeap;
        private PriorityQueue<Integer> maxHeap;
    
        /** initialize your data structure here. */
        public MedianFinder() {
            minHeap = new PriorityQueue<>();
            maxHeap = new PriorityQueue<>((o1 , o2) -> o2 - o1);
        }
        
        public void addNum(int num) {
            if(maxHeap.isEmpty()){
                maxHeap.add(num);
                return;
            }
            //添加元素
            if(num > maxHeap.peek())    minHeap.add(num);
            else    maxHeap.add(num);
            //平衡两个堆的个数
            //要求:大根堆元素数量最多只能比小根堆的元素数量多一个
            //小根堆的元素个数要么和大根堆数量一样多,要么比大根堆少一个
            if(maxHeap.size() > minHeap.size() + 1){
                minHeap.add(maxHeap.poll());
            }else if(maxHeap.size() < minHeap.size()){
                maxHeap.add(minHeap.poll());
            }
        }
        
        public double findMedian() {
            if(maxHeap.size() > minHeap.size()){
                return maxHeap.peek();
            }else{
                return (maxHeap.peek() + minHeap.peek()) * 0.5;
            }
        }
    }
    

    总结

    提示:这里对文章进行总结:
    例如:以上就是今天要讲的内容,本文仅仅简单介绍了pandas的使用,而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。

    展开全文
  • 优先队列 优先队列可在O(1)时间内货的最大值,并且可以在O(logn)时间内取出最大值或插入任意值。 用数组表示时,位置 i 的结点的父结点位置一定是 i/2 ,它的两个子结点一定是 2i 和 2i+1。 class Heap { private: ...

    优先队列

    优先队列可在O(1)时间内货的最大值,并且可以在O(logn)时间内取出最大值或插入任意值。

    用数组表示时,位置 i 的结点的父结点位置一定是 i/2 ,它的两个子结点一定是 2i 和 2i+1。

    class Heap {
    private:
        vector<int> heap;
        // 上浮
        void swim(int pos) {
            while (pos > 1 && heap[pos / 2] < heap[pos]) {
                swap(heap[pos / 2], heap[pos]);
                pop /= 2;
            }
        }
        
        // 下沉
        void sink(int pos) {
            while (2 * pos <= heap.size()) {
                int i = 2 * pos;
                // 选择子结点更大的那个
                if (i < heap.size() && heap[i] < heap[i + 1]) {
                    ++i;
                }
                // 父结点与子结点比较
                if (heap[pos] >= heap[i]) {
                    break;
                }
                swap(heap[pos], heap[i]);
                pos = i;
            }
        }
    public:
    }
    // 获得最大值
    void top() {
        return heap[0];
    }
    
    // 插入任意值,把新的数字放在最后一位,然后上浮
    void push(int k) {
        heap.push_back(k);	// 在heap最后一个向量后面插入一个元素
        swim(heap.size() - 1);
    }
    
    // 删除最大值,把最后一个数字挪到开头,然后下沉
    void pop() {
        heap[0] = heap.back();	// back()返回heap的最后一个元素
        heap.pop_back();		// 删除heap的最后一个元素
        sink(0);
    }
    
    展开全文
  • 1046. Last Stone Weight class Solution { public: int lastStoneWeight(vector<int>& stones) { priority_queue<int> PQ(stones.begin(), stones.end()); while(PQ.size() >... PQ.po

    1046. Last Stone Weight

    在这里插入图片描述

    class Solution {
    public:
        int lastStoneWeight(vector<int>& stones) {
            priority_queue<int> PQ(stones.begin(), stones.end());
            while(PQ.size() > 1) {
                int y = PQ.top();
                PQ.pop();
                int x = PQ.top();
                PQ.pop();
                if(x != y) PQ.push(y - x);
            }
            if(PQ.empty()) return 0;  // 这里需要注意可能全部被清空,返回 0 
            return PQ.top();
        }
    };
    
    展开全文
  • 面试题 17.09. 第 k 个数 class Solution { public: typedef long long LL; int getKthMagicNumber(int k) { priority_queue<LL, vector<LL>, greater<LL> > PQ; PQ.push(1);... i
  • 295. Find Median from Data Stream class MedianFinder { public: /** initialize your data structure here.... // 简单讲,把所有元素分成大的一半和小的一半,分别用小顶堆和大顶堆存储,两个堆顶元素就是中间的...
  • 优先队列:维持一个有序的队列 23. 合并K个排序链表 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [  1-&gt;4-&gt;5,  1-&gt;3-&gt;4,  2-&gt...
  • 剑指 Offer 45. 把数组排成最小的数 class Solution { public: struct cmp{ bool operator ()(string str1, string str2) { return str1 + str2 > str2 + str1; } }; string minNumber... priority_que
  • 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/get-kth-magic-number-lcci 题解: 这道题,想法大概就是从提示来的 先建立一个数组x储存0~k的结果,初始化为1 然后建立三个.
  • leetcode优先队列题目集合

    千次阅读 2019-08-18 18:52:45
    一、在N个元素中选出前M个元素(N远大于M时) 在1,000,000个元素中选出前100...具体实现:使用优先队列维护M个元素,即每次向优先队列中加入一个元素时,需要将当前队列中的最小元素替换出去,保证队列中的M个元素...
  • 分析:借由广度优先算法的思想,先循环根节点的海域,接着是根节点外面的第一层海域,然后是与第一层相邻的第二层海域,以此类推,探索过的位置不需要探索,直到探索完全部海域。 如果用树的形式来解释,就是按照:A...
  • Python-Leetcode-优先队列

    2020-07-14 20:54:03
    https://www.sohu.com/a/256022793_478315【优先队列】 堆的基本要求是堆中所有结点的值必须大于或等于(或小于或等于)其孩子结点的值。除此以外,所有叶子结点都是处于第 h 或 h - 1层(h为树的高度),其实堆也是...
  • 题目 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接...来源:力扣(LeetCode) 链接:https://leetc
  • 仍然是广度优先搜索,广度优先搜索需要结合队列。广度优先搜索是有模板的,即把第一个节点加入队列,然后找该节点的相邻的节点,是为第一层,第一层取完了,判断完了,再取第二层,进行判断。判断过的节点,要注意...
  • 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/clone-graph 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 分析 克隆图,仍然以DFS为解法。遍历每一个节点,如果没访问...
  • 题目 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16,...仍然是广度优先搜索BFS,注意step的增加,要每一轮或者说每一圈搜索结束后,再增长。 BFS三大核心,visited,queue,step。 解法 func numSquares(n int
  • 优先队列保存元素,然后求前k大的。 AC代码: struct Pair{ int a; int b; Pair(int _a, int _b) : a(_a), b(_b) {} bool operator<(const Pair &x) const { return b > x.b; } bool ...
  • } } 为了再次学习队列知识,把用优先队列的解法2放一下 在选择每一轮中的任务时,我们也可以用优先队列(堆)来代替排序。在一开始,我们把所有的任务加入到优先队列中。在每一轮,我们从优先队列中选择最多 n + 1 ...
  • 点击打开链接class Solution { public: struct cmp{ bool operator()(pair&lt;int, int&gt;num1, pair&lt;int, int&gt;num2){ return num1.first +num1.second &gt;... ...
  • 1.使用优先队列来做 2.sort然后增删 这里使用的是第一个思路 c++代码 class Solution { public: int lastStoneWeight(vector<int>& stones) { priority_queue<int> pq; for (int s : stones) pq....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,384
精华内容 4,553
关键字:

leetcode优先队列