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

数据结构面试知识点总结3

#来自ウルトラマンティガ(迪迦)

1 线性表

最基本、最简单、最常用的一种数据结构。一个线性表是 n 个具有相同特性的数据元素的有限序列。

特征:数据元素之间是一对一的逻辑关系。

  • 第一个数据元素没有前驱,称为头结点;
  • 最后一个数据元素没有后继,称为尾结点;
  • 除了头结点和尾结点,其他数据元素有且仅有一个前驱和一个后继。

分类:

  • 顺序存储
  • 链式存储

2 顺序表

顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元,依次存储线性表中的各个元素。

public class SequenceList<T> implements Iterable<T> {//存储元素的数组private T[] eles;//记录当前顺序表中的元素个数private int N;//构造方法public SequenceList(int capacity) {//初始化数组this.eles = (T[]) new Object[capacity];//初始化长度this.N = 0;}//将一个线性表置为空表public void clear() {this.N = 0;}//判断当前线性表是否为空表public boolean isEmpty() {return N == 0;}//获取线性表的长度public int length() {return N;}//获取指定位置的元素public T get(int i) {return eles[i];}//向线型表中添加元素 tpublic void insert(T t) {if (N == eles.length) {resize(2 * eles.length);}eles[N++] = t;}//在 i 元素处插入元素 tpublic void insert(int i, T t) {if (N == eles.length) {resize(2 * eles.length);}//先把i索引处的元素及其后面的元素依次向后移动一位for (int index = N; index > i; index--) {eles[index] = eles[index - 1];}//再把t元素放到i索引处即可eles[i] = t;//元素个数+1N++;}//删除指定位置i处的元素,并返回该元素public T remove(int i) {//记录索引i处的值T current = eles[i];//索引i后面元素依次向前移动一位即可for (int index = i; index < N - 1; index++) {eles[index] = eles[index + 1];}//元素个数-1N--;if (N < eles.length / 4) {resize(eles.length / 2);}return current;}//查找t元素第一次出现的位置public int indexOf(T t) {for (int i = 0; i < N; i++) {if (eles[i].equals(t)) {return i;}}return -1;}//根据参数newSize,重置eles的大小public void resize(int newSize) {//定义一个临时数组,指向原数组T[] temp = eles;//创建新数组eles = (T[]) new Object[newSize];//把原数组的数据拷贝到新数组即可for (int i = 0; i < N; i++) {eles[i] = temp[i];}}@Overridepublic Iterator<T> iterator() {return new SIterator();}private class SIterator implements Iterator {private int cursor;public SIterator() {this.cursor = 0;}@Overridepublic boolean hasNext() {return cursor < N;}@Overridepublic T next() {return eles[cursor++];}}
}

复杂度:

get(i):时间复杂度 O(1)

insert(int i, T t):时间复杂度 O(n)

remove(int i):时间复杂度 O(n)

3 链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点(链表中的每一个元素称为结点)组成,结点可以在运行时动态生成。

//链表结点
public class Node<T> { //存储元素 public T item; //指向下一个结点 public Node next; public Node(T item, Node next) { this.item = item;this.next = next; } 
}

复杂度:

get(i):时间复杂度 O(n)

insert(int i, T t):时间复杂度 O(1)

remove(int i):时间复杂度 O(1)

3.1 单向链表

单向链表是链表的一种,它由多个结点组成,每个结点都由一个数据域和一个指针域组成,数据域用来存储数据,指针域用来指向其后继结点。链表的头结点的数据域不存储数据,指针域指向第一个真正存储数据的结点。

