室内设计师服务平台,谷歌seo和百度区别,线上教育,从零开始学做网站cdsn算法#xff1a;搜索、查找、排序、双指针、回溯、分治、动态规划、贪心、位运算、数学等。 数据结构#xff1a;数组、栈、队列、字符串、链表、树、图、堆、哈希表等。 数据结构是为实现对计算机数据有效使用的各种数据组织形式#xff0c;服务于各类计算机操作。不同的… 算法搜索、查找、排序、双指针、回溯、分治、动态规划、贪心、位运算、数学等。 数据结构数组、栈、队列、字符串、链表、树、图、堆、哈希表等。 数据结构是为实现对计算机数据有效使用的各种数据组织形式服务于各类计算机操作。不同的数据结构具有各自对应的适用场景旨在降低各种算法计算的时间与空间复杂度达到最佳的任务执行效率。常见的数据结构可分为「线性数据结构」与「非线性数据结构」具体为「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。数组是将相同类型的元素存储于连续内存空间的数据结构其长度不可变。链表以节点为单位每个元素都是一个独立对象在内存空间的存储是非连续的。链表的节点对象具有两个成员变量「值 val」「后继节点引用 next」 。栈是一种具有 「先入后出」 特点的抽象数据结构可使用数组或链表实现。通过常用操作「入栈 push()」,「出栈 pop()」展示了栈的先入后出特性。队列是一种具有 「先入先出」 特点的抽象数据结构可使用链表实现。通过常用操作「入队 push()」,「出队 pop()」展示了队列的先入先出特性。 树是一种非线性数据结构根据子节点数量可分为 「二叉树」 和 「多叉树」最顶层的节点称为「根节点 root」。以二叉树为例每个节点包含三个成员变量「值 val」、「左子节点 left」、「右子节点 right」 。图是一种非线性数据结构由「节点顶点vertex」和「边 edge」组成每条边连接一对顶点。根据边的方向有无图可分为「有向图」和「无向图」。 表示图的方法通常有两种邻接矩阵 使用数组 vertices 存储顶点邻接矩阵 edges 存储边edges[i] [j] 代表节点 i1 和 节点 j1 之间是否有边。 vertices [1, 2, 3, 4, 5]
edges [[0, 1, 1, 1, 1],[1, 0, 0, 1, 0],[1, 0, 0, 0, 1],[1, 1, 0, 0, 1],[1, 0, 1, 1, 0]]邻接表 使用数组 vertices 存储顶点邻接表 edges 存储边。 edges 为一个二维容器第一维 i 代表顶点索引第二维 edges[i] 存储此顶点对应的边集和例如 edges[0][1,2,3,4] 代表 vertices[0] 的边集合为 [1,2,3,4] 。 vertices [1, 2, 3, 4, 5]
edges [[1, 2, 3, 4],[0, 3],[0, 4],[0, 1, 4],[0, 2, 3]]邻接矩阵 VS 邻接表 邻接矩阵的大小只与节点数量有关即 N 2 N^2 N2 其中 N 为节点数量。因此当边数量明显少于节点数量时使用邻接矩阵存储图会造成较大的内存浪费。因此邻接表 适合存储稀疏图顶点较多、边较少 邻接矩阵 适合存储稠密图顶点较少、边较多。 散列表是一种非线性数据结构通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」以实现高效的元素查找。则可通过建立姓名为 key 学号为 value 的散列表实现此需求代码如下 # 初始化散列表
dic {}
# 添加 key - value 键值对
dic[小力] 10001
dic[小特] 10002
dic[小扣] 10003
# 从姓名查找学号
dic[小力] # - 10001
dic[小特] # - 10002
dic[小扣] # - 10003实际的 Hash 函数需保证低碰撞率、 高鲁棒性等以适用于各类数据和场景。 堆是一种基于「完全二叉树」的数据结构可使用数组实现。以堆为原理的排序算法称为「堆排序」基于堆实现的数据结构为「优先队列」。堆分为「大顶堆」和「小顶堆」大小顶堆任意节点的值不大于小于其父节点的值。 完全二叉树定义 设二叉树深度为 k 若二叉树除第 k 层外的其它各层第 1 至 k−1 层的节点达到最大个数且处于第 k 层的节点都连续集中在最左边则称此二叉树为完全二叉树。 为包含 1, 4, 2, 6, 8 元素的小顶堆。将堆完全二叉树中的结点按层编号即可映射到右边的数组存储形式。 通过使用「优先队列」的「压入 push()」和「弹出 pop()」操作即可完成堆排序实现代码如下 from heapq import heappush, heappop
# 初始化小顶堆
heap []
# 元素入堆
heappush(heap, 1)
heappush(heap, 4)
heappush(heap, 2)
heappush(heap, 6)
heappush(heap, 8)
# 元素出堆从小到大
heappop(heap) # - 1
heappop(heap) # - 2
heappop(heap) # - 4
heappop(heap) # - 6
heappop(heap) # - 8算法复杂度旨在计算在输入数据量 N 的情况下算法的「时间使用」和「空间使用」情况体现算法运行使用的时间和空间随「数据大小 N 」而增大的速度。算法复杂度主要可从 时间 、空间 两个角度评价 时间 假设各操作的运行时间为固定常数统计算法运行的「计算操作的数量」 以代表算法运行所需时间 空间 统计在最差情况下算法运行所需使用的「最大空间」 根据输入数据的特点时间复杂度具有「最差」、「平均」、「最佳」三种情况分别使用 O , Θ , Ω 三种符号表示。 根据从小到大排列常见的算法时间复杂度主要有 O ( 1 ) O ( l o g N ) O ( N ) O ( N l o g N ) O ( N 2 ) O ( 2 N ) O ( N ! ) 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!) 空间复杂度涉及的空间类型有 输入空间 存储输入数据所需的空间大小暂存空间 算法运行过程中存储所有中间变量和对象等数据所需的空间大小输出空间 算法运行返回时存储输出数据所需的空间大小 通常情况下空间复杂度指在输入数据大小为 N 时算法运行所使用的「暂存空间」「输出空间」的总体大小。 编译后程序指令所使用的内存空间。算法中的各项变量使用的空间包括声明的常量、变量、动态数组、动态对象等使用的内存空间。程序调用函数是基于栈实现的函数在调用期间占用常量大小的栈帧空间直至返回后释放。 对于算法的性能需要从时间和空间的使用情况来综合评价。优良的算法应具备两个特性即时间和空间复杂度皆较低。而实际上对于某个算法问题同时优化时间复杂度和空间复杂度是非常困难的。降低时间复杂度往往是以提升空间复杂度为代价的反之亦然。
题目书店店员有一张链表形式的书单每个节点代表一本书节点中的值表示书的编号。为更方便整理书架店员需要将书单倒过来排列就可以从最后一本书开始整理逐一将书放回到书架上。请倒序返回这个书单链表。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:vectorint reverseBookList(ListNode* head) {stackint st;vectorint 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* InvertList(link head){ListNode* pre,phead,temp;phead head; //将phead指向链表头做游标使用pre NULL; //pre为头指针之前的节点while(phead ! NULL){temp pre;pre phead;phead phead-next;pre-next temp; //pre接到之前的节点 }return pre;
}利用递归先递推至链表末端回溯时依次将节点值加入列表即可实现链表值的倒序输出。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:vectorint res;void track(ListNode* head){if(headnullptr){return ;}track(head-next);res.push_back(head-val);}vectorint reverseBookList(ListNode* head) {track(head);return res;}
};题目给定单向链表的头指针和一个要删除的节点的值定义一个函数删除该节点。返回删除后的链表的头节点。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {ListNode* prenode new ListNode(-1);prenode-next head;ListNode* temp prenode;while(temp-next){if(temp-next-val val){temp-next temp-next-next;break;}temp temp-next;}return prenode-next;}
};本题删除值为 val 的节点分需为两步定位节点、修改引用。定位节点 遍历链表直到 head.val val 时跳出即可定位目标节点。修改引用 设节点 cur 的前驱节点为 pre 后继节点为 cur.next 则执行 pre.next cur.next 即可实现删除 cur 节点。对于头节点没有前驱可以设置一个虚拟节点。
题目给定一个头节点为 head 的单链表用于记录一系列核心肌群训练编号请将该系列训练编号 倒序 记录于链表并返回。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* trainningPlan(ListNode* head) {ListNode *pre,*cur;pre nullptr;cur head;while(head){cur head;head head-next;cur-next pre;pre cur;}return pre;}
};时间复杂度 O(N) 遍历链表使用线性大小时间。空间复杂度 O(1) 变量 pre 和 cur 使用常数大小额外空间。
题目给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号请查找并返回倒数第 cnt 个训练项目编号。 /*** Definition for singly-linked list.
* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* trainingPlan(ListNode* head, int cnt) {int n0;ListNode* node nullptr;for(nodehead;node;nodenode-next){n;}for(node head;ncnt;n--){node node-next;}return node;}
};两次遍历用双指针只需要一次遍历 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* trainingPlan(ListNode* head, int cnt) {ListNode* left head;ListNode* right head;while(right cnt0){right right-next;cnt--;}while(right){right right-next;left left-next;}return left;}
};题目给定两个以 有序链表 形式记录的训练计划 l1、l2分别记录了两套核心肌群训练项目编号请合并这两个训练计划按训练项目编号 升序 记录于链表并返回。注意新链表是通过拼接给定的两个链表的所有节点组成的。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* trainningPlan(ListNode* l1, ListNode* l2) {if(!l1){return l2;}if(!l2)return l1;ListNode* res;ListNode* head;if(l1-val l2-val){head l1;l1 l1-next;}else{head l2;l2 l2-next;}res head;while(l1 l2){if(l1-val l2-val){res-next l1;l1 l1-next;}else{res-next l2;l2 l2-next;}res res-next;}if(l1){res-next l1;}if(l2){res-next l2;}return head;}
};链表 l1 , l2 是 递增 的因此容易想到使用双指针 l1 和 l2 遍历两链表根据 l1.val 和 l2.val 的大小关系确定节点添加顺序两节点指针交替前进直至遍历完毕。引入伪头节点 由于初始状态合并链表中无节点因此循环第一轮时无法将节点添加到合并链表中。解决方案初始化一个辅助节点 dum 作为合并链表的伪头节点将各节点添加至 dum 之后。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* trainningPlan(ListNode* l1, ListNode* l2) {ListNode* dumy new ListNode(0);ListNode* cur dumy;while(l1 l2){if(l1-val l2-val){cur-next l1;l1 l1-next;}else{cur-next l2;l2 l2-next;}cur cur-next;}cur-next l1!nullptr?l1:l2;return dumy-next;}
};题目某教练同时带教两位学员分别以链表 l1、l2 记录了两套核心肌群训练计划节点值为训练项目编号。两套计划仅有前半部分热身项目不同后续正式训练项目相同。请设计一个程序找出并返回第一个正式训练项目编号。如果两个链表不存在相交节点返回 null 。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// ListNode* pa headA;// ListNode* pb headB;if(!headB || !headA){return NULL;}ListNode* cur headA,*res NULL;while(cur){cur-val * -1;cur cur-next;}cur headB;while(cur){if(cur-val 0){res cur;break;}cur cur-next;}cur headA;while(cur){cur-val * -1;cur cur-next;}return res;}
};/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB){return nullptr;}ListNode *paheadA,*pbheadB;while(pa ! pb){pa panullptr?headB:pa-next;pb pbnullptr?headA:pb-next;}return pa;}
};题目请实现 copyRandomList 函数复制一个复杂链表。在复杂链表中每个节点除了有一个 next 指针指向下一个节点还有一个 random 指针指向链表中的任意节点或者 null。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 /*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val _val;next NULL;random NULL;}
};
*/
class Solution {
public:Node* copyRandomList(Node* head) {if(headnullptr){return nullptr;}for(Node* node head;node!nullptr;nodenode-next-next){Node* newnode new Node(node-val);newnode-next node -next;node-next newnode;}for(Node* node head;node!nullptr;node node-next-next){Node* newnode node-next;newnode-random (node-random ! nullptr)?node-random-next:nullptr;}Node* newhead head-next;for(Node* nodehead;node!nullptr;node node-next){Node* newnode node-next;node-next node-next-next;newnode-next (newnode-next!nullptr)?newnode-next-next:nullptr;}return newhead; }
};
