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

Java数据结构和算法相关面试题


天行健,君子以自强不息;地势坤,君子以厚德载物。


每个人都有惰性,但不断学习是好好生活的根本,共勉!


文章均为学习整理笔记,分享记录为主,如有错误请指正,共同学习进步。


《送别》
寻阳五溪水,沿洄直入巫山里。胜境由来人共传,
君到南中自称美。送君别有八月秋,飒飒芦花复益愁。
云帆望远不相见,日暮长江空自流。


文章目录

  • 数据结构和算法
    • 1. 时间复杂度和空间复杂度
      • 1.1 时间复杂度
      • 1.2 空间复杂度
    • 2. 数组和链表的结构对比
      • 2.1 数组
        • 概念
        • 数组的特性
      • 2.2 链表
        • 概念
        • 链表的特性
        • 常见的链表
        • 应用
    • 3. 遍历一个树
    • 4. 冒泡排序 Bubble Sort
      • 4.1 算法描述
      • 4.2 复杂度
      • 4.3 代码实现
    • 5. 快速排序 Quick Sort
      • 5.1 算法描述
      • 5.2 复杂度
      • 5.3 代码实现
    • 6. 二分查找 Binary Search
      • 6.1 算法描述
      • 6.2 复杂度
      • 6.3 代码实现
      • 6.4 拓展


数据结构和算法

1. 时间复杂度和空间复杂度

时间复杂度和空间复杂度是衡量一个算法是否高效的重要标准
时间复杂度不是算法执行的时间,这是错误的

1.1 时间复杂度

指的是算法语句执行的次数,如O(1), O(n), O(logn), O(n2)

1.2 空间复杂度

指的是一个算法在运行过程中临时占用的存储空间大小,即被创建次数最多的变量被创建了多少次,这个算法的空间复杂度就是多少
如果算法语句中就有创建对象,那么该算法的时间复杂度和空间复杂度一般一致
算法语句被执行了多少次就创建了多少个对象

2. 数组和链表的结构对比

2.1 数组

概念

相同数据类型的元素按一定顺序排列的集合
就是把有限个类型相同的变量用一个名字,改名字就是数组名,用编号区分数组中变量,编号就是下标

数组的特性
  • 数组必须先定义固定长度,不能动态适应数据动态增减
  • 当数据增加时,可能超出原先定义的元素个数,当数据减少时,造成内存浪费
  • 数据查询比较方便,根据下标就可以直接找到元素,时间复杂度O(1),增加和删除比较复杂,需要移动操作数所在位置后的所有数据,时间复杂度为O(N)

2.2 链表

概念

一种物理存储单元上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

链表的特性
  • 链表动态进行存储分配,可适应数据动态增减
  • 插入、删除数据比较方便,时间复杂度为O(1),查询必须从头开始找起,时间复杂度为O(N),相当麻烦
常见的链表
  • 单链表,链表每一个元素都要保存一个指向下一个元素的指针
  • 双链表,每个元素既要保存到下一个元素的指针,还要保存一个上一个元素的指针
  • 循环链表,在最后一个元素中下一个元素指针指向首元素

链表和数组都是在堆里分配内存

应用

快速访问数据,较少或不插入和删除元素时,用数组更好
较多插入和删除元素时,使用链表数据结构更高效

3. 遍历一个树

四个遍历概念

  • 先序遍历,先访问根节点,再访问左子树,最后访问右子树
  • 后序遍历,先左子树,再右子树,最后根节点
  • 中序遍历,先左子树,再根节点,最后右子树
  • 层序遍历,每一层从左到右访问每一个节点

每一个子树遍历时依然按照此时的遍历顺序,可以采用递归实现遍历

4. 冒泡排序 Bubble Sort

4.1 算法描述

  • 比较相邻的元素,第一个比第二个大,则交换两个元素位置
  • 对每一个相邻元素作同样的工作,从开始第一对到结尾的最后一对,在最后的元素应该会是最大的数
  • 对所有元素重复以上操作,除了最后一个元素
  • 重复前面三个步骤,直到排序完成