public class LinkList<T> implements Iterable<T> {//头结点private Node head;//链表的长度private int N;//结点类private class Node {//存储数据T item;//下一个结点Node next;public Node(T item, Node next) {this.item = item;this.next = next;}}public LinkList() {//初始化头结点、this.head = new Node(null, null);//初始化元素个数this.N = 0;}//清空链表public void clear() {head.next = null;this.N = 0;}//获取链表的长度public int length() {return N;}//判断链表是否为空public boolean isEmpty() {return N == 0;}//获取指定位置i出的元素public T get(int i) {//通过循环,从头结点开始往后找,依次找i次,就可以找到对应的元素Node n = head.next;for (int index = 0; index < i; index++) {n = n.next;}return n.item;}//向链表中添加元素tpublic void insert(T t) {//找到当前最后一个结点Node n = head;while (n.next != null) {n = n.next;}//创建新结点,保存元素tNode newNode = new Node(t, null);//让当前最后一个结点指向新结点n.next = newNode;//元素的个数+1N++;}//向指定位置i出,添加元素tpublic void insert(int i, T t) {//找到i位置前一个结点Node pre = head;for (int index = 0; index <= i - 1; index++) {pre = pre.next;}//找到i位置的结点Node curr = pre.next;//创建新结点,并且新结点需要指向原来i位置的结点Node newNode = new Node(t, curr);//原来i位置的前一个节点指向新结点即可pre.next = newNode;//元素的个数+1N++;}//删除指定位置i处的元素,并返回被删除的元素public T remove(int i) {//找到i位置的前一个节点Node pre = head;for (int index = 0; index <= i - 1; i++) {pre = pre.next;}//要找到i位置的结点Node curr = pre.next;//找到i位置的下一个结点Node nextNode = curr.next;//前一个结点指向下一个结点pre.next = nextNode;//元素个数-1N--;return curr.item;}//查找元素t在链表中第一次出现的位置public int indexOf(T t) {//从头结点开始,依次找到每一个结点,取出item,和t比较,如果相同,就找到了Node n = head;for (int i = 0; n.next != null; i++) {n = n.next;if (n.item.equals(t)) {return i;}}return -1;}@Overridepublic Iterator<T> iterator() {return new LIterator();}private class LIterator implements Iterator {private Node n;public LIterator() {this.n = head;}@Overridepublic boolean hasNext() {return n.next != null;}@Overridepublic Object next() {n = n.next;return n.item;}}//用来反转整个链表public void reverse() {//判断当前链表是否为空链表,如果是空链表,则结束运行,如果不是,则调用重载的reverse方法完成反转if (isEmpty()) {return;}reverse(head.next);}//反转指定的结点curr,并把反转后的结点返回public Node reverse(Node curr) {if (curr.next == null) {head.next = curr;return curr;}//递归的反转当前结点curr的下一个结点;返回值就是链表反转后,当前结点的上一个结点Node pre = reverse(curr.next);//让返回的结点的下一个结点变为当前结点curr;pre.next = curr;//把当前结点的下一个结点变为nullcurr.next = null;return curr;}
}

3.2 双向链表

双向链表也叫双向表,是链表的一种,它由多个结点组成,每个结点都由一个数据域和两个指针域组成,数据域用来存储数据,其中一个指针域用来指向其后继结点,另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据,指向前驱结点的指针域值为null,指向后继结点的指针域指向第一个真正存储数据的结点。

public class TowWayLinkList<T> implements Iterable<T> {//首结点private Node head;//最后一个结点private Node last;//链表的长度private int N;//结点类private class Node {//存储数据T item;//指向上一个结点Node pre;//指向下一个结点Node next;public Node(T item, Node pre, Node next) {this.item = item;this.pre = pre;this.next = next;}}public TowWayLinkList() {//初始化头结点和尾结点this.head = new Node(null, null, null);this.last = null;//初始化元素个数this.N = 0;}//清空链表public void clear() {this.head.next = null;this.head.pre = null;this.head.item = null;this.last = null;this.N = 0;}//获取链表长度public int length() {return N;}//判断链表是否为空public boolean isEmpty() {return N == 0;}//获取第一个元素public T getFirst() {if (isEmpty()) {return null;}return head.next.item;}//获取最后一个元素public T getLast() {if (isEmpty()) {return null;}return last.item;}//插入元素tpublic void insert(T t) {if (isEmpty()) {//如果链表为空://创建新的结点Node newNode = new Node(t, head, null);//让新结点称为尾结点last = newNode;//让头结点指向尾结点head.next = last;} else {//如果链表不为空Node oldLast = last;//创建新的结点Node newNode = new Node(t, oldLast, null);//让当前的尾结点指向新结点oldLast.next = newNode;//让新结点称为尾结点last = newNode;}//元素个数+1N++;}//向指定位置i处插入元素tpublic void insert(int i, T t) {//找到i位置的前一个结点Node pre = head;for (int index = 0; index < i; index++) {pre = pre.next;}//找到i位置的结点Node curr = pre.next;//创建新结点Node newNode = new Node(t, pre, curr);//让i位置的前一个结点的下一个结点变为新结点pre.next = newNode;//让i位置的前一个结点变为新结点curr.pre = newNode;//元素个数+1N++;}//获取指定位置i处的元素public T get(int i) {Node n = head.next;for (int index = 0; index < i; index++) {n = n.next;}return n.item;}//找到元素t在链表中第一次出现的位置public int indexOf(T t) {Node n = head;for (int i = 0; n.next != null; i++) {n = n.next;if (n.next.equals(t)) {return i;}}return -1;}//删除位置i处的元素,并返回该元素public T remove(int i) {//找到i位置的前一个结点Node pre = head;for (int index = 0; index < i; index++) {pre = pre.next;}//找到i位置的结点Node curr = pre.next;//找到i位置的下一个结点Node nextNode = curr.next;//让i位置的前一个结点的下一个结点变为i位置的下一个结点pre.next = nextNode;//让i位置的下一个结点的上一个结点变为i位置的前一个结点nextNode.pre = pre;//元素的个数-1N--;return curr.item;}@Overridepublic Iterator<T> iterator() {return new TIterator();}private class TIterator implements Iterator {private Node n;public TIterator() {this.n = head;}@Overridepublic boolean hasNext() {return n.next != null;}@Overridepublic Object next() {n = n.next;return n.item;}}
}

