数据结构#xff1a;数组、栈、队列、字符串、链表、树、图、堆、哈希表等。

数据结构是为实现对计算机数据有效使用的各种数据组织形式#xff0c;服务于各类计算机操作。

不同的…

算法搜索、查找、排序、双指针、回溯、分治、动态规划、贪心、位运算、数学等。

数据结构是为实现对计算机数据有效使用的各种数据组织形式服务于各类计算机操作。

不同的数据结构具有各自对应的适用场景旨在降低各种算法计算的时间与空间复杂度达到最佳的任务执行效率。

常见的数据结构可分为「线性数据结构」与「非线性数据结构」具体为「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。

数组是将相同类型的元素存储于连续内存空间的数据结构其长度不可变。

链表以节点为单位每个元素都是一个独立对象在内存空间的存储是非连续的。

链表的节点对象具有两个成员变量「值

val」「后继节点引用

edge」组成每条边连接一对顶点。

根据边的方向有无图可分为「有向图」和「无向图」。

使用数组

为节点数量。

因此当边数量明显少于节点数量时使用邻接矩阵存储图会造成较大的内存浪费。

因此邻接表

适合存储稀疏图顶点较多、边较少

堆是一种基于「完全二叉树」的数据结构可使用数组实现。

以堆为原理的排序算法称为「堆排序」基于堆实现的数据结构为「优先队列」。

堆分为「大顶堆」和「小顶堆」大小顶堆任意节点的值不大于小于其父节点的值。

完全二叉树定义

元素的小顶堆。

将堆完全二叉树中的结点按层编号即可映射到右边的数组存储形式。

push()」和「弹出

的情况下算法的「时间使用」和「空间使用」情况体现算法运行使用的时间和空间随「数据大小

、空间

假设各操作的运行时间为固定常数统计算法运行的「计算操作的数量」

根据输入数据的特点时间复杂度具有「最差」、「平均」、「最佳」三种情况分别使用

O(1)O(logN)O(N)O(NlogN)O(N^2)O(2^N)O(N!)

O(1)O(logN)O(N)O(NlogN)O(N2)O(2N)O(N!)

输入空间

算法运行过程中存储所有中间变量和对象等数据所需的空间大小输出空间

编译后程序指令所使用的内存空间。

算法中的各项变量使用的空间包括声明的常量、变量、动态数组、动态对象等使用的内存空间。

程序调用函数是基于栈实现的函数在调用期间占用常量大小的栈帧空间直至返回后释放。

对于算法的性能需要从时间和空间的使用情况来综合评价。

优良的算法应具备两个特性即时间和空间复杂度皆较低。

而实际上对于某个算法问题同时优化时间复杂度和空间复杂度是非常困难的。

降低时间复杂度往往是以提升空间复杂度为代价的反之亦然。

题目书店店员有一张链表形式的书单每个节点代表一本书节点中的值表示书的编号。

为更方便整理书架店员需要将书单倒过来排列就可以从最后一本书开始整理逐一将书放回到书架上。

请倒序返回这个书单链表。

/***

ve;while(head){st.push(head-val);head

head-next;}while(!st.empty()){ve.push_back(st.top());st.pop();}return

ve;}

};反转的实现就是一点小技巧需要用到三个指针变量类似于两个数交换的思想层次递进。

现在假设定义pre、phead、temp三个指针变量用phead指向链表的头结点而pre代表phead的前一个节点。

具体实现代码如下

ListNode*

}利用递归先递推至链表末端回溯时依次将节点值加入列表即可实现链表值的倒序输出。

/***

;}track(head-next);res.push_back(head-val);}vectorint

head)

};题目给定单向链表的头指针和一个要删除的节点的值定义一个函数删除该节点。

返回删除后的链表的头节点。

/***

prenode;while(temp-next){if(temp-next-val

val){temp-next

nullptr;for(nodehead;node;nodenode-next){n;}for(node

head;ncnt;n--){node

right-next;cnt--;}while(right){right

right-next;left

l1、l2分别记录了两套核心肌群训练项目编号请合并这两个训练计划按训练项目编号

记录于链表并返回。

注意新链表是通过拼接给定的两个链表的所有节点组成的。

/***

的大小关系确定节点添加顺序两节点指针交替前进直至遍历完毕。

引入伪头节点

由于初始状态合并链表中无节点因此循环第一轮时无法将节点添加到合并链表中。

解决方案初始化一个辅助节点

dum

记录了两套核心肌群训练计划节点值为训练项目编号。

两套计划仅有前半部分热身项目不同后续正式训练项目相同。

请设计一个程序找出并返回第一个正式训练项目编号。

如果两个链表不存在相交节点返回

null

pbnullptr?headA:pb-next;}return

pa;}

指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。

复制链表中的指针都不应指向原链表中的节点

Definition

head;node!nullptr;nodenode-next-next){Node*

newnode

nullptr)?node-random-next:nullptr;}Node*

newhead

(newnode-next!nullptr)?newnode-next-next:nullptr;}return

newhead;