当前位置: 首页 > news >正文

ui设计参考网站有哪些/seo云优化软件破解版

ui设计参考网站有哪些,seo云优化软件破解版,php做商城网站步骤,购物网站开发的难点专栏:Java数据结构秘籍 个人主页: 目录 一、优先级队列常用接口 1.1. 优先级队列的特性 1.2. 优先级队列的使用 1.3. 最小K个数 二、堆的应用 2.1. 堆排序 一、优先级队列常用接口 1.1. 优先级队列的特性 Java集合框架中提供了PriorityQueue和Pri…

专栏:Java数据结构秘籍

个人主页:

目录

一、优先级队列常用接口

1.1. 优先级队列的特性

1.2. 优先级队列的使用

1.3. 最小K个数

二、堆的应用

2.1. 堆排序


一、优先级队列常用接口

1.1. 优先级队列的特性

        Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列, PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的。注意,使⽤PriorityQueue时必须导⼊PriorityQueue所在的包。

import java.util.PriorityQueue;

        从上图中我们可以看出,PriorityQueue实现了AbstractQueue接口,我们来看一下PriorityQueue的源码里面继承了AbstractQueue类。而AbstractQueue类里面继承AbstractCollection类和实现了Queue接口。

public class PriorityQueue<E> extends AbstractQueue<E>implements java.io.Serializable {
public abstract class AbstractQueue<E>extends AbstractCollection<E>implements Queue<E>

        插入元素:

import java.util.PriorityQueue;public class Test {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(10);queue.offer(4);queue.offer(7);}
}

        offer的源码如下,从下面的逻辑中可以看出,它的向上调整是一个一个实现的,而不是直接去调整一个数组,所以下面的时间复杂度是O(n) = nlogn

    public boolean offer(E e) {if (e == null)throw new NullPointerException();modCount++;int i = size;if (i >= queue.length)grow(i + 1);siftUp(i, e);size = i + 1;return true;}

注意事项:

  • PriorityQueue中放置的元素必须要能够⽐较⼤⼩,不能插⼊⽆法⽐较⼤⼩的对象,否则会抛出 ClassCastException异常。要想实现就必须实现Compareble的接口。