3.3 循环链表

链表整体要形成一个圆环状。让单向链表的最后一个节点的指针指向头结点。

4 题目

4.1 反转链表

LeetCode:24 题

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while(cur != null) {ListNode tmp =  cur.next;cur.next = pre;pre = cur;cur = tmp;}return pre;}
}

4.2 快慢指针

给定一个链表,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回 true 。 否则,返回 false 。

示例:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
public class Solution {public boolean hasCycle(ListNode head) {//快慢指针if(head == null || head.next == null) return false;ListNode slow = head;ListNode fast = head.next;while(slow != fast){if(fast == null || fast.next == null) return false;slow = slow.next;fast = fast.next.next;}return true;}
}

相关文章:

数据结构面试知识点总结3

#来自ウルトラマンティガ&#xff08;迪迦&#xff09; 1 线性表 最基本、最简单、最常用的一种数据结构。一个线性表是 n 个具有相同特性的数据元素的有限序列。 特征&#xff1a;数据元素之间是一对一的逻辑关系。 第一个数据元素没有前驱&#xff0c;称为头结点&#xff1…...

python-爬虫实例(5):将进酒,杯莫停!

目录 前言 将进酒&#xff0c;杯莫停&#xff01; 一、浇给 二、前摇 1.导入selenium库 2.下载浏览器驱动 三、爬虫四步走 1.UA伪装 2.获取url 3.发送请求 4.获取响应数据进行解析并保存 总结 前言 博主身为一个农批&#xff0c;当然要尝试爬取王者荣耀的东西啦。 将进…...

AGI 之 【Hugging Face】 的【从零训练Transformer模型】之二 [ 从零训练一个模型 ] 的简单整理

AGI 之 【Hugging Face】 的【从零训练Transformer模型】之二 [ 从零训练一个模型 ] 的简单整理 目录 AGI 之 【Hugging Face】 的【从零训练Transformer模型】之二 [ 从零训练一个模型 ] 的简单整理 一、简单介绍 二、Transformer 1、模型架构 2、应用场景 3、Hugging …...

十大排序的稳定性和时间复杂度

十大排序算法的稳定性和时间复杂度是数据结构和算法中的重要内容。 以下是对这些算法的稳定性和时间复杂度的详细分析&#xff1a; 稳定性 稳定性指的是排序算法在排序过程中是否能够保持相等元素的原始相对顺序。根据这个定义&#xff0c;我们可以将排序算法分为稳定排序和…...

【系列教程之】1、点亮一个LED灯

1、点亮一个LED灯 作者将狼才鲸创建日期2024-07-23 CSDN教程目录地址&#xff1a;【目录】8051汇编与C语言系列教程本Gitee仓库原始地址&#xff1a;才鲸嵌入式/8051_c51_单片机从汇编到C_从Boot到应用实践教程 本源码包含C语言和汇编工程&#xff0c;能直接在电脑中通过Keil…...

搜维尔科技:Manus Metagloves使用精确的量子跟踪技术捕捉手部每一个细节动作

Manus Metagloves使用精确的量子跟踪技术捕捉手部每一个细节动作 搜维尔科技&#xff1a;Manus Metagloves使用精确的量子跟踪技术捕捉手部每一个细节动作...

机器学习 | 阿里云安全恶意程序检测

目录 一、数据探索1.1 数据说明1.2 训练集数据探索1.2.1 数据特征类型1.2.2 数据分布1.2.3 缺失值1.2.4 异常值1.2.5 标签分布探索 1.3 测试集探索1.3.1 数据信息1.3.2 缺失值1.3.3 数据分布1.3.4 异常值 1.4 数据集联合分析1.4.1 file_id 分析1.4.2 API 分析 二、特征工程与基…...

python打包exe文件-实现记录

1、使用pyinstaller库 安装库&#xff1a; pip install pyinstaller打包命令标注主入库程序&#xff1a; pyinstaller -F.\程序入口文件.py 出现了一个问题就是我在打包运行之后会出现有一些插件没有被打包。 解决问题&#xff1a; 通过添加--hidden-importcomtypes.strea…...

基本的DQL语句-单表查询

一、DQL语言 DQL(Data Query Language 数据查询语言)。用途是查询数据库数据&#xff0c;如SELECT语句。是SQL语句 中最核心、最重要的语句&#xff0c;也是使用频率最高的语句。其中&#xff0c;可以根据表的结构和关系分为单表查询和多 表联查。 注意&#xff1a;所有的查询…...

Vue3 对比 Vue2

相关信息简介2020年9月18日&#xff0c;Vue.js发布3.0版本&#xff0c;代号&#xff1a;One Piece&#xff08;海贼王&#xff09; 2 年多开发, 100位贡献者, 2600次提交, 600次 PR、30个RFC Vue3 支持 vue2 的大多数特性 可以更好的支持 Typescript&#xff0c;提供了完整的…...

2024中国大学生算法设计超级联赛(1)

&#x1f680;欢迎来到本文&#x1f680; &#x1f349;个人简介&#xff1a;陈童学哦&#xff0c;彩笔ACMer一枚。 &#x1f3c0;所属专栏&#xff1a;杭电多校集训 本文用于记录回顾总结解题思路便于加深理解。 &#x1f4e2;&#x1f4e2;&#x1f4e2;传送门 A - 循环位移解…...

offer题目51:数组中的逆序对

题目描述&#xff1a;在数组中的两个数字&#xff0c;如果前面一个数字大于后面的数字&#xff0c;则这两个数字组成一个逆序对。输入一个数组&#xff0c;求出这个数组中的逆序对的总数。例如&#xff0c;在数组{7,5,6,4}中&#xff0c;一共存在5个逆序对&#xff0c;分别是(7…...

45、PHP 实现滑动窗口的最大值

题目&#xff1a; PHP 实现滑动窗口的最大值 描述&#xff1a; 给定一个数组和滑动窗口的大小&#xff0c;找出所有滑动窗口里数值的最大值。 例如&#xff1a; 如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3&#xff0c; 那么一共存在6个滑动窗口&#xff0c; 他们的最大值…...

【计算机视觉】siamfc论文复现实现目标追踪

什么是目标跟踪 使用视频序列第一帧的图像(包括bounding box的位置)&#xff0c;来找出目标出现在后序帧位置的一种方法。 什么是孪生网络结构 孪生网络结构其思想是将一个训练样本(已知类别)和一个测试样本(未知类别)输入到两个CNN(这两个CNN往往是权值共享的)中&#xff0…...

数学建模学习(111):改进遗传算法(引入模拟退火、轮盘赌和网格搜索)求解JSP问题

文章目录 一、车间调度问题1.1目前处理方法1.2简单案例 二、基于改进遗传算法求解车间调度2.1车间调度背景介绍2.2遗传算法介绍2.2.1基本流程2.2.2遗传算法的基本操作和公式2.2.3遗传算法的优势2.2.4遗传算法的不足 2.3讲解本文思路及代码2.4算法执行结果&#xff1a; 三、本文…...

Golang | Leetcode Golang题解之第241题为运算表达式设计优先级

题目&#xff1a; 题解&#xff1a; const addition, subtraction, multiplication -1, -2, -3func diffWaysToCompute(expression string) []int {ops : []int{}for i, n : 0, len(expression); i < n; {if unicode.IsDigit(rune(expression[i])) {x : 0for ; i < n &…...

Unity客户端接入原生Google支付

Unity客户端接入原生Google支付 1. Google后台配置2. 开始接入Java部分C#部分Lua部分 3. 导出工程打包测试参考踩坑注意 1. Google后台配置 找到内部测试&#xff08;这个测试轨道过审最快&#xff09;&#xff0c;打包上传&#xff0c;这个包不需要接入支付&#xff0c;如果已…...

Spring Cloud之五大组件

Spring Cloud 是一系列框架的有序集合&#xff0c;为开发者提供了快速构建分布式系统的工具。这些组件可以帮助开发者做服务发现&#xff0c;配置管理&#xff0c;负载均衡&#xff0c;断路器&#xff0c;智能路由&#xff0c;微代理&#xff0c;控制总线等。以下是 Spring Cl…...

在 CentOS 7 上安装 Docker 并安装和部署 .NET Core 3.1

1. 安装 Docker 步骤 1.1&#xff1a;更新包索引并安装依赖包 先安装yum的扩展&#xff0c;yum-utils提供了一些额外的工具&#xff0c;这些工具可以执行比基本yum命令更复杂的任务 sudo yum install -y yum-utils sudo yum update -y #更新系统上已安装的所有软件包到最新…...

redis的学习(一):下载安装启动连接

简介 redis的下载&#xff0c;安装&#xff0c;启动&#xff0c;连接使用 nosql nosql&#xff0c;即非关系型数据库&#xff0c;和传统的关系型数据库的对比&#xff1a; sqlnosql数据结构结构化非结构化数据关联关联的非关联的查询方式sql查询非sql查询事务特性acidbase存…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...