4.2 复杂度

排序方法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性
冒泡排序O(n2),2在n的右上角标O(n2),2在n的右上角标O(n)O(1)稳定

如果两个元素相等,不会再交换位置,所以冒泡排序是一种稳定排序算法

4.3 代码实现

冒泡排序

public class BubbleSort{public static void bubbleSort(int[] arr){for(int i = 0; i< arr.length-1; i++){for(int j = 0; j< arr.length-i-1; j++){if(arr[j] > arr[j+1]){//当前面的值大于后面的值,交换位置int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}public static void main(String[] args){int[] arr = {4,2,5,1,9,3};bubbleSort(arr);for(int i : arr){System.out.print(i+"");}}
}

5. 快速排序 Quick Sort

5.1 算法描述

使用分治法将一串list分为两个子串sub-list,具体如下

  • 从数列中挑出一个元素,称为基准pivot
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任意一边)。在这个分区退出后,该基准数处于数列的中间位置,这个称为分区操作partition
  • 递归地rcursive将小于基准值元素的子数列和大于基准值元素的子数列排序

5.2 复杂度

排序方法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性
快速排序O(nlog2n),2在log右下角标O(n2), 2在n的右上角标O(nlog2n), 2在log右下角标O(nlog2n), 2在log右下角标稳定

key值的选取可以有多种形式,例如中间数或随机数,分别会对算法的复杂度产生不同的影响

5.3 代码实现

快速排序

public class QuickSort{public static void quickSort(int[] data, int low, int high){int i,j,temp,t;if(low>high){return;}i = low;j = high;//temp为基准位temp = data[low];System.out.println("基准位:"+temp);while(i<j){//先看右边,依次往左递减while(temp<=data[j]&&i<j){j--;}//再看左边,依次往右递增while(temp>=data[i]&&i<j){i++;}//如果满足条件则交换if(i<j){System.out.println("交换: "+data[i]+" 和 "+data[j]);t = data[j];data[j] = data[i];data[i] = t;System.out.println(java.util.Arrays.toString(data))}}//最后将基准位与i和j相等位置的数字互换System.out.println("基准位 "+temp+" 和i、j相遇的位置 "+data[i]+"交换");data[low] = data[i];data[i] = temp;System.out.println(java.util.Arrays.toString(data));//递归调用左半数组quickSort(data, low, j-1);//递归调用右半数组quickSort(data, j+1, high);}public static void main(String[] args){int[] data = {3, 44, 34, 5, 25, 58, 20, 1, 57, 23, 12, 60, 43};System.out.println("排序之前:\n"+java.util.Arrays.toString(data));quickSort(data, 0, data.length-1);System.out.println("排序之后:\n"+java.util.Arrays.toString(data));}}

6. 二分查找 Binary Search

6.1 算法描述

  • 二分查找又称为折半查找,是一种效率较高的查找方法,要求列表中的元素是有序排列的,即如果未排序则必须先排序才可进行二分查找
  • 假定表中元素按升序排序,将表中中间位置记录的关键字与查找的关键字进行比较,如果两者相等则查找成功
  • 如果不相等,利用中间位置记录将表分成前后两个子表,如果中间位置记录的关键字大于所要查找的关键字,则进行查找前一个子表,否则就去查后一个子表
  • 重复以上过程,知道找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功

6.2 复杂度

二分查找法
时间复杂度为O(log2n)
空间复杂度为O(1)

6.3 代码实现

二分法查找

public class BinarySearch{public static int binarySearch(int[] arr, int left, int right, int findValue){if(left>right){//递归推出条件, 找不到,返回-1return -1}int midIndex = (left+right)/2;if(finaValue<arr[midIndex]>){//向左递归查找return binarySearch(arr, left, midIndex, findValue);}else if(findValue>arr[midIndex]){//向右递归查找return binarySearch(arr, midIndex, right, findValue);}else{return midIndex;}}public static void main(String[] args){//注意:需要对已排序的数组进行二分查找int[] data = {-40, -30, -12, -1, 2, 33, 38, 49, 50};int i = binarySearch(data, 0, data.length, 33);System.out.println(i);}
}

6.4 拓展

当有序数组中有多个相同的数值时,如何将所有的数值都查到

代码

public class BinarySearch2{public static List<Integer> binarySearch2(int[] arr, int left, int right, int findValue){List<Integer> list = new ArrayList<>();if(left>right){//递归退出条件,找不到,返回-1return list;}int midIndex = (left+right)/2;int midValue = arr[midIndex];if(findValue<midValue){//向左递归查找return binarySearch2(arr, left, mdiIndex-1, findValue);}else if(findValue>midValue){//向右递归查找return binarySearch2(arr, midIndex+1, right, findValue);}else{System.out.println("midIndex="+midIndex);//向左扫描int temp = midIndex-1;while(true){if(temp<0||arr[temp]!=findValue){break;}if(arr[temp]==findValue){list.add(temp);}temp -= 1;}//将中间这个索引加入list.add(midIndex);//向右边扫描temp = midIndex + 1;while(true){if(temp>arr.length-1||arr[temp]!=findValue){break;}if(arr[temp]==findValue){list.add(temp);}temp += 1;}return list;}}public static void main(String[] args){//注意: 需要对已排序的数组进行二分查找int[] data = {1, 4, 10, 58, 100, 1000, 1200, 1234, 1234, 3000, 4000};List<Integer> list = binarySearch2(data, 0, data.length, 1234);System.out.println(list);}
}

感谢阅读,祝君暴富!


相关文章:

Java数据结构和算法相关面试题

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

网络安全风险评估

项目背景 随着信息化技术的快速发展&#xff0c;特别是面向社会、政府机构、企业等业务系统的投入使用&#xff0c;各组织机构对网络和信息系统安全防护都提出了新的要求。为满足安全需求&#xff0c;需对组织机构的网络和信息系统的安全进行一次系统全面的评估&#xff0c;以…...

ADAM优化算法与学习率调度器:深度学习中的关键工具

深度学习模型的训练效果离不开优化算法和学习率的选择。ADAM&#xff08;Adaptive Moment Estimation&#xff09;作为深度学习领域中广泛应用的优化算法之一&#xff0c;以其高效性和鲁棒性成为许多任务的默认选择。而学习率调度器则是优化算法的“助推器”&#xff0c;帮助训…...

岛屿数量C++11新特性

每日一题 200. 岛屿数量 class Solution {//使用深度的优先搜索来搜索岛屿图//遍历整个图片 当char数组的值为1时开始从这个点开始往外扩散搜索//注意处理边界 图不是正方形 public:int ans;int d[4][2] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};int N;int M;void dfs(vector<…...

Git 快速入门:全面了解与安装步骤

Git 快速入门&#xff1a;全面了解与安装步骤 一、关于Git 1.1 简介 Git 是一个开源的分布式版本控制系统&#xff0c;由 Linus Torvalds 于 2005 年创建&#xff0c;最初是为了更好地管理 Linux 内核开发而设计。 Git用于跟踪计算机文件的变化&#xff0c;特别是源代码文件…...

基于域自适应的双光融合

目录 引言DAF-Net编码器-解码器分支编码器部分融合层解码器部分 域自适应层概述多核最大均值差异&#xff08;MK-MMD&#xff09;第一阶段&#xff1a;编码器-解码器分支训练训练过程损失函数 第二阶段&#xff1a;融合层训练训练过程损失函数 实验与结果总结 文章声明&#xf…...

迭代器模式 (Iterator Pattern)

文章目录 迭代器模式 (Iterator Pattern)原理优点缺点示例代码场景描述1. 定义迭代器接口2. 定义集合接口3. 实现具体集合类4. 客户端代码输出结果 UML 类图使用场景优化与扩展小结 迭代器模式 (Iterator Pattern) 迭代器模式是一种 行为型设计模式&#xff0c;用于顺序访问集…...

039集——渐变色之:CAD中画彩虹()(CAD—C#二次开发入门)

&#xff08;来左边儿 跟我一起画个龙&#xff0c;在你右边儿 画一道彩虹 ~~~~~~~~~~~ &#xff09; 效果如下&#xff1a; namespace AcTools {public class Class1{public Wform.Timer timer;//定时器需建在类下面public static DateTime startTime;[CommandM…...

如何将 GitHub 私有仓库(private)转换为公共仓库(public)

文章目录 如何将 GitHub 私有仓库转换为公共仓库步骤 1: 登录 GitHub步骤 2: 导航到目标仓库步骤 3: 访问仓库设置步骤 4: 更改仓库可见性步骤 5: 确认更改步骤 6: 验证更改注意事项 如何将 GitHub 私有仓库转换为公共仓库 在软件开发领域&#xff0c;GitHub 是一个广受欢迎的…...

C++11 右值引用

目录 左值 右值 左值引用与右值引用比较 左值引用总结&#xff1a; 右值引用总结&#xff1a; 左值引用的使用场景&#xff1a; 引用传参和做返回值都可以提高效率(减少拷贝) 左值引用的短板&#xff1a; 右值引用和移动语义解决上述问题&#xff1a; 下面就是有移动…...

WPS表格学习计划与策略

一、学习目标 掌握WPS表格的基本操作:包括新建、打开、保存工作簿,单元格的编辑与格式化,数据的输入与验证等。熟练运用WPS表格的数据处理功能:包括数据排序、筛选、分类汇总,以及使用公式和函数进行计算和分析。学会制作图表与数据可视化:掌握不同类型图表(如柱状图、折…...

Android 引入 proto 项目及使用方法

Proto&#xff08;Protocol Buffers&#xff09;是Google开发的一种语言无关、平台无关的序列化结构数据的方法&#xff0c;它类似于JSON和XML&#xff0c;但相对于XML而言更小&#xff0c;相对于JSON而言解析更快&#xff0c;支持多语言。以下是将Proto引入Android项目的方法及…...

VSOMEIP主要流程的时序

请求服务: client应用&#xff1a; ​ application_impl::request_service ​ routing_manager_client::request_service (老版本是routing_manager_proxy) ​ routing_manager_client::send_request_services ​ protocol::request_service_command its_command; // 创建…...

右值引用和移动语义:

C 右值引用和移动语义详解 在 C 的发展历程中&#xff0c;右值引用和移动语义的引入带来了显著的性能提升和编程灵活性。本文将深入探讨右值引用和移动语义的概念、用法以及重要性。 一、引言 C 作为一门高效的编程语言&#xff0c;一直在不断演进以满足现代软件编程的需求。…...

经纬高LLA转地心地固ECEF坐标,公式,代码

经纬高转地心地固的目的 坐标系转换是gis或者slam系统常见操作。GNSS获取的一般是经纬高&#xff0c;经纬高在slam系统里无法应用&#xff0c;slam系统一般是xyz互相垂直的笛卡尔坐标系&#xff0c;所以需要把GNSS的经纬高转到直角坐标系地心地固ECEF或者高斯投影GKP。 划重点…...

VUE前端实现天爱滑块验证码--详细教程

第一步&#xff1a; Git地址&#xff1a;tianai-captcha-demo: 滑块验证码demo 找到目录 src/main/resources/static,拷贝 static 并改名为 tac 即可。 第二步&#xff1a; 将改为 tac 的文件&#xff0c;放进项目根目录中&#xff0c;如下图&#xff1a; 第三步&#xff1…...

【链表】【删除节点】【刷题笔记】【灵神题单】

237.删除链表的节点 链表删除节点的本质是不用删除&#xff0c;只需要操作指针&#xff0c;跳过需要删除的节点&#xff0c;指向下下一个节点即可&#xff01; 删除某个节点&#xff0c;但是不知道这个节点的前一个节点&#xff0c;也不知道头节点&#xff01;摘自力扣评论区…...

springboot339javaweb的新能源充电系统pf(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;新能源充电系统的设计与实现 摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解…...

【嵌入式——QT】QT制作安装包

第一步 QT程序写好之后&#xff0c;编译release版本 第二步 拿到release生成的.exe文件 第三步 新建文件夹deploy 第四步 将.exe文件复制到deploy目录下 第五步 在该目录下输入cmd指令&#xff0c;回车 第六步 在打开的命令窗口下输入 windeployqt TegNetCom_1.0.…...

python的文件操作练习

文件操作&#xff1a;成绩统计 有一个文件grades.txt&#xff0c;文件内容是每行一个学生的成绩&#xff08;格式&#xff1a;姓名,成绩&#xff09;。要求&#xff1a; 读取文件内容&#xff0c;统计所有学生的平均成绩&#xff1b; 将不及格&#xff08;<60分&#xff09…...

jQuery九宫格抽奖,php处理抽奖信息

功能介绍 jQuery九宫格抽奖是一种基于jQuery库的前端抽奖效果。通过九宫格的形式展示抽奖项&#xff0c;用户点击抽奖按钮后&#xff0c;九宫格开始旋转&#xff0c;最终停在一个随机位置上&#xff0c;此位置对应的抽奖项为用户的中奖结果。 本文实现九宫格的步骤为&#xf…...

2024年一级建造师考试成绩,即将公布!

一级建造师考试成绩一般在考试结束后3个月左右的时间公布&#xff01; 根据官方通知&#xff0c;重庆、江苏、青海、江西、云南、湖南、福建、北京、山西、黑龙江等地在今年一建报名通知里提到&#xff1a;2024年一级建造师考试成绩预计于2024年12月上旬公布。考生可在这个时间…...

M4V 视频是一种什么格式?如何把 M4V 转为 MP4 格式?

M4V 是一种视频文件格式&#xff0c;主要由苹果公司用于其产品和服务中&#xff0c;如 iTunes Store 上的电影和电视节目。这种格式可以包含受版权保护的内容&#xff0c;并且通常与苹果的 DRM&#xff08;数字版权管理&#xff09;技术结合使用&#xff0c;以限制内容的复制和…...

Leetcode 每日一题 104.二叉树的最大深度

目录 问题描述 示例 示例 1&#xff1a; 示例 2&#xff1a; 约束条件 题解 方法一&#xff1a;广度优先搜索&#xff08;BFS&#xff09; 步骤 代码实现 方法二&#xff1a;递归 步骤 代码实现 结论 问题描述 给定一个二叉树 root&#xff0c;我们需要返回其最大…...

文件上传漏洞:你的网站安全吗?

文章目录 文件上传漏洞攻击方式&#xff1a;0x01绕过前端限制0x02黑名单绕过1.特殊解析后缀绕过2..htaccess解析绕过3.大小写绕过4.点绕过5.空格绕过6.::$DATA绕过7.配合中间件解析漏洞8.双后缀名绕过9.短标签绕过 0x03白名单绕过1.MIME绕过(Content-Type绕过)2.%00截断3.0x00截…...

AWS账号提额

Lightsail提额 控制台右上角&#xff0c;用户名点开&#xff0c;选择Service Quotas 在导航栏中AWS服务中找到lightsail点进去 在搜索框搜索instance找到相应的实例类型申请配额 4.根据自己的需求选择要提额的地区 5.根据需求来提升配额数量,提升小额配额等大约1小时生效 Ligh…...

电子应用设计方案-29:智能云炒菜系统方案设计

智能云炒菜系统方案设计 一、系统概述 本智能云炒菜系统旨在为用户提供便捷、高效、个性化的烹饪体验&#xff0c;结合云技术实现远程控制、食谱分享、智能烹饪流程优化等功能。 二、系统组成 1. 炒菜锅主体 - 高品质不粘锅内胆&#xff0c;易于清洁和维护。 - 加热装置&#x…...

腾讯rapidJson使用例子

只需要把库的头文件拿下来加入项目中使用就行&#xff0c;我是以二进制文件存储内容并解析&#xff1a; #include <iostream> #include <fstream> #include <string> #include "rapidjson/document.h" #include "rapidjson/error/en.h"…...

UE5_CommonUI简单使用(2)

上篇我是简单写了一下CommonUI使用的初始设置以及Common Activatable Widget和Common Activatable Widget Stack以及Common 控件Style以及鼠标控制的一些内容,这些对于了解UMG的朋友来说没什么难度,唯一需要注意的就是Common Activatable Widget Stack堆栈管理只能是用来管理…...

探讨播客的生态系统

最近对播客发生了兴趣&#xff0c;从而引起了对播客背后的技术&#xff0c;生态的关注。本文谈谈播客背后的技术生态系统。 播客很简单 播客&#xff08;podcast&#xff09;本质上就是以语音的方式发布信息。它和博客非常类似。如果将CSDN 网站上的文字加一个语音播报。CSDN …...

海南营销型网站建设/优化大师app

微软一直宣称Exchange 的传输引擎足够负担非常大量的邮件传输&#xff08;EXTREMELY large volumes of messages&#xff09;,但是在现实场景中&#xff0c;很多时候都会出现服务器的物理资源不够无法负担这么大量的出站与入站邮件量&#xff0c;换句话说微软的意思是俺设计的产…...

县科协微网站建设/安装百度

Map 和 Set 目录 Map 和 Set 概念&#xff1a; 主要内容&#xff1a; Mao集合 Map的常用方法 注意事项 HashMap,TreeMap和LinkedHashMap TreeMap和HashMap的区别 Set集合 作用&#xff1a; 常用方法&#xff1a; 注意事项 Map 和 Set 概念&#xff1a; Map和…...

南充营销型网站建设/漯河网站seo

分类算法很多&#xff0c;有的效果比较好&#xff0c;有的效果稍微差点。 这里还有一种“新”分类算法&#xff0c;就是把多个分类器组合成一个分类器&#xff0c;主要有bagging 和boosting两种。 bagging算法&#xff1a;从原始数据中随机抽取n个样本&#xff0c;重复s次&am…...

做电影网站怎么选服务器/品牌推广外包

夜光序言&#xff1a; 有没有想过你的那点心思谁能够当做礼物&#xff0c;你又能留给谁?最终用来安慰自己&#xff0c;成长是需要代价的。就像是最让你痛心的&#xff0c;并不是没有得到&#xff0c;而是已失去。最让人难受的&#xff0c;就像是你得到了&#xff0c;拥有过&am…...

江门网站制作软件/搜索引擎营销的简称是

看面经的时候看到这样两个问题&#xff1a; BFC是什么&#xff1f; 举个例子&#xff1f; margin重叠问题&#xff1f;如何解决&#xff1f; 之前没有系统的了解过&#xff0c;所以就整理一下相关的知识。 1. BFC 官方定义&#xff1a; BFC&#xff08;Block Formatting Cont…...

四个常见的网络营销方式/北京网站优化方法

Association rule mining 是数据挖掘中最活跃的研究方法之一&#xff0c;可以用来发现事情之间的联系&#xff0c;最早是为了发现超市交易数据库中不同的商品之间的关系。 这里有一则沃尔玛超市的趣闻。沃尔玛曾今对数据仓库中一年多的原始交易数据进行了详细的分析&#xff0c…...