春招冲刺百题计划|堆

Java基础复习

Java数组的声明与初始化
Java ArrayList
Java HashMap
Java String 类
Java LinkedList
Java Deque继承LinkedList
Java Set
Java 队列
优先队列:第二题用到了

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

在这里插入图片描述
可以直接使用Arrays.sort()快排，然后return nums[n-k];
或者手动实现快速选择的内容：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
在这里插入图片描述

class Solution {int quickselect(int[] nums, int l, int r, int k) {if (l == r) return nums[k];int x = nums[l], i = l - 1, j = r + 1; //选最左边的为基准。while (i < j) {do{ i++; }while(nums[i] < x);//左边的都小于xdo{j--;}while(nums[j] > x);//右边的都大于xif (i < j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}if (k <= j) return quickselect(nums, l, j, k); //一趟排序后，基准比第k大的大，那么在基准左边找。else return quickselect(nums, j + 1, r, k);//否则在基准右边找。}public int findKthLargest(int[] _nums, int k) {int n = _nums.length;return quickselect(_nums, 0, n - 1, n - k);}
}

另一种解法就是堆排序：参考：https://pdai.tech/md/algorithm/alg-sort-x-heap.html
逻辑结构是完全二叉树，存储结构是数组。之间的联系如下：
在这里插入图片描述算法实现步骤就是， ① 初始化堆: 将数列a[1…n]构造成最大堆。 ② 交换数据: 将a[1]和a[n]交换，使a[n]是a[1…n]中的最大值；然后将a[1…n-1]重新调整为最大堆。接着，将a[1]和a[n-1]交换，使a[n-1]是a[1…n-1]中的最大值；然后将a[1…n-2]重新调整为最大值。依次类推，直到整个数列都是有序的。

    public static void maxHeapDown(int[] a, int start, int end) {int c = start;            // 当前(current)节点的位置int l = 2*c + 1;        // 左(left)孩子的位置int tmp = a[c];            // 当前(current)节点的大小for (; l <= end; c=l,l=2*l+1) {// "l"是左孩子，"l+1"是右孩子if ( l < end && a[l] < a[l+1])l++;        // 左右两孩子中选择较大者，即m_heap[l+1]if (tmp >= a[l])break;        // 调整结束else {            // 交换值a[c] = a[l];a[l]= tmp;}}}/** 堆排序(从小到大)** 参数说明: *     a -- 待排序的数组*     n -- 数组的长度*/public static void heapSortAsc(int[] a, int n) {int i,tmp;// 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。for (i = n / 2 - 1; i >= 0; i--)maxHeapDown(a, i, n-1);// 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素for (i = n - 1; i > 0; i--) {// 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。tmp = a[0];a[0] = a[i];a[i] = tmp;// 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。// 即，保证a[i-1]是a[0...i-1]中的最大值。maxHeapDown(a, 0, i-1);}}

提交代码：

class Solution {public static void heapSortAsc(int[] a, int n){for(int i=n/2-1; i>=0; i--){maxHeapDown(a, i, n-1);}for (int i = n - 1; i > 0; i--) {// 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。int tmp = a[0];a[0] = a[i];a[i] = tmp;// 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。// 即，保证a[i-1]是a[0...i-1]中的最大值。maxHeapDown(a, 0, i-1);}}public static void maxHeapDown(int[] a, int start, int end) {int c = start;            // 当前(current)节点的位置int l = 2*c + 1;        // 左(left)孩子的位置int tmp = a[c];            // 当前(current)节点的大小for (; l <= end; c=l,l=2*l+1) {// "l"是左孩子，"l+1"是右孩子if ( l < end && a[l] < a[l+1])l++;        // 左右两孩子中选择较大者，即m_heap[l+1]if (tmp >= a[l])break;        // 调整结束else {            // 交换值a[c] = a[l];a[l]= tmp;}}}public int findKthLargest(int[] _nums, int k) {int n = _nums.length;heapSortAsc(_nums, n);return _nums[n-k];}
}

第二题：373. 查找和最小的 K 对数字

在这里插入图片描述
以下写法超出内存限制：

class Solution {public static void heapSortAsc(int[][] a, int n){for(int i=n/2-1; i>=0; i--){maxHeapDown(a, i, n-1);}for (int i = n - 1; i > 0; i--) {// 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。int[] tmp = a[0];a[0] = a[i];a[i] = tmp;// 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。// 即，保证a[i-1]是a[0...i-1]中的最大值。maxHeapDown(a, 0, i-1);}}public static void maxHeapDown(int[][] a, int start, int end) {int c = start;            // 当前(current)节点的位置int l = 2*c + 1;        // 左(left)孩子的位置int[] tmp = a[c];            // 当前(current)节点的大小for (; l <= end; c=l,l=2*l+1) {// "l"是左孩子，"l+1"是右孩子if ( l < end && (a[l][0] + a[l][1]) < (a[l+1][0] + a[l+1][1]))l++;        // 左右两孩子中选择较大者，即m_heap[l+1]if ((tmp[0]+tmp[1]) >=  (a[l][0] + a[l][1]))break;        // 调整结束else {            // 交换值a[c] = a[l];a[l] = tmp;}}}public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {int n = nums1.length*nums2.length;int[][] a = new int[n][2];int idx = 0;for(int i=0; i<nums1.length; i++){for(int j=0; j<nums2.length; j++){a[idx][0] = nums1[i];a[idx++][1] = nums2[j];}}heapSortAsc(a, n);List<List<Integer>> results = new ArrayList<List<Integer>>();   for(int i=0; i<k; i++){List<Integer> tmp = new ArrayList<Integer>();tmp.add(a[i][0]);tmp.add(a[i][1]);results.add(tmp);}return results;}
}

参考：灵茶山艾府的题解
在这里插入图片描述
觉得这样的大神，每次写得代码都很简洁。哭唧唧。我和这篇的问题，就在于，我使用的代码的堆，没办法随时调整。

class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {List<List<Integer>> ans = new ArrayList<>(k); // 预分配空间PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);pq.add(new int[]{nums1[0] + nums2[0], 0, 0});while (ans.size() < k) {int[] p = pq.poll();int i = p[1];int j = p[2];ans.add(List.of(nums1[i], nums2[j]));if (j == 0 && i + 1 < nums1.length) {pq.add(new int[]{nums1[i + 1] + nums2[0], i + 1, 0});}if (j + 1 < nums2.length) {pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});}}return ans;}
}

这里自己仿照源码写了一份优先队列

class Solution {class MyPriorityQueue{//仿照源码编写自己的private int[][] queue;private int size;MyPriorityQueue(){queue=new int[0][0];size = 0;}private int Mycompare(int[] a, int[] b){return a[0]-b[0];}public void offer(int[] e){int i = size;if (i >= queue.length)queue = Arrays.copyOf(queue, i+1);size = i + 1;if (i == 0)//队列原来为空，这是插入的第一个元素queue[0] = e;elsesiftUp(i, e);//调整}private void siftUp(int k, int[] x) { //找到x该待的位置while (k > 0) {int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2int[] e = queue[parent];if (Mycompare(x, e) >= 0) break;queue[k] = e;k = parent;}queue[k] = x;}public int[] peek() {if (size == 0)return null;return queue[0];//0下标处的那个元素就是最小的那个}public int[] poll() {if (size == 0)return null;int s = --size;int[] result = queue[0];//0下标处的那个元素就是最小的那个int[] x = queue[s]; //最后一个叶子结点queue[s] = null;if (s != 0) //队列不为空要调整siftDown(0, x);//调整return result;}private void siftDown(int k, int[] x) {int half = size >>> 1; //size/2while (k < half) {//首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标int child = (k << 1) + 1;//leftNo = parentNo*2+1int[] c = queue[child];int right = child + 1;if (right < size && Mycompare(c, queue[right]) > 0)c = queue[child = right];if (Mycompare(x, c) <= 0)break;queue[k] = c;//然后用c取代原来的值k = child;}queue[k] = x;}}public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {List<List<Integer>> ans = new ArrayList<>(k); // 预分配空间MyPriorityQueue pq = new MyPriorityQueue();pq.offer(new int[]{nums1[0] + nums2[0], 0, 0});while (ans.size() < k) {int[] p = pq.poll();int i = p[1];int j = p[2];ans.add(List.of(nums1[i], nums2[j]));if (j == 0 && i + 1 < nums1.length) {pq.offer(new int[]{nums1[i + 1] + nums2[0], i + 1, 0});}if (j + 1 < nums2.length) {pq.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});}}return ans;}
}

第三题：264. 丑数 II

在这里插入图片描述
首先明确一下质因子是什么？
质因子（或质因数）在数论里是指能整除给定正整数的质数。
只有两个正因数（1和它本身）的自然数即为质数。（2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97…）
仔细想想还是不难的，就是用小顶堆，弹出一个x，添加2x，3x，5x进去。

class Solution {int[] NUMS = new int[]{2, 3, 5};class MyPriorityQueue{//仿照源码编写自己的private long[] queue;private int size;MyPriorityQueue(){queue=new long[0];size = 0;}private long Mycompare(long a, long b){return a-b;}public void offer(long e){int i = size;if (i >= queue.length)queue = Arrays.copyOf(queue, i+1);size = i + 1;if (i == 0)//队列原来为空，这是插入的第一个元素queue[0] = e;elsesiftUp(i, e);//调整}private void siftUp(int k, long x) { //找到x该待的位置while (k > 0) {int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2long e = queue[parent];if (Mycompare(x, e) >= 0) break;queue[k] = e;k = parent;}queue[k] = x;}public long peek() {return queue[0];//0下标处的那个元素就是最小的那个}public long poll() {int s = --size;long result = queue[0];//0下标处的那个元素就是最小的那个long x = queue[s]; //最后一个叶子结点queue[s] = -1;if (s != 0) //队列不为空要调整siftDown(0, x);//调整return result;}private void siftDown(int k, long x) {int half = size >>> 1; //size/2while (k < half) {//首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标int child = (k << 1) + 1;//leftNo = parentNo*2+1long c = queue[child];int right = child + 1;if (right < size && Mycompare(c, queue[right]) > 0)c = queue[child = right];if (Mycompare(x, c) <= 0)break;queue[k] = c;//然后用c取代原来的值k = child;}queue[k] = x;}}public int nthUglyNumber(int n) {//我目前的思路就是得到一组序列，长度为n，就是从1开始算，找到第n个满足条件的就行。int[] result = new int[n+1];result[1] = 1;if(n==1){return result[n];}int sum=2;MyPriorityQueue queue = new MyPriorityQueue();Set<Long> had = new HashSet<>();queue.offer(2); had.add(2l);queue.offer(3); had.add(3l);queue.offer(5); had.add(5l);while(sum<=n){long tmp = queue.poll();result[sum] = (int)tmp;for(int i=0; i<NUMS.length; i++){if(!had.contains(tmp*NUMS[i])){had.add(tmp*NUMS[i]);queue.offer(tmp*NUMS[i]);}}sum++;}return result[n];}
}