class Student{}public class Test {public static void main(String[] args) {PriorityQueue<Student> queue = new PriorityQueue<>();queue.offer(new Student());}
}

  • 不能插⼊null对象,否则会抛出NullPointerException。

        public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(null);}

    • “没有容量限制”,可以插⼊任意多个元素,其内部可以⾃动扩容。
    • 插入和删除的时间复杂度为O(n) = nlogn

    1.2. 优先级队列的使用

    构造器功能
    PriorityQueue()
    创建一个空的优先级队列,默认容量为11
    PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列
    PriorityQueue(Collection<? extends E> c)用一个集合来创建优先级队列
    import java.util.ArrayList;
    import java.util.PriorityQueue;public class Solution {public static void main(String[] args) {PriorityQueue<Integer> queue1 = new PriorityQueue<>();PriorityQueue<Integer> queue2 = new PriorityQueue<>();ArrayList<Integer> list = new ArrayList<>();list.add(4);list.add(3);list.add(2);list.add(1);PriorityQueue<Integer> queue3 = new PriorityQueue<>(list);System.out.println(queue3);}
    }
    
    //PriorityQueue所实现的成员变量,默认容量为11
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    PriorityQueue<Character> queue3 = new PriorityQueue<>(list);

            如果优先级队列里的泛型不匹配,就会出现报错。我们该如何知道这里的类型呢?我们来看一下PriorityQueue构造方法的源码:Collection可以接受任何类型,后面可以继承它本身的类型或者是它的子类。而上面的Collection接收为ArrayList,E接收为Character,就会产生报错。

        public PriorityQueue(Collection<? extends E> c)
    方法名功能
    boolean offer(E e)插入元素,成功返回true。如果插入元素为空,抛出异常
    E peek()获取优先级最高的元素
    E poll()移除优先级最高的元素并返回
    int size()获取有效元素的个数
    void clear()清空
    boolean isEmpty()检查优先级队列是否为空
    public class Solution {public static void main(String[] args) {PriorityQueue<Integer> queue1 = new PriorityQueue<>();queue1.offer(27);queue1.offer(15);queue1.offer(19);queue1.offer(28);queue1.offer(34);queue1.offer(49);System.out.println(queue1);System.out.println(queue1.isEmpty());System.out.println(queue1.size());System.out.println(queue1.peek());System.out.println(queue1.poll());queue1.clear();}
    }
    public class Solution {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(10);queue.offer(5);}
    }

            默认情况下,PriorityQueue队列是⼩堆,如果需要大堆需要用户提供比较器。我们来看一下offer里面sifup所实现的源码。当我们传入一个10的时候,通过Comparable进行强转,在传入数组。方法里面的k作为数组的下标,每传入一个元素,进行比较,而里面的k调用了compareTo接口

        public boolean offer(E e) {if (e == null)throw new NullPointerException();modCount++;int i = size;if (i >= queue.length)grow(i + 1);siftUp(i, e);size = i + 1;return true;}
        private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x, queue, comparator);elsesiftUpComparable(k, x, queue);}private static <T> void siftUpComparable(int k, T x, Object[] es) {Comparable<? super T> key = (Comparable<? super T>) x;while (k > 0) {int parent = (k - 1) >>> 1;Object e = es[parent];if (key.compareTo((T) e) >= 0)break;es[k] = e;k = parent;}es[k] = key;}

            我们来看一下Integer里面的源码,在Structure里面找到compare(int ,int),因为10>5,进不来上面的循环,就可以走下面的代码,再把0下标给到5元素,从而实现小根堆。

        public int compareTo(Integer anotherInteger) {return compare(this.value, anotherInteger.value);}
        public static int compare(int x, int y) {return (x < y) ? -1 : ((x == y) ? 0 : 1);}

            如果没有进入if语句,则相当于进行交换。我们如果想实现大根堆,就要走break这条语句。源码的Integer写死了,我们无法在这里进行修改,此时就需要用到比较器。

    import java.util.Comparator;
    import java.util.PriorityQueue;class BigTmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
    }public class Solution {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>(new BigTmp());queue.offer(10);queue.offer(5);System.out.println(queue.peek());}
    }
    

    1.3. 最小K个数

            第一种解法,我们可以利用冒泡排序,排完序之后,找前k个数;第二种解法,利用小根堆,找出前k个数。

    class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueue<Integer> queue = new PriorityQueue<>();for (int i = 0; i < arr.length; i++) {queue.offer(arr[i]);}int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}
    }

            除此之外,还有第三种解法,就是利用大根堆。先建立一个大小为k的大根堆,从数组的第k+1个元素开始遍历数组,如果数组元素比堆顶元素小,则交换,遍历结束之后,大根堆里的元素就是最小k个数。

    import java.util.Arrays;
    import java.util.PriorityQueue;
    import java.util.Scanner;public class Solution {public int[] smallestK(int[] arr, int k){PriorityQueue<Integer> queue = new PriorityQueue<>();for (int i = 0; i < arr.length; i++) {queue.offer(arr[i]);}for (int i = k; i < arr.length; i++) {int val = queue.peek();if(val > arr[i]){queue.poll();queue.offer(arr[i]);}}int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNextInt()){int size = in.nextInt();int[] arr = new int[size];for (int i = 0; i < size; i++) {arr[i] = in.nextInt();}int k = in.nextInt();Solution solution = new Solution();int[] ret = solution.smallestK(arr,k);System.out.println(Arrays.toString(ret));}}
    }

    二、堆的应用

    2.1. 堆排序

            如果我们要使用堆排序的思想,是采用大根堆还是小根堆呢?如果采用小根堆,那么栈顶元素就是最小的,只需要弹出依次元素即可,空间复杂度也会变大,因为还需要额外的数组来接收弹出的元素。如果采用大根堆,我们的思路是将堆顶元素与最后一个元素进行交换,再把这棵树调整为大根堆。

            完整代码实现:

    public class MyHeap {public int[] elem;public int usedSize;public MyHeap() {elem = new int[10];}public void Initial(int[] array) {for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}}public void CreateHeap() {for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {ShiftDown(parent, usedSize);}}private void ShiftDown(int parent, int usedSize) {int child = 2 * parent + 1;while (child < usedSize) {if (child + 1 < usedSize && elem[child] < elem[child + 1]) {child++;}if (elem[child] > elem[parent]) {swap(parent,child);parent = child;child = 2 * parent + 1;} else {break;}}}private void swap(int i, int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}public void HeapSort(){int end = usedSize - 1;while (end > 0) {swap(0,end);ShiftDown(0,end);end--;}}
    }
    public class Test {public static void main(String[] args) {int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};MyHeap heap = new MyHeap();heap.Initial(array);heap.CreateHeap();heap.HeapSort();System.out.println();}
    }
    http://www.whsansanxincailiao.cn/news/30288288.html

    相关文章:

  1. 最专业的外贸网站建设公司/同城推广引流平台
  2. 大连品牌网站建设公司/如何建立网页
  3. wordpress csv导入/企业网站优化哪家好
  4. 员工管理网站模板/武汉seo诊断
  5. 外贸商城 网站建设/b站广告投放平台入口
  6. 专门做隐形眼镜的网站/58网络推广
  7. 视频网站内容规划/bt种子磁力搜索引擎
  8. 重庆大型网站建设重庆网站制作/seo搜索排名优化
  9. 做飞机票预订网站/注册商标查询官网入口
  10. 如何查询个人名下企业/seo关键词优化报价价格
  11. 如何确定网站被k/广州推动优化防控措施落地
  12. 汉中免费做网站公司/如何将网站的关键词排名优化
  13. 杭州公司注册地址/关键词优化案例
  14. 长沙有哪些做的好一点的网站/浙江网站推广运营
  15. 响应式网站发展/谷歌官网首页
  16. 余姚做轴承网站/设计网站接单
  17. h5怎么制作进入下一页/青岛百度快速排名优化
  18. 建设厅网站更改登陆密码/优化seo招聘
  19. 网站建设及维护费算业务宣传费/免费网站注册com
  20. 网站建设与规划实训总结/seo网络推广案例
  21. 广州天河 网站建设/单页网站模板
  22. 自己怎么免费做网站/免费网站服务器
  23. 聊城网站建设企业/网络广告营销方案
  24. 商丘手机网站制作/央视新闻最新消息今天
  25. 个人博客网站模板源码/广东网站se0优化公司
  26. 在线网站推广工具/seo关键词排名优化软件
  27. 个人做网站用哪个主机好/长沙网站优化方案
  28. 建设食品网站/百度 个人中心首页
  29. 潍坊搜易网站建设/重庆网络推广专员
  30. ps做网站的优点/什么叫优化关键词