堆排序及常见面试题

news/2024/4/25 0:07:05/

请添加图片描述
⭐️前言⭐️

本篇文章记录堆排序以及对应的一些练习。

🍉欢迎点赞 👍 收藏留言评论 📝私信必回哟😁

🍉博主将持续更新学习记录收获,友友们有任何问题可以在评论区留言

🍉博客中涉及源码及博主日常练习代码均已上传GitHub


请添加图片描述

📍内容导读📍

  • 🍅1.堆排序实现
  • 🍅2.线段最大重合问题
  • 🍅3.加强堆的实现

🍅1.堆排序实现

实现思路:
1.首先先建大堆
2.建好堆后,利用堆的性质完成排序
3.将堆顶元素与堆位元素互换,那么堆尾位置元素就是堆中的最大元素,并将堆顶元素向下调整,继续保持堆结构。
4.持续相同操作,直到到堆顶位置,此时堆中元素变为升序。

代码实现:

public class HeapSort {public static void heapSort(int[] array) {createBigHeap(array);int end=array.length-1;while (end>=0) {swap(array,0,end);shiftDown(array,0,end);end--;}}private static void shiftDown(int[] array,int parent,int len) {// 保证有左孩子int child=2*parent+1;while (child<len) {// 如果有右孩子,左右孩子比较,child记录较大值的下标if(child+1<len&&array[child]<array[child+1]) {child++;}if(array[child]>array[parent]) {swap(array,child,parent);// 继续向下调整parent=child;child=2*parent+1;}else {break;}}}private static void swap(int[] array,int i,int j) {int tmp=array[i];array[i]=array[j];array[j]=tmp;}private static void createBigHeap(int[] array) {// 先找到最后一棵子树的父节点,让每棵子树成为大顶堆for(int parent=(array.length-1-1)/2;parent>=0;parent--) {shiftDown(array,parent,array.length);}}
}

🍅2.线段最大重合问题

题目:
给定很多线段,每个线段都有两个数[start, end],
表示线段开始位置和结束位置,左右都是闭区间
规定:
1)线段的开始和结束位置一定都是整数值
2)线段重合区域的长度必须>=1
返回线段最多重合区域中,包含了几条线段

题解思路:
1.首先通过比较器,将所有线段基于线段的起始位置进行排序,然后来求每条线段的最大重复线段数。
2.利用小根堆(小根堆存储每条线段的结束位置),每次到达新线段时,将小根堆中比新线段起始位置小的数弹出(弹出的线段是起始位置和结束位置都比新线段其实位置小的线段,不可能有重复),并将新线段的结束位置放入小根堆,此时小根堆中代表的线段就是有公共重合区域的线段,返回heap.size()就是重复线段数。
3.每条线段都进行这样的操作,返回heap.size()中最大的max,就表示线段最多重合区域中,包含的线段数。

代码实现:

public class CoverMax {static class Line {public int start;public int end;public Line(int start, int end) {this.start = start;this.end = end;}}static int maxCover(int[][] m) {Line[] lines=new Line[m.length];for (int i = 0; i < m.length; i++) {lines[i]=new Line(m[i][0],m[i][1]);}Arrays.sort(lines, new Comparator<Line>() {@Overridepublic int compare(Line o1, Line o2) {return o1.start-o2.start;}});// Arrays.sort(lines,(a,b)->a.start-b.start);  // 语法糖PriorityQueue<Integer> heap=new PriorityQueue<>();int max=0;for (int i = 0; i < lines.length; i++) {while (!heap.isEmpty()&&heap.peek()<=lines[i].start) {heap.poll();}heap.add(lines[i].end);max=Math.max(max,heap.size());}return max;}
}

🍅3.加强堆的实现

是对于普通堆结构的改写,增添了一些普通堆不具有的功能

public class HeapGreater<T> {private ArrayList<T> heap;private HashMap<T,Integer> indexMap;  // 用于加强堆结构中的反向索引操作private int heapSize;private Comparator<? super T> comp;public HeapGreater(Comparator<? super T> comp) {heap=new ArrayList<>();indexMap=new HashMap<>();heapSize=0;this.comp = comp;}// 判断堆是否为空public boolean isEmpty() {return heapSize==0;}// 返回堆大小public int size() {return heapSize;}// 判断堆中是否包含某个元素public boolean contains(T obj) {return indexMap.containsKey(obj);}// 返回堆顶元素public T peek() {return heap.get(0);}// 堆中新增元素public void push(T obj) {heap.add(obj);indexMap.put(obj,heapSize);heapInsert(heapSize);heapSize++;}// 堆中插入新元素,向上调整新元素private void heapInsert(int child) {int parent=(child-1)/2;while (child>0) {if(comp.compare(heap.get(child),heap.get(parent))<0) {swap(child,parent);child=parent;parent=(child-1)/2;}else {break;}}}private void swap(int i, int j) {T o1=heap.get(i);T o2=heap.get(j);heap.set(i,o2);heap.set(j,o1);indexMap.put(o2,i);indexMap.put(o1,j);}// 弹出堆顶元素public T pop() {T ans=heap.get(0);swap(0,heapSize-1);indexMap.remove(ans);heap.remove(--heapSize);shiftDown(0);return ans;}// 小根堆向下调整private void shiftDown(int parent) {int child=2*parent+1;while (child<heapSize) {if(child+1<heapSize&&comp.compare(heap.get(child+1),heap.get(child))<0) {child++;}if(comp.compare(heap.get(child),heap.get(parent))<0) {swap(child,parent);parent=child;child=2*parent+1;}else {break;}}}// 去除某个元素public void remove(T obj) {T replace=heap.get(heapSize-1);int index=indexMap.get(obj);indexMap.remove(obj);heap.remove(--heapSize);if(obj!=replace) {heap.set(index,replace);indexMap.put(replace,index);resign(replace);}}private void resign(T obj) {heapInsert(indexMap.get(obj));shiftDown(indexMap.get(obj));}// 返回堆上所有元素public List<T> getAllElements() {List<T> ans=new ArrayList<>();for(T c:heap) {ans.add(c);}return ans;} 
}

⭐️最后的话⭐️
总结不易,希望uu们不要吝啬你们的👍哟(^U^)ノ~YO!!如有问题,欢迎评论区批评指正😁

请添加图片描述


http://www.ppmy.cn/news/47359.html

相关文章

392. 判断子序列

给定字符串 s 和 t &#xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些&#xff08;也可以不删除&#xff09;字符而不改变剩余字符相对位置形成的新字符串。&#xff08;例如&#xff0c;"ace"是"abcde"的一个子序列&#…

三年创作,两年偷懒,一年划水

回顾 离我写第一篇文章开始&#xff0c;不知不觉已经三年了&#xff0c;回顾写作分享之路&#xff0c;可谓是坎坷崎岖&#xff0c;当然也正因为这一路的磨难让我收获不菲。 兜兜转转三年写了很多文章&#xff0c;回顾起我的写作起点&#xff0c;尤为艰难。刚刚开始写作时&…

【hello Linux】进程控制

目录 1. 进程创建 2. 进程终止 3. 进程常见的退出方法 4. 进程等待 5. 进程等待的方法 6. 获取子进程status Linux&#x1f337; 1. 进程创建 fork 函数初识 在 linux 中 fork 函数是非常重要的函数&#xff0c;它可以从已存在进程中创建一个新进程。 新进程便是我们所说的子进…

[API]IO文件流单字节读取块及读取(六)

IO&#xff1a; 可以让我们用标准的读写操作来完成对不同设备的读写数据工作。java将IO按照方向划分为输入与输出,参照点是我们写的程序 输入&#xff1a;用来读取数据的,是从外界到程序的方向,用于获取数据。输出&#xff1a;用来写出数据的,是从程序到外界的方向,用于发送数…

基于html+css的盒子展示8

准备项目 项目开发工具 Visual Studio Code 1.44.2 版本: 1.44.2 提交: ff915844119ce9485abfe8aa9076ec76b5300ddd 日期: 2020-04-16T16:36:23.138Z Electron: 7.1.11 Chrome: 78.0.3904.130 Node.js: 12.8.1 V8: 7.8.279.23-electron.0 OS: Windows_NT x64 10.0.19044 项目…

Metasploit高级技术【第九章】

预计更新第一章 Metasploit的使用和配置 1.1 安装和配置Metasploit 1.2 Metasploit的基础命令和选项 1.3 高级选项和配置 第二章 渗透测试的漏洞利用和攻击方法 1.1 渗透测试中常见的漏洞类型和利用方法 1.2 Metasploit的漏洞利用模块和选项 1.3 模块编写和自定义 第三章 Met…

( “树” 之 BFS) 513. 找树左下角的值 ——【Leetcode每日一题】

513. 找树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 示例 2: 输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7 提示: 二叉树的节点个数的范围是 […

C语言函数大全-- l 开头的函数

C语言函数大全 本篇介绍C语言函数大全-- l 开头的函数 1. labs&#xff0c;llabs 1.1 函数说明 函数声明函数功能long labs(long n);计算长整型的绝对值long long int llabs(long long int n);计算long long int 类型整数的绝对值 1.2 演示示例 #include <stdio.h>…

prettier 命令行工具来格式化多个文件

prettier 命令行工具来格式化多个文件 你可以使用 prettier 命令行工具来格式化多个文件。以下是一个使用命令行批量格式化文件的示例&#xff1a; 安装 prettier 如果你还没有安装 prettier&#xff0c;你可以使用以下命令安装它&#xff1a; npm install -g prettier 进入…

Serilog介绍

SerilogSerilogSerilog是.net 下的新兴的日志框架&#xff0c;本文这里简单的介绍一下它的用法。 首先安装Nuget包&#xff1a; Install-Package SerilogInstall-Package Serilog.Sinks.Console 其中包Serilog是Log核心库&#xff0c;Serilog.Sinks.Console是Log的控制台输出…

大数据项目之数仓相关知识

第1章 数据仓库概念 数据仓库&#xff08;DW&#xff09;: 为企业指定决策&#xff0c;提供数据支持的&#xff0c;帮助企业&#xff0c;改进业务流程&#xff0c;提高产品质量等。 DW的输入数据通常包括&#xff1a;业务数据&#xff0c;用户行为数据和爬虫数据等 ODS: 数据…

【Maven】修改编码格式的多种方式

文章目录 方式一方式二方式三是否生效 为什么修改&#xff1f; 中文操作系统编码为GBK&#xff0c;Maven安装后会使用系统默认编码&#xff0c;编译含有中文字符的UTF-8格式源码文件时就出现编码不匹配的问题 场景&#xff1a;使用Maven编译项目&#xff0c;虽然提示编译成功&…

详解C语言string.h中常见的14个库函数(二)

本篇博客继续讲解string.h中的库函数。在上一篇博客中&#xff0c;我介绍了strlen, strcpy, strcat, strcmp这4个字符串操作函数&#xff0c;本篇博客会继续介绍strncpy, strncat, strncmp这3个类似的函数。 strcpy, strcat, strcmp这3个函数是长度不受限制的字符串操作函数&a…

Web 攻防之业务安全:验证码绕过测试.(修改数据包中 res_code 的值 实现绕过.)

Web 攻防之业务安全&#xff1a;验证码绕过测试. 业务安全是指保护业务系统免受安全威胁的措施或手段。广义的业务安全应包括业务运行的软硬件平台&#xff08;操作系统、数据库&#xff0c;中间件等&#xff09;、业务系统自身&#xff08;软件或设备&#xff09;、业务所提供…

利用R语言实现vcf转txt算法,基于vcfR和tidyverse

算法&#xff1a;vcf转txt并自动规范化 引言 vcf文件是存放基因变异信息的一种方式&#xff0c;本文提供一种算法&#xff0c;用于读取vcf文件并转换等位基因展示方法、替换染色体展示格式、以及自动识别非唯一变异并进行修改&#xff0c;用于对变异信息进行整理。 主要步骤与设…

测试5年,从纯手工测试到测试开发,我是怎么拿到腾讯25koffer的?

什么都做了&#xff0c;和什么都没做其实是一样的&#xff0c;走出“瞎忙活”的安乐窝&#xff0c;才是避开弯路的最佳路径。希望我的经历能帮助到有需要的朋友。 在测试行业已经混了5个年头了&#xff0c;以前经常听到开发对我说&#xff0c;天天的点点点有意思没&#xff1f…

Java工程行业管理系统源码-专业的工程管理软件-提供一站式服务

Java版工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离 功能清单如下&#xff1a; 首页 工作台&#xff1a;待办工作、消息通知、预警信息&#xff0c;点击可进入相应的列表 项目进度图表&#xff1a;选择&#xff08;总体或单个&#xff09;项目显示1…

使用Softing edgePlug软件扩展数控机床的连接性

那些使用SINUMERIK 840D控制器来运行数控机床的制造商正面临着一个挑战——从车间提取机床性能和过程数据来进行分析。这些数据对于优化流程至关重要&#xff0c;但它们却无法通过传统方式来被获取。对此&#xff0c;制造商的应对方法是通过自定义代码来实现数据访问&#xff0…

BufferedOutputStream,BufferedInputStream是字节流,对象处理流,序列化,输入输出流,转换流

BufferedInputStream字节输入流 意思就是InputStream类及其子类都能以参数的形式放到BufferedInputStream构造器的参数 package com.hspedu.outputstream_;import java.io.*;/*** author 韩顺平* version 1.0* 演示使用BufferedOutputStream 和 BufferedInputStream使用* 使用他…

带你浅谈下Quartz的简单使用

Scheduler 每次执行&#xff0c;都会根据JobDetail创建一个新的Job实例&#xff0c;这样就可以规避并发访问的问题&#xff08;jobDetail的实例也是新的&#xff09; Quzrtz 定时任务默认都是并发执行&#xff0c;不会等待上一次任务执行完毕&#xff0c;只要间隔时间到就会执…