1. 堆(优先级队列)

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

完全二叉树：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

每一棵子树的根结点最大的堆(即根节点大于等于子节点)叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆

2. 优先级队列(PriorityQueue)与比较器

  2.     public static class MyComparator implements Comparator<Integer> {
  4.         // 负数,第一个参数在前
  5.         // 正数,第二个参数在前
  6.         // 0,不作交换
  7.         @Override
  8.         public int compare(Integer o1, Integer o2) {
  9.             if (o1 > o2) {
  10.                 return -1;
  11.             } else if (o2 > o1) {
  12.                 return 1;
  13.             } else {
  14.                 return 0;
  15.             }
  16.         }
  18.     }
  20.     public static void main(String[] args) {
  21.         PriorityQueue<Integer> heap = new PriorityQueue<>(); // 默认小根堆的优先队列
  22.         heap.add(5);
  23.         heap.add(3);
  24.         heap.add(8);
  25.         heap.add(1);
  26.         System.out.println(heap.peek()); // 查看队头
  27.         for (Integer integer : heap) {
  28.             System.out.print(integer + " ");
  29.         }
  30.         System.out.println();
  32. //        PriorityQueue<Integer> heap2 = new PriorityQueue<>(new MyComparator()); // 大根堆的优先队列 构造时传入比较器
  33.         PriorityQueue<Integer> heap2 = new PriorityQueue<>((o1,o2)-> o2-o1); // 大根堆的优先队列 构造时传入比较器
  34.         heap2.add(5);
  35.         heap2.add(3);
  36.         heap2.add(8);
  37.         heap2.add(1);
  38.         System.out.println(heap2.peek()); // 查看队头
  39.         for (Integer integer : heap2) {
  40.             System.out.print(integer + " ");
  41.         }
  42.         System.out.println();
  44.     }

3. 数组实现大根堆

  1.     public static class MyMaxheap {
  2.         private int[] heap;
  3.         private final int limit; // heap的最大值
  4.         private int size; // heap当前大小
  6.         public MyMaxheap(int limit) {
  7.             this.limit = limit;
  8.             heap = new int[limit];
  9.             size = 0;
  10.         }
  12.         public boolean isEmpty() {
  13.             return size == 0;
  14.         }
  16.         public boolean isFull() {
  17.             return size == limit;
  18.         }
  20.         public void push(int value) {
  21.             if (size == limit) {
  22.                 throw new RuntimeException("当前堆已满!");
  23.             }
  24.             heap[size] = value;
  25.             heapInsert(heap, size++);
  26.         }
  28.         public int pop() {
  29.             int ans = heap[0];
  30.             swap(heap, 0, --size);
  31.             heapify(heap, 0, size);
  32.             return ans;
  33.         }
  35.         // 向下沉
  36.         private void heapify(int[] heap, int index, int size) {
  37.             int left = index * 2 + 1;
  38.             while (left < size) { // 存在左孩子时 有可能存在右孩子
  39.                 int largest = left + 1 < size && heap[left + 1] > heap[left] ? left + 1 : left; // 判断是否有右孩子 并且挑出最大值的下标
  40.                 largest = heap[largest] > heap[index] ? largest : index; // 如果孩子大于当前push节点 则赋值下标 否则下标为index
  41.                 if (largest == index) { // 最大值是自身 无需下沉
  42.                     break;
  43.                 }
  44.                 swap(heap, largest, index); // 存在孩子大于当前push节点 交换并下沉(使最大值孩子成为根节点,push节点成为孩子)
  45.                 index = largest; // 继续与下面孩子进行比较
  46.                 left = index * 2 + 1; // 是否存在左孩子 由while循环决定
  48.             }
  50.         }
  52.         private void swap(int[] heap, int i, int j) {
  53.             int temp = heap[i];
  54.             heap[i] = heap[j];
  55.             heap[j] = temp;
  56.         }
  58.         // 向上移动
  59.         private void heapInsert(int[] heap, int index) {
  60.             while (heap[index] > heap[(index - 1) / 2]) { // 如果当前push的节点比它的根节点大则
  61.                 swap(heap, index, (index - 1) / 2); // 进行交换
  62.                 index = (index - 1) / 2;
  63.             }
  64.         }
  66.     }
  68.     public static class RightMaxHeap {
  69.         private int[] arr;
  70.         private final int limit;
  71.         private int size;
  73.         public RightMaxHeap(int limit) {
  74.             arr = new int[limit];
  75.             this.limit = limit;
  76.             size = 0;
  77.         }
  79.         public boolean isEmpty() {
  80.             return size == 0;
  81.         }
  83.         public boolean isFull() {
  84.             return size == limit;
  85.         }
  87.         public void push(int value) {
  88.             if (size == limit) {
  89.                 throw new RuntimeException("heap is full");
  90.             }
  91.             arr[size++] = value;
  92.         }
  94.         public int pop() {
  95.             int maxIndex = 0;
  96.             for (int i = 1; i < size; i++) {
  97.                 if (arr[i] > arr[maxIndex]) {
  98.                     maxIndex = i;
  99.                 }
  100.             }
  101.             int ans = arr[maxIndex];
  102.             arr[maxIndex] = arr[--size];
  103.             return ans;
  104.         }
  106.     }
  108.     public static class MyComparator implements Comparator<Integer> {
  110.         @Override
  111.         public int compare(Integer o1, Integer o2) {
  112.             return o2 - o1;
  113.         }
  115.     }
  117.     public static void main(String[] args) {
  119.         // 小根堆
  120.         PriorityQueue<Integer> heap = new PriorityQueue<>(new MyComparator());
  121.         heap.add(5);
  122.         heap.add(5);
  123.         heap.add(5); //堆是可以添加重复元素的
  124.         heap.add(3);
  125.         // 5 , 3
  126.         System.out.println(heap.peek());
  127.         heap.add(7);
  128.         heap.add(0);
  129.         heap.add(7);
  130.         heap.add(0);
  131.         heap.add(7);
  132.         heap.add(0);
  133.         System.out.println(heap.peek());
  134.         while (!heap.isEmpty()) {
  135.             System.out.println(heap.poll());
  136.         }
  138.         int value = 1000;
  139.         int limit = 100;
  140.         int testTimes = 1000000;
  141.         for (int i = 0; i < testTimes; i++) {
  142.             int curLimit = (int) (Math.random() * limit) + 1;
  143.             MyMaxheap my = new MyMaxheap(curLimit);
  144.             RightMaxHeap test = new RightMaxHeap(curLimit);
  145.             int curOpTimes = (int) (Math.random() * limit);
  146.             for (int j = 0; j < curOpTimes; j++) {
  147.                 if (my.isEmpty() != test.isEmpty()) {
  148.                     System.out.println("Oops!");
  149.                 }
  150.                 if (my.isFull() != test.isFull()) {
  151.                     System.out.println("Oops!");
  152.                 }
  153.                 if (my.isEmpty()) {
  154.                     int curValue = (int) (Math.random() * value);
  155.                     my.push(curValue);
  156.                     test.push(curValue);
  157.                 } else if (my.isFull()) {
  158.                     if (my.pop() != test.pop()) {
  159.                         System.out.println("Oops!");
  160.                     }
  161.                 } else {
  162.                     if (Math.random() < 0.5) {
  163.                         int curValue = (int) (Math.random() * value);
  164.                         my.push(curValue);
  165.                         test.push(curValue);
  166.                     } else {
  167.                         if (my.pop() != test.pop()) {
  168.                             System.out.println("Oops!");
  169.                         }
  170.                     }
  171.                 }
  172.             }
  173.         }
  174.         System.out.println("finish!");
  176.     }

4. 堆排序

  1. 0~N 范围上变成大根堆，heapsize = 需排序数组长度
  2. 0 与 N 进行交换值
  3. 0~N-1 范围上变成大根堆，再进行 0与 N-1 交换，直到heapsize— 成为1(只剩下0~0没进行heapInster)

时间复杂程度:O(N*logN)

不断的缩小要排序数组的大小 每次将堆顶(大根堆即最大值)放置到末尾 并断开连接(下次排序此元素不参与)

4.1. 自底向上变成大根堆

在上面堆排序我们使用的从根节点到底部叶子节点 headpSort 时间复杂程度为:O(N*logN)

而我们从底部headpSort时 叶子节点只需根自己比较即是大根堆 时间复杂程度为:O(N) 因为大量的节点存在于叶子节点N个数就要操作N*logN次 而自底向上只需要 N次操作

注意：自底向上建堆必须给定一个具体数组（必须知晓叶子节点），无法像自顶向下建堆灵活一个一个建立

  1. public static void heapSort(int[] arr) {
  2.         if (arr == null || arr.length < 2) {
  3.             return;
  4.         }
  6.         // 自顶向下插入堆 O(N*logN)
  7. //     for (int i = 0; i < arr.length; i++) {
  8. //        heapInster(arr,i);
  9. //    }
  11.         // 自底向上推进堆 O(N)
  12.         for (int i = arr.length - 1; i >= 0; i--) { // 整个堆的最后的叶子节点此操作 无需下沉
  13.             heapify(arr, i, arr.length);
  14.         }
  15.         int heapsize = arr.length;
  16.         swap(arr, 0, --heapsize); // heapInster后第一个为大根堆最大值 直接丢到数组末端并heapsize-- 下次操作不包括此元素
  17.         while (heapsize > 0) {
  18.             heapify(arr, 0, heapsize);// 向下沉
  19.             swap(arr, 0, --heapsize); // 交换
  20.         }
  21.     }
  23.     // 向下移动
  24.     private static void heapify(int[] arr, int i, int heapsize) {
  25.         int left = i * 2 + 1;
  26.         while (left < heapsize) {
  27.             int largest = left + 1 < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;
  28.             largest = arr[i] < arr[largest] ? largest : i;
  29.             if (largest == i) {
  30.                 break;
  31.             }
  32.             swap(arr, i, largest);
  33.             i = largest;
  34.             left = i * 2 + 1;
  36.         }
  38.     }
  40.     // 向上移动
  41.     private static void heapInster(int[] arr, int i) {
  42.         while (arr[i] > arr[(i - 1) / 2]) {
  43.             swap(arr, i, (i - 1) / 2);
  44.             i = (i - 1) / 2;
  45.         }
  46.     }
  48.     private static void swap(int[] arr, int i, int j) {
  49.         int temp = arr[i];
  50.         arr[i] = arr[j];
  51.         arr[j] = temp;
  53.     }

线段最大重合问题

  1. 给定很多线段，每个线段都有两个数[start, end]，
  2. 表示线段开始位置和结束位置，左右都是闭区间
  3. 规定：
  4. 1）线段的开始和结束位置一定都是整数值
  5. 2）线段重合区域的长度必须>=1
  6. 返回线段最多重合区域中，包含了几条线段
  1.     //暴力解法
  2.     public static int maxCover1(int[][] lines) {
  3.         int min = Integer.MAX_VALUE;
  4.         int max = Integer.MIN_VALUE;
  5.         for (int i = 0; i < lines.length; i++) { //找出线段最小值和最大值
  6.             min = Math.min(min, lines[i][0]);
  7.             max = Math.max(max, lines[i][1]);
  8.         }
  9.         int cover = 0;
  10.         for (double p = min + 0.5; p < max; p += 1) {  //每个隔0.5
  11.             int cur = 0;
  12.             for (int i = 0; i < lines.length; i++) {
  13.                 if (lines[i][0] < p && lines[i][1] > p) { //数有多少条线处于这0.5中 即有多少条重合线段
  14.                     cur++;
  15.                 }
  16.             }
  17.             cover = Math.max(cover, cur); //返回最大重合的数
  18.         }
  19.         return cover;
  20.     }
  23.     //堆解法
  24.     public static int maxCovcer2(int[][] lines) {
  25.         //比如, m = { {5,7}, {1,4}, {2,6} } 跑完如下的code之后变成：{ {1,4}, {2,6}, {5,7} }
  26.         Arrays.sort(lines,(o1,o2) -> (o1[0] - o2[0])); //以线段开始点 排序
  27.         //准备小根堆
  28.         PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
  29.         int max = 0;
  30.         for (int[] line : lines) {
  31.             //堆不为空 并且当前线段开头 大于等于 堆顶
  32.             while(!heap.isEmpty() && heap.peek() <= line[0]) {
  33.                 heap.poll(); //删除堆顶
  34.             }
  35.             heap.add(line[1]); //添加线段结束点到堆中
  36.             max = Math.max(max, heap.size());
  37.         }
  38.         return max;
  39.     }

5. 加强堆

  1. 系统提供的堆只能删除头节点(pop) 无法快速删除其他位置的节点
  2. 加强堆建立一个反向索引 通过值查找堆中索引 可以更快删除 删除之后与最后一个节点进行交换 再进行上移和下沉 保存堆的完整结构

需要提供一个比较器，来定义大根堆还是小根堆

  1. public class HeapGreater<T> {
  3.     private ArrayList<T> heap;
  4.     private HashMap<T, Integer> indexMap; // 反向索引表
  5.     private int heapSize;
  6.     private Comparator<? super T> comp;
  8.     public HeapGreater(Comparator<T> comp) {
  9.         heap = new ArrayList<>();
  10.         indexMap = new HashMap<>();
  11.         heapSize = 0;
  12.         this.comp = comp;
  13.     }
  15.     public boolean isEmpty() {
  16.         return heapSize == 0;
  17.     }
  19.     public int size() {
  20.         return heapSize;
  21.     }
  23.     public boolean contains(T obj) { // 返回此元素的索引是否存在
  24.         return indexMap.containsKey(obj);
  25.     }
  27.     public T peek() {
  28.         return heap.get(0); // 获取堆顶
  29.     }
  31.     public void push(T obj) { // 往堆添加元素
  32.         heap.add(obj);
  33.         indexMap.put(obj, heapSize); // 反向索引表
  34.         heapInsert(heapSize++);
  35.     }
  37.     public void heapInsert(int index) {
  38.         // 使用比较器比较当前元素 与它的根节点大小,当前元素大则进入循环体
  39.         while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
  40.             swap(index, (index - 1) / 2);
  41.             index = (index - 1) / 2;
  42.         }
  44.     }
  46.     public void swap(int i, int j) {
  47.         T o1 = heap.get(i); // 获取值
  48.         T o2 = heap.get(j);
  49.         heap.set(i, o2); // 增加替换指定索引
  50.         heap.set(j, o1);
  51.         indexMap.put(o2, i);// 更新反向索引
  52.         indexMap.put(o1, j);
  54.     }
  56.     public T pop() { // 删除并返回堆顶
  57.         T ans = heap.get(0);
  58.         swap(0, heapSize - 1); // 堆顶与尾元素交换
  59.         indexMap.remove(ans); // 删除索引
  60.         heap.remove(--heapSize); // 与尾元素断开连接
  61.         heapify(0);
  62.         return ans;
  63.     }
  65.     // 下沉
  66.     private void heapify(int index) {
  67.         int left = index * 2 + 1;
  68.         while (left < heapSize) {
  69.             // 查找左右孩子最大值下标
  70.             int best = left + 1 < heapSiz e && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
  71.             best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
  72.             if (best == index) {
  73.                 break;
  74.             }
  75.             // 与当前节点交换
  76.             swap(best, index);
  77.             index = best; // 继续下沉
  78.             left = index * 2 + 1;
  80.         }
  82.     }
  84.     // 从堆中删除用户给定的值 并保存堆完整性
  85.     public void remove(T obj) {
  86.         T replace = heap.get(heapSize - 1); // 获取尾元素
  87.         int index = indexMap.get(obj); // 获取要删除的索引
  88.         indexMap.remove(obj); // 删除索引
  89.         heap.remove(--heapSize); // 删除尾元素 前面已经缓存了尾元素值
  90.         if (obj != replace) {
  91.             heap.set(index, replace); // 直接更新堆替换为尾元素
  92.             indexMap.put(replace, index); // 更新索引表
  93.             resign(replace);
  95.         }
  97.     }
  99.     // 更新了一个堆中元素 保存堆完整性
  100.     public void resign(T replace) {
  101.         heapInsert(indexMap.get(replace)); // 上移
  102.         heapify(indexMap.get(replace)); // 下沉总会发生一个事件
  103.     }
  105.     public List<T> getAllElements() {
  106.         List<T> ans = new ArrayList<>();
  107.         for (T t : heap) {
  108.             ans.add(t);
  109.         }
  110.         return ans;
  111.     }
  113. }

5.1. 加强堆面试题

  1. 做一个加强堆的题目，给定一个整型数组，int[] arr；和一个布尔类型数组，boolean[] op
  2. 两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作
  3. arr= [3,3,1,2,1,2,5…
  4. op = [T,T,T,T,F,T,F…
  5. 依次表示：
  6. 3用户购买了一件商品
  7. 3用户购买了一件商品
  8. 1用户购买了一件商品
  9. 2用户购买了一件商品
  10. 1用户退货了一件商品
  11. 2用户购买了一件商品
  12. 5用户退货了一件商品…
  13. 一对arr[i]和op[i]就代表一个事件：
  14. 用户号为arr[i]，op[i] == T就代表这个用户购买了一件商品
  15. op[i] == F就代表这个用户退货了一件商品
  16. 现在你作为电商平台负责人，你想在每一个事件到来的时候，
  17. 都给购买次数最多的前K名用户颁奖。
  18. 所以每个事件发生后，你都需要一个得奖名单（得奖区）。
  19. 得奖系统的规则：
  20. 1，如果某个用户购买商品数为0，但是又发生了退货事件，
  21.      则认为该事件无效，得奖名单和上一个事件发生后一致，例子中的5用户
  22. 2，某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
  23. 3，每次都是最多K个用户得奖，K也为传入的参数
  24.       如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果
  25. 4，得奖系统分为得奖区和候选区，任何用户只要购买数>0，
  26.       一定在这两个区域中的一个
  27. 5，购买数最大的前K名用户进入得奖区，
  28.       在最初时如果得奖区没有到达K个用户，那么新来的用户直接进入得奖区
  29. 6，如果购买数不足以进入得奖区的用户，进入候选区
  30. 7，如果候选区购买数最多的用户，已经足以进入得奖区，
  31.      该用户就会替换得奖区中购买数最少的用户（大于才能替换），
  32.      如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户
  33.      如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户
  34. 8，候选区和得奖区是两套时间，
  35.      因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有
  36.      从得奖区出来进入候选区的用户，得奖区时间删除，
  37.      进入候选区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
  38.      从候选区出来进入得奖区的用户，候选区时间删除，
  39.      进入得奖区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
  40. 9，如果某用户购买数==0，不管在哪个区域都离开，区域时间删除，
  41.      离开是指彻底离开，哪个区域也不会找到该用户
  42.      如果下次该用户又发生购买行为，产生>0的购买数，
  43.      会再次根据之前规则回到某个区域中，进入区域的时间重记
  44. 请遍历arr数组和op数组，遍历每一步输出一个得奖名单
  45. public List<List<Integer>>  topK (int[] arr, boolean[] op, int k)
  1. // 封装对象
  2.     public static class Customer {
  3.         public int id;
  4.         public int buy;
  5.         public int enterTime;
  7.         public Customer(int id, int buy, int enterTime) {
  8.             this.id = id;
  9.             this.buy = buy;
  10.             this.enterTime = enterTime;
  11.         }
  13.     }
  15.     public static class CandidateComparator implements Comparator<Customer> {
  17.         @Override
  18.         public int compare(Customer o1, Customer o2) {
  20.             // 如果待选区的购买时间相同 则以购买金额比较(从大到小排序 第一个元素为最大值) 否则以时间则比较
  21.             return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
  22.         }
  24.     }
  26.     public static class DaddyComparator implements Comparator<Customer> {
  28.         @Override
  29.         public int compare(Customer o1, Customer o2) {
  30.             // 如果待选区的购买时间相同 则以购买金额比较(从小到大排序 第一个元素为最小值) 否则以时间则比较
  31.             return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
  32.         }
  34.     }
  36.     public static class WhoYourDaddy {
  37.         private HashMap<Integer, Customer> customers; // 反向索引表
  38.         private HeapGreater<Customer> candHeap; // 待选区
  39.         private HeapGreater<Customer> daddyHeap; // 得奖区
  40.         private final int daddyLimit; // 得奖区大小
  42.         public WhoYourDaddy(int daddyLimit) {
  43.             this.daddyLimit = daddyLimit;
  44.             customers = new HashMap<>();
  45.             candHeap = new HeapGreater<>(new CandidateComparator());
  46.             ;
  47.             daddyHeap = new HeapGreater<>(new DaddyComparator());
  48.         }
  50.         public void operate(int time, int id, boolean buyOrRefund) {
  51.             // 退货操作 并且索引表(即两个区都没有记录)没有 不用进行扣减不存在负数的记录
  52.             if (!buyOrRefund && !customers.containsKey(id)) {
  53.                 return;
  54.             }
  55.             // 两个区都不存在此记录 先精灵索引
  56.             if (!customers.containsKey(id)) {
  57.                 // 以id为索引 初始化值后面修改
  58.                 customers.put(id, new Customer(id, 0, 0));
  59.             }
  60.             Customer c = customers.get(id); // 以id在索引表查找出对象 进行修改
  61.             if (buyOrRefund) {
  62.                 // 是购买记录(即为T) 购买数++
  63.                 c.buy++;
  64.             } else {
  65.                 // 是退货记录
  66.                 c.buy--;
  67.             }
  68.             if (c.buy == 0) {
  69.                 // 如果目前对象进行增减操作后购买数为仍0 则要移除 从索引表删除
  70.                 customers.remove(id);
  71.             }
  73.             //多种情况分别讨论
  74.             if (!candHeap.contains(c) && !daddyHeap.contains(c)) {
  75.                 //此对象 待选区和得奖区都不存在 
  77.                 //得奖区有空闲位置 直接丢入得奖区
  78.                 if(daddyHeap.size() < daddyLimit) {
  79.                     c.enterTime = time;
  80.                     daddyHeap.push(c);
  81.                 } else {
  82.                     //得奖区已满 丢人待选区
  83.                     c.enterTime = time;
  84.                     candHeap.push(c);
  86.                 }
  87.             } else if(candHeap.contains(c)) {
  88.                 //此对象 存在于待选区
  90.                 if(c.buy == 0) {
  91.                     //为0 从待选区移除
  92.                     candHeap.remove(c);
  93.                 } else {
  94.                     //进行 上移和下沉操作 重新保持堆的完整性
  95.                     candHeap.resign(c);
  96.                 }
  97.             } else {
  98.                 //此对象 存在于得奖区
  99.                 if(c.buy == 0) {
  100.                     daddyHeap.remove(c);
  101.                 } else {
  102.                     daddyHeap.resign(c);
  103.                 }
  104.             }
  106.             daddyMove(time); //本次添加对象已经整合完毕 进行待选区与得奖区的比较
  107.         }
  109.         private void daddyMove(int time) {
  110.             //待选区为空 结束操作
  111.             if(candHeap.isEmpty()) {
  112.                 return;
  113.             }
  114.             //如果得奖区还有空位 则以待选区 堆顶元素 丢入得奖区
  115.             if(daddyHeap.size() < daddyLimit) {
  116.                 Customer p =  candHeap.pop(); //删除并获取待选区堆顶
  117.                 p.enterTime = time; //重新设置当前为当前时间
  118.                 daddyHeap.push(p); //丢入得奖区
  119.             } else {
  120.                 //比较 待选区最大值 与 得奖区最小值的大小
  121.                 if(candHeap.peek().buy > daddyHeap.peek().buy) {
  122.                     Customer oldDaddy = daddyHeap.pop(); //得奖区最小值
  123.                     Customer newDaddy = candHeap.pop(); //待选区最大值
  124.                     oldDaddy.enterTime = time; //重置时间
  125.                     newDaddy.enterTime = time;
  126.                     daddyHeap.push(newDaddy); //将待选区最大值丢入得奖区
  127.                     candHeap.push(oldDaddy); //将得奖区最小值丢回待选区
  128.                 }
  129.             }
  131.         }
  133.         //获取得奖区的全部id(用户)
  134.         public List<Integer> getDaddies(){
  135.             List<Customer> customers = daddyHeap.getAllElements(); //获取得奖区的全部对象
  136.             List<Integer> ans = new ArrayList<>();
  137.             for (Customer c : customers) {
  138.                 ans.add(c.id);
  139.             }
  140.             return ans;
  141.         }
  143.     }
  145.     public static List<List<Integer>> topK(int[] arr,boolean[] op,int k){
  146.         List<List<Integer>> ans = new ArrayList<>();
  147.         WhoYourDaddy whoDaddies = new WhoYourDaddy(k);
  148.         for (int i = 0; i < arr.length; i++) {
  149.             whoDaddies.operate(i, arr[i], op[i]);
  150.             ans.add(whoDaddies.getDaddies());
  151.         }
  152.         return ans;
  153.     }
  158.     // 暴力破解法
  159.     // 干完所有的事，模拟，不优化
  160.         public static List<List<Integer>> compare(int[] arr, boolean[] op, int k) {
  161.             HashMap<Integer, Customer> map = new HashMap<>();
  162.             ArrayList<Customer> cands = new ArrayList<>();
  163.             ArrayList<Customer> daddy = new ArrayList<>();
  164.             List<List<Integer>> ans = new ArrayList<>();
  165.             for (int i = 0; i < arr.length; i++) {
  166.                 int id = arr[i];
  167.                 boolean buyOrRefund = op[i];
  168.                 if (!buyOrRefund && !map.containsKey(id)) {
  169.                     ans.add(getCurAns(daddy));
  170.                     continue;
  171.                 }
  172.                 // 没有发生：用户购买数为0并且又退货了
  173.                 // 用户之前购买数是0，此时买货事件
  174.                 // 用户之前购买数>0， 此时买货
  175.                 // 用户之前购买数>0, 此时退货
  176.                 if (!map.containsKey(id)) {
  177.                     map.put(id, new Customer(id, 0, 0));
  178.                 }
  179.                 // 买、卖
  180.                 Customer c = map.get(id);
  181.                 if (buyOrRefund) {
  182.                     c.buy++;
  183.                 } else {
  184.                     c.buy--;
  185.                 }
  186.                 if (c.buy == 0) {
  187.                     map.remove(id);
  188.                 }
  189.                 // c
  190.                 // 下面做
  191.                 if (!cands.contains(c) && !daddy.contains(c)) {
  192.                     if (daddy.size() < k) {
  193.                         c.enterTime = i;
  194.                         daddy.add(c);
  195.                     } else {
  196.                         c.enterTime = i;
  197.                         cands.add(c);
  198.                     }
  199.                 }
  200.                 cleanZeroBuy(cands);
  201.                 cleanZeroBuy(daddy);
  202.                 cands.sort(new CandidateComparator());
  203.                 daddy.sort(new DaddyComparator());
  204.                 move(cands, daddy, k, i);
  205.                 ans.add(getCurAns(daddy));
  206.             }
  207.             return ans;
  208.         }
  210.         public static void move(ArrayList<Customer> cands, ArrayList<Customer> daddy, int k, int time) {
  211.             if (cands.isEmpty()) {
  212.                 return;
  213.             }
  214.             // 候选区不为空
  215.             if (daddy.size() < k) {
  216.                 Customer c = cands.get(0);
  217.                 c.enterTime = time;
  218.                 daddy.add(c);
  219.                 cands.remove(0);
  220.             } else { // 等奖区满了，候选区有东西
  221.                 if (cands.get(0).buy > daddy.get(0).buy) {
  222.                     Customer oldDaddy = daddy.get(0);
  223.                     daddy.remove(0);
  224.                     Customer newDaddy = cands.get(0);
  225.                     cands.remove(0);
  226.                     newDaddy.enterTime = time;
  227.                     oldDaddy.enterTime = time;
  228.                     daddy.add(newDaddy);
  229.                     cands.add(oldDaddy);
  230.                 }
  231.             }
  232.         }
  234.         public static void cleanZeroBuy(ArrayList<Customer> arr) {
  235.             List<Customer> noZero = new ArrayList<Customer>();
  236.             for (Customer c : arr) {
  237.                 if (c.buy != 0) {
  238.                     noZero.add(c);
  239.                 }
  240.             }
  241.             arr.clear();
  242.             for (Customer c : noZero) {
  243.                 arr.add(c);
  244.             }
  245.         }
  247.         public static List<Integer> getCurAns(ArrayList<Customer> daddy) {
  248.             List<Integer> ans = new ArrayList<>();
  249.             for (Customer c : daddy) {
  250.                 ans.add(c.id);
  251.             }
  252.             return ans;
  253.         }
  255.         // 为了测试
  256.         public static class Data {
  257.             public int[] arr;
  258.             public boolean[] op;
  260.             public Data(int[] a, boolean[] o) {
  261.                 arr = a;
  262.                 op = o;
  263.             }
  264.         }
  266.         // 为了测试
  267.         public static Data randomData(int maxValue, int maxLen) {
  268.             int len = (int) (Math.random() * maxLen) + 1;
  269.             int[] arr = new int[len];
  270.             boolean[] op = new boolean[len];
  271.             for (int i = 0; i < len; i++) {
  272.                 arr[i] = (int) (Math.random() * maxValue);
  273.                 op[i] = Math.random() < 0.5 ? true : false;
  274.             }
  275.             return new Data(arr, op);
  276.         }
  278.         // 为了测试
  279.         public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
  280.             if (ans1.size() != ans2.size()) {
  281.                 return false;
  282.             }
  283.             for (int i = 0; i < ans1.size(); i++) {
  284.                 List<Integer> cur1 = ans1.get(i);
  285.                 List<Integer> cur2 = ans2.get(i);
  286.                 if (cur1.size() != cur2.size()) {
  287.                     return false;
  288.                 }
  289.                 cur1.sort((a, b) -> a - b);
  290.                 cur2.sort((a, b) -> a - b);
  291.                 for (int j = 0; j < cur1.size(); j++) {
  292.                     if (!cur1.get(j).equals(cur2.get(j))) {
  293.                         return false;
  294.                     }
  295.                 }
  296.             }
  297.             return true;
  298.         }
  300.         public static void main(String[] args) {
  301.             int maxValue = 10;
  302.             int maxLen = 100;
  303.             int maxK = 6;
  304.             int testTimes = 100000;
  305.             System.out.println("测试开始");
  306.             for (int i = 0; i < testTimes; i++) {
  307.                 Data testData = randomData(maxValue, maxLen);
  308.                 int k = (int) (Math.random() * maxK) + 1;
  309.                 int[] arr = testData.arr;
  310.                 boolean[] op = testData.op;
  311.                 List<List<Integer>> ans1 = topK(arr, op, k);
  312.                 List<List<Integer>> ans2 = compare(arr, op, k);
  313.                 if (!sameAnswer(ans1, ans2)) {
  314.                     for (int j = 0; j < arr.length; j++) {
  315.                         System.out.println(arr[j] + " , " + op[j]);
  316.                     }
  317.                     System.out.println(k);
  318.                     System.out.println(ans1);
  319.                     System.out.println(ans2);
  320.                     System.out.println("出错了！");
  321.                     break;
  322.                 }
  323.             }
  324.             System.out.println("测试结束");
  325.         }

6. 23. 合并K个升序链表

  1. public class ListNode {
  2.         int val;
  3.         ListNode next;
  5.         ListNode() {
  6.         }
  8.         ListNode(int val) {
  9.             this.val = val;
  10.         }
  12.         ListNode(int val, ListNode next) {
  13.             this.val = val;
  14.             this.next = next;
  15.         }
  16.     }
  18.     public ListNode mergeKLists(ListNode[] lists) {
  19.         PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>((o1, o2) -> o1.val - o2.val); //自定义比较器的最小堆
  20.         for (ListNode listNode : lists) { //遍历链表数组
  21.             if (listNode != null) { 
  22.                 heap.add(listNode); //非空则push到最小堆
  23.             }
  24.         }
  25.         if (heap.isEmpty()) { //堆中没有
  26.             return null;
  27.         }
  28.         ListNode head = heap.poll(); // 弹出最小堆头
  29.         ListNode pre = head;
  30.         if (pre.next != null) {
  31.             heap.add(pre.next); // 如果pre下一跳 不为空 直接push到最小堆中
  32.         }
  33.         while (!heap.isEmpty()) { //最小堆不为空
  34.             ListNode cur = heap.poll(); //弹出栈顶 即最小值
  35.             pre.next = cur; //下一跳 连接
  36.             pre = cur; //更新当前节点
  37.             if (cur.next != null) { //当前节点 下一跳不为空则添加到最小堆中
  38.                 heap.add(cur.next);
  39.             }
  40.         }
  41.         return head;
  43.     }