算法教学课件载

算法教学课件基础到进阶—算法学习的意义为什么学习算法如此重要？算法是解决问题的核心方法算法是计算机科学的核心，也是解决复杂问题的关键工具无论是日常编程还是逻辑思维培养高级系统设计，算法思维都扮演着不可替代的角色掌握算法不仅能提升你的编程能力，还能培养系统化的思考方式和解决问题的策略算法学习锻炼严密的逻辑推理能力，培养结构化思考习惯，提升分析和解决复杂问题的能力在当今数据驱动的时代，算法的重要性日益突出从搜索引擎到社交媒体推荐，从自动驾驶到金融交易系统，算法无处不在深入理解算法原理，将使你能够设计更高效、更可靠的系统，为用户创造更好的体验计算能力提升通过算法训练，你将学会如何优化计算过程，提高程序效率，处理大规模数据面试必备技能技术公司面试中，算法题是检验候选人基本素质的标准手段，掌握算法是求职成功的关键算法与数据结构关系算法与数据结构的共生关系算法与数据结构是计算机科学中紧密相连的两个核心概念如果将算法比作解决问题的方法和步骤，那么数据结构就是存储和组织数据的方式高效的算法往往依赖于选择合适的数据结构，而优秀的数据结构设计则能极大地提升算法性能在算法设计过程中，我们需要考虑如何组织和存储数据？如何高效地访问和修改数据？不同的数据结构在时间和空间效率上各有优势，选择合适的数据结构可以显著提高算法效率例如，使用哈希表可以将查找操作的时间复杂度从On优化到O1；使用平常见数据结构与对应算法衡二叉树可以保证查找、插入和删除操作的时间复杂度为Olog n数据结构是算法的基础，而算法则是数据结构的应用和扩展两者相辅相成，共同构成•数组与线性表排序算法、二分查找了计算机科学的重要基石在学习算法的过程中，我们必须深入理解各种数据结构的特•链表链表反转、环检测性和适用场景，才能设计出既正确又高效的算法•栈与队列表达式求值、广度优先搜索•树与图深度优先搜索、最短路径算法•哈希表快速查找、去重•堆优先队列、堆排序时间复杂度与空间复杂度算法效率的度量标准常见时间复杂度及实例时间复杂度和空间复杂度是衡量算法效率的两个核心指标时间复杂度度量算法执行所需的时间资源，而空间复杂度度量算法执行所需的存储资源在实际应用O1-常数时间中，我们通常使用大O表示法（Big Onotation）来表示算法的渐近复杂度，它描述了算法性能的上界为什么复杂度分析如此重要？哈希表查找、数组随机访问、栈顶操作当数据规模增大时，不同复杂度的算法性能差异会变得异常明显例如，对于包含100万个元素的数组，On²算法可能需要数天才能完成，而On logn算法可能只需几秒钟在处理大规模数据时，选择合适的算法可以节省大量时间和计算资源Olog n-对数时间在算法设计中，我们通常需要在时间复杂度和空间复杂度之间进行权衡有时，我们可以通过牺牲一些空间来换取时间效率的提升，这就是所谓的空间换时间策二分查找、平衡二叉树操作、快速幂算法略；反之，也可以通过增加计算量来减少存储需求，即时间换空间策略On-线性时间数组遍历、线性搜索、计数排序On logn-线性对数时间归并排序、快速排序、堆排序On²-平方时间冒泡排序、插入排序、简单嵌套循环O2ⁿ-指数时间基本排序算法总览快速排序Quick Sort基于分治思想的高效排序算法，平均时间复杂度为On logn•选择基准元素（pivot），将数组分为两部分•递归排序子数组，最终合并结果•随机选择pivot可避免最坏情况•不稳定排序，但在实践中表现优异归并排序Merge Sort稳定的分治排序算法，时间复杂度稳定在On logn•将数组分为两半，递归排序•合并两个有序子数组•稳定排序，适合链表排序•空间复杂度为On，需要额外存储空间基础排序算法简单但效率较低的排序算法，时间复杂度为On²•冒泡排序相邻元素比较交换，大元素冒泡•选择排序每次选择最小元素放到前面•插入排序构建有序序列，未排序元素插入•希尔排序插入排序的改进版，使用间隔序列快速排序算法模板快速排序核心思想快速排序常见优化快速排序是一种高效的比较排序算法，由英国计算机科学家Tony Hoare于1960年提出其核心思想是分治法（Divide andConquer）通过选随机选择基准避免在已排序或部分排序的数组上出现最坏情况择一个基准元素（pivot），将数组分为两部分，使得左部分的所有元素都小于等于基准，右部分的所有元素都大于等于基准，然后递归地对两个三数取中法从首、尾、中间位置选择中间值作为基准子数组进行排序双路快排处理大量重复元素的情况三路快排将数组分为小于、等于、大于三部分，更好处理重复元素//快速排序伪代码function quickSortarr,left,right{if leftright{//分区操作，返回基准元素位置小数组使用插入排序对于小规模数组，插入排序可能更快let pivotIndex=partitionarr,left,right;//递归排序左右子数组quickSortarr,left,pivotIndex-1;quickSortarr,pivotIndex+1,right;}return arr;}function partitionarr,left,尾递归优化减少函数调用栈深度right{//选择基准元素let pivot=arr[right];let i=left-1;for let j=left;jright;j++{if arr[j]=pivot{i++;swaparr,i,j;}}swaparr,i+1,right;return i+1;}应用场景快速排序在实际应用中表现优异，适用于•大规模数据排序•随机访问存储（如数组）•对时间效率要求高且稳定性不重要的场景归并排序与逆序对归并排序核心思想归并排序解决逆序对问题归并排序（Merge Sort）是一种经典的分治算法，其基本思想是将待逆序对是指数组中的两个元素，如果前面的元素大于后面的元素，则排序数组分成两个子数组，递归地对子数组进行排序，然后将已排序这两个元素构成一个逆序对逆序对的数量可以衡量一个数组的有序的子数组合并为一个有序数组归并排序的时间复杂度稳定在On log程度，逆序对越少，数组越接近有序n，是一种稳定的排序算法，适合处理大型数据集和链表结构归并排序过程中，我们可以在合并两个有序子数组时统计逆序对的数归并排序的特点量当左子数组的元素大于右子数组的元素时，就形成了逆序对这是归并排序的一个重要应用•稳定排序相等元素的相对位置保持不变•非原地排序需要额外On的空间•时间复杂度稳定不受输入数据分布影响•适合外部排序处理无法一次性加载到内存的大型数据集二分查找算法二分查找基本原理浮点数二分与高级应用二分查找（Binary Search）是一种高效的查找算法，适用于在有序数组中寻找目标值其核心思想是通过不断将查找区间一分为二，每次比较中间元素与目标值浮点数二分是二分查找的扩展，用于在连续的实数域中寻找满足特定条件的点与整数二分不同，浮点数二分通常需要设定精度阈值作为终止条件的大小，从而缩小查找范围，直到找到目标值或确定目标值不存在//浮点数二分查找模板function binarySearchFloatleft,right,precision{while right-leftprecision{let mid=二分查找的时间复杂度为Olog n，这意味着即使是在包含数十亿元素的数组中，二分查找也能在极少的步骤内完成然而，二分查找要求数组必须有序，且通常left+right/2;if checkmid{right=mid;}else{left=mid;}}需要随机访问能力，因此不适用于链表等顺序访问的数据结构return left+right/2;}整数二分查找模板//查找第一个大于等于target的位置function lowerBoundarr,target{let left=0,right=arr.length;while leftright{let mid=Math.floorleft+right/2;if arr[mid]target{left=mid+1;}else{right=mid;}}return left;}//查找第一个大于target的位置function upperBoundarr,target{letleft=0,right=arr.length;while leftright{let mid=Math.floorleft+right/2;if arr[mid]=target{left=mid+1;}else{right=mid;}}return left;}二分查找的高级应用最优化问题最小化最大值、最大化最小值第K小问题在排序数组中查找第K小的元素旋转排序数组在部分旋转的有序数组中查找近似计算计算平方根、立方根等双指针与滑动窗口1双指针技巧双指针是一种常用的算法技巧，通过使用两个指针遍历数组或链表，以减少时间复杂度双指针主要有以下几种常见形式对撞指针两个指针从数组两端向中间移动，如二分查找、判断回文串快慢指针两个指针以不同速度移动，如检测链表环、寻找链表中点分离双指针两个指针分别在不同数组或链表上移动，如合并两个有序数组双指针技巧的核心优势在于将嵌套循环（On²）优化为单循环（On），显著提高算法效率//双指针判断回文串function isPalindromes{let left=0,right=s.length-1;while leftright{if s[left]!==s[right]{return false;}left++;right--;}return true;}2滑动窗口技巧滑动窗口是双指针的一种特殊形式，特别适用于处理子串或子数组的问题其核心思想是维护一个可变大小的窗口，通过移动窗口的左右边界，在线性时间内解决最优子串或子数组问题滑动窗口算法模板

1.初始化窗口左右边界（left=0,right=0）

2.扩大窗口（right++），直到窗口包含有效解

3.尝试缩小窗口（left++），优化当前解

4.重复步骤2-3，直到right到达数组末尾//滑动窗口模板function slidingWindows{let left=0,right=0;let result=初始值;while rights.length{//扩大窗口添加s[right]到窗口;right++;//窗口满足条件时，尝试缩小while窗口需要缩小{//缩小窗口移除s[left]从窗口;left++;}//更新结果更新result;}return result;}单调栈与单调队列单调栈原理与应用单调队列原理与应用单调栈（Monotonic Stack）是一种特殊的栈结构，其中栈内元素保持单调递增或单调递减的顺序单调栈特别适合解决下一个更大/更小元素类型的问题，通常可以将时间复杂单调队列（Monotonic Queue）是一种特殊的队列结构，其中队列元素保持单调递增或单调递减的顺序单调队列常用于解决滑动窗口中的最大度从On²优化到On值/最小值问题，能够在On时间内完成处理单调栈构建过程典型应用场景

1.遍历数组元素•滑动窗口最大值/最小值

2.与栈顶元素比较，根据单调性要求决定是否弹出栈顶•柱状图中最大矩形面积

3.当前元素入栈•区间覆盖问题

4.栈内元素保持单调性//单调栈模板-求解下一个更大元素function nextGreaterElementnums{const n=nums.length;const result=new Arrayn.fill-1;const stack=[];for leti=0;in;i++{//当前元素大于栈顶元素，弹出栈顶并更新结果while stack.length0nums[i]nums[stack[stack.length-1]]{const idx=stack.pop;result[idx]=nums[i];}//当前索引入栈stack.pushi;}return result;}基础数据结构复习栈Stack队列Queue遵循后进先出（LIFO）原则的线性数据结构遵循先进先出（FIFO）原则的线性数据结构•支持操作push入栈、pop出栈、top栈顶、isEmpty判空•支持操作enqueue入队、dequeue出队、front队首、isEmpty判空•时间复杂度所有操作均为O1•时间复杂度所有操作均为O1•应用函数调用栈、表达式求值、括号匹配、单调栈•应用广度优先搜索、任务调度、缓冲区管理优先队列Priority Queue堆Heap元素按优先级而非到达顺序出队的队列特殊的完全二叉树，用于高效维护最大值或最小值•通常使用堆实现•最大堆父节点值大于等于子节点值•支持操作插入、取出最高优先级元素•最小堆父节点值小于等于子节点值•时间复杂度插入Olog n、取最值O1•支持操作insert插入、extractMax/Min取出最值、heapify构建堆•应用Dijkstra算法、事件驱动模拟、合并K个有序链表•时间复杂度插入Olog n、取最值O

1、构建On//堆的基本操作伪码class Heap{constructorcomparator{this.heap=[];this.comparator=comparator||a,b=a-b;//默认最小堆}size{return this.heap.length;}isEmpty{returnthis.size===0;}peek{return this.heap

[0];}pushvalue{this.heap.pushvalue;this.siftUpthis.size-1;}pop{const result=this.peek;const last=this.heap.pop;if this.size0{this.heap

[0]=last;this.siftDown0;}return result;}//上浮操作siftUpindex{//实现细节省略}//下沉操作siftDownindex{//实现细节省略}}链表与二叉树基础链表基础与操作二叉树基础与遍历链表是一种线性数据结构，其中的元素不是存储在连续的内存位置，而是通过指针二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点连接链表主要分为单链表和双链表两种类型和右子节点单链表class TreeNode{constructorval{this.val=val;每个节点包含数据和指向下一个节点的指针this.left=null;this.right=null;}}class ListNode{constructorval{this.val=val;this.next=null;}}二叉树的基本概念•深度从根节点到该节点的路径长度双链表•高度从该节点到最远叶节点的路径长度每个节点包含数据和指向前后节点的两个指针•满二叉树除叶节点外，所有节点都有两个子节点•完全二叉树除最后一层外，每层都是满的，最后一层从左到右填充class DoublyListNode{constructorval{this.val=•平衡二叉树任意节点的左右子树高度差不超过1val;this.prev=null;this.next=null;}}二叉树的遍历方式•前序遍历（根-左-右）适用于复制树、表达式解析•中序遍历（左-根-右）对于二叉搜索树，得到有序序列•后序遍历（左-右-根）适用于删除树、计算目录大小•层序遍历按层从上到下，从左到右遍历常用链表操作二叉树的高级应用•插入节点O1时间复杂度（已知位置）•树的直径任意两节点间的最长路径•删除节点O1时间复杂度（已知位置）•最近公共祖先（LCA）两个节点的最近共同祖先•查找节点On时间复杂度•反转链表常见面试题•检测环使用快慢指针•找中点使用快慢指针搜索算法与DFS BFS深度优先搜索DFS广度优先搜索BFS深度优先搜索是一种优先探索深度的搜索策略，它尽可能深地搜索树或图的分支，直到达到叶节点，然后回溯到前一个节点，继续搜索其他分支广度优先搜索是一种优先探索广度的搜索策略，它逐层遍历，先访问离起始节点最近的节点，然后再访问下一层节点DFS实现方式BFS实现方式递归实现利用系统栈，代码简洁直观队列实现使用队列维护待访问节点显式栈实现手动维护栈，避免系统栈溢出双端队列优化某些特殊情况下的优化DFS适用场景BFS适用场景•查找所有可能的解（如排列组合问题）•最短路径问题•拓扑排序•层序遍历•检测环•连通性检测•连通分量分析•无权图的最短路径//DFS递归实现function dfsnode,visited=new Set{if!node||visited.hasnode return;//访问当前节点console.lognode.val;visited.addnode;//递归访问相邻节点for const neighbor ofnode.neighbors{dfsneighbor,visited;}}//DFS栈实现function dfsWithStackstartNode{const visited=new Set;conststack=[startNode];while stack.length0{const node=stack.pop;if visited.hasnodecontinue;//访问当前节点console.lognode.val;visited.addnode;//将相邻节点入栈for const neighbor ofnode.neighbors{if!visited.hasneighbor{stack.pushneighbor;}}}}图论算法基础图的表示方法图的基本算法图是一种非线性数据结构，由顶点（节点）和边组成根据边的方向性，图可分为有向图和无向图的遍历图；根据边的权重，可分为有权图和无权图图的表示方法主要有深度优先搜索DFS使用栈或递归实现，适合查找路径、判断连通性邻接矩阵广度优先搜索BFS使用队列实现，适合求解最短路径使用二维数组表示图中顶点之间的连接关系对于有n个顶点的图，邻接矩阵是一个n×n的矩阵拓扑排序对有向无环图DAG的所有顶点进行排序，使得对于任意的边u,v，顶点u在排序中都出现在顶优点查询两点间是否有边的时间复杂度为O1点v之前缺点空间复杂度为On²，对于稀疏图很浪费空间•应用任务调度、课程安排、依赖分析邻接表连通分量使用数组+链表表示图，数组的每个元素对应一个顶点，链表中存储与该顶点相邻的所有顶点强连通分量SCC有向图中互相可达的顶点集合弱连通分量WCC将有向图视为无向图时的连通分量优点空间效率高，特别适合稀疏图双连通分量BCC无向图中去除任意一个顶点后仍连通的最大子图缺点查询两点间是否有边的时间复杂度为O度边集数组直接存储图中所有的边，每条边用一个结构体表示，包含起点、终点和权重优点适合对边进行操作的算法，如Kruskal算法缺点不便于查找顶点的相邻点最短路径算法Dijkstra算法Bellman-Ford算法Floyd-Warshall算法解决单源最短路径问题的贪心算法，适用于所有边权重为非负的图解决单源最短路径问题的动态规划算法，可处理负权边，还能检测负权环解决所有顶点对之间最短路径的动态规划算法，可处理负权边但不能有负权环算法步骤算法步骤算法步骤

1.初始化起点距离为0，其他顶点距离为无穷大

1.初始化起点距离为0，其他顶点距离为无穷大

1.初始化直接相连的顶点距离为边权重，不相连的距离为无穷大

2.选择每次选择未访问的距离最小的顶点

2.对所有边进行V-1次松弛操作

2.对于每个顶点k，更新所有顶点对i,j的距离

3.松弛更新所有与当前顶点相邻的顶点的距离

3.检查是否存在负权环再进行一次松弛，如有更新则存在负权环

3.如果通过k的路径更短，则更新距离

4.重复2-3步骤，直到所有顶点都被访问时间复杂度时间复杂度时间复杂度•OV·E•OV³•基础实现OV²•优先队列优化OE logV•斐波那契堆优化OE+V logV//Dijkstra算法伪码（优先队列优化）function dijkstragraph,start{const n=graph.length;const dist=newArrayn.fillInfinity;dist[start]=0;//优先队列，按距离排序const pq=new PriorityQueuea,b=a.dist-b.dist;pq.push{node:start,dist:0};while!pq.isEmpty{const{node,dist:d}=pq.pop;//如果队列中的距离大于已知距离，跳过if ddist[node]continue;//遍历所有相邻节点for const[neighbor,weight]of graph[node]{//松弛操作if dist[node]+weightdist[neighbor]{dist[neighbor]=dist[node]+weight;pq.push{node:neighbor,dist:dist[neighbor]};}}}return dist;}最小生成树算法最小生成树概念Prim算法最小生成树（Minimum SpanningTree，MST）是一个连通无向图的生成树，其权重之和最小对于有n个顶点的连通图，MST包含n-1条边，连接所有顶点且Prim算法也是一种贪心算法，从任意顶点开始，逐步扩展最小生成树，每次选择连接树与非树顶点的最小权重边无环最小生成树在网络设计、电路布线、集群分析等领域有广泛应用算法步骤Kruskal算法

1.选择任意顶点作为起点，加入最小生成树Kruskal算法是一种贪心算法，基于边的权重对所有边进行排序，然后逐一添加不形成环的最小权重边，直到所有顶点都被连接

2.考察所有连接树中顶点与非树顶点的边，选择权重最小的边及其连接的非树顶点加入树中算法步骤

3.重复步骤2，直到所有顶点都加入树中或无法继续扩展时间复杂度

1.将图中所有边按权重升序排序

2.初始化每个顶点为独立的连通分量•基础实现OV²

3.依次考察每条边如果边的两个顶点不在同一连通分量中，则将该边加入最小生成树，并合并两个连通分量•优先队列优化OE logV

4.重复步骤3，直到选择了n-1条边或考察完所有边两种算法的比较时间复杂度•Kruskal算法更适合稀疏图（边较少）•OE logE，主要来自边的排序•Prim算法更适合稠密图（边较多）•使用并查集实现连通分量的合并与查询，操作接近O1•Kruskal算法易于并行实现•Prim算法在部分生成树时就可得到结果字符串算法基础KMP算法字符串哈希Knuth-Morris-Pratt（KMP）算法是一种高效的字符串匹配算法，用于在主文本串中查找模式串传统的暴力匹配在最坏情况下时间复杂度为Om*n，而KMP字符串哈希是将字符串映射为整数的技术，常用于快速比较字符串或子串通过合适的哈希函数，可以在O1时间内判断两个字符串是否相等（存在哈希冲突的小算法通过利用已经匹配的信息，避免不必要的比较，将时间复杂度优化到Om+n概率），大大提高字符串处理的效率算法核心部分匹配表常用哈希函数KMP算法的关键在于构建模式串的部分匹配表（next数组），该表记录了模式串中每个前缀的最长相等前后缀长度利用这个表，算法可以在匹配失败时，知道多项式哈希（Polynomial Hash）是最常用的字符串哈希方法将字符串视为基数为p（通常是质数）的多项式，对一个大质数取模下一步应该从模式串的哪个位置开始比较，而不必回溯主文本串的指针hashs=s

[0]*p^n-1+s

[1]*p^n-2+...+s[n-1]%mod//构建next数组function buildNextpattern{const m=pattern.length;const next=new Arraym.fill0;let j=0;for leti=1;im;i++{while j0pattern[i]!==pattern[j]{j=next[j-1];}if pattern[i]===pattern[j]{j++;}next[i]=j;}return next;}//KMP匹配其中p通常取131或13331，mod通常取一个大质数如10^9+7function kmptext,pattern{if pattern.length===0return0;const next=buildNextpattern;const n=前缀哈希text.length;const m=pattern.length;letj=0;for leti=0;in;i++{while j0text[i]!==pattern[j]{j=next[j-1];}if text[i]===pattern[j]通过预计算字符串的所有前缀哈希值，可以在O1时间内计算任意子串的哈希值，用于快速子串比较{j++;}if j===m{return i-m+1;//找到匹配，返回起始索引}}return-1;//未找到匹配}应用场景子串查找在长文本中查找特定模式回文串检测判断字符串是否为回文最长公共子串寻找两个字符串的最长公共部分字符串匹配包括精确匹配和模糊匹配动态规划方法论DP建立状态转移方程问题分析与定义状态状态转移方程描述了当前状态与之前状态的关系，是动态规划的核心一个好的状态转移方程应该清晰地表达如何从已知状态得到新状态的最优解动态规划的第一步是分析问题，找出子问题结构，并明确定义状态状态通常表示为DP[i]或DP[i][j]，代表问题规模缩小到i或i,j时的最优解状态的定义是DP常见的状态转移模式的核心，好的状态定义能使问题变得简单明了•线性DP[i]=max/minDP[i-1],DP[i-2],...•状态必须能够完整描述子问题•双序列DP[i][j]=fDP[i-1][j],DP[i][j-1],DP[i-1][j-1]•状态应尽量简洁，避免冗余信息•区间DP[i][j]=fDP[i+1][j],DP[i][j-1],DP[i+1][j-1],...•状态数量应尽可能少，减少时空复杂度优化空间与时间复杂度确定边界条件与计算顺序在基本算法正确的基础上，可以考虑优化空间和时间复杂度动态规划常用的优化技巧包括状态压缩、滚动数组、单调队列/栈等边界条件是动态规划的起点，必须正确设置才能保证算法的正确性计算顺序需要确保在计算当前状态时，所依赖的所有状态都已经计算出来•滚动数组当前状态只依赖于前几个状态时，可以重用数组空间•边界条件通常是问题规模最小时的情况•状态压缩使用位运算表示状态集合，减少空间使用•计算顺序可以是自底向上（迭代）或自顶向下（递归+记忆化）•预处理通过预处理信息加速状态转移计算•多维DP可能需要考虑复杂的遍历顺序•数据结构优化使用特殊数据结构维护状态信息DP问题分类根据问题特点，动态规划可以分为多种类型，掌握这些类型有助于快速识别问题并设计解决方案线性DP如最长递增子序列、最大子数组和背包问题01背包、完全背包、多重背包等区间DP如最长回文子串、戳气球树形DP在树结构上进行动态规划状态压缩DP使用位运算表示状态数位DP按数位进行动态规划概率DP处理概率相关的问题博弈DP分析博弈问题的最优策略DP的适用条件并非所有问题都适合用动态规划解决一个问题适合使用动态规划的充分条件是最优子结构问题的最优解包含子问题的最优解重叠子问题求解过程中会反复计算相同的子问题无后效性当前状态只与之前的状态有关，不影响之前的状态经典背包问题01背包问题完全背包问题多重背包问题有N件物品和一个容量为V的背包，每件物品只能使用一次，第i件物品的体积为v[i]，价值为w[i]，求解将与01背包相似，但每件物品可以使用无限次与01背包相似，但第i件物品最多可以使用s[i]次哪些物品装入背包可使价值总和最大状态定义朴素解法状态定义dp[i][j]表示前i件物品放入容量为j的背包的最大价值可以将s[i]件相同物品看作s[i]件不同物品，转化为01背包问题dp[i][j]表示前i件物品放入容量为j的背包的最大价值状态转移方程二进制优化状态转移方程dp[i][j]=maxdp[i-1][j],dp[i][j-v[i]]+w[i]将s[i]件物品拆分为若干二进制组物品，如拆分为1,2,4,8,...个物品，这样可以用更少的物品表示任意数dp[i][j]=maxdp[i-1][j],dp[i-1][j-v[i]]+w[i]一维优化量一维优化单调队列优化dp[j]=maxdp[j],dp[j-v[i]]+w[i]dp[j]=maxdp[j],dp[j-v[i]]+w[i]利用单调队列优化状态转移，进一步降低时间复杂度注意必须正序遍历j，允许物品被多次使用注意必须逆序遍历j，保证每个物品只被使用一次//01背包二维实现function knapsack01_2dweights,values,capacity{const n=weights.length;const dp=Arrayn+

1.fill.map=Arraycapacity+

1.fill0;for leti=1;i=n;i++{for letj=0;j=capacity;j++{if j=weights[i-1]{dp[i][j]=Math.maxdp[i-1][j],dp[i-1][j-weights[i-1]]+values[i-1];}else{dp[i][j]=dp[i-1][j];}}}return dp[n][capacity];}//01背包一维优化function knapsack01_1dweights,values,capacity{constn=weights.length;const dp=Arraycapacity+

1.fill0;for leti=0;in;i++{for letj=capacity;j=weights[i];j--{dp[j]=Math.maxdp[j],dp[j-weights[i]]+values[i];}}return dp[capacity];}区间与状态机DP DP区间动态规划状态机动态规划区间DP是动态规划的一种特殊形式，它处理的问题通常具有以下特点将原问题划分为若干个连续区间子问题，通过合并这些子问题的解得到原问题的解区间状态机DP是将问题抽象为有限状态机模型的动态规划方法在这类问题中，系统在任意时刻都处于有限个状态之一，且状态之间存在转移关系状态机DP的核心DP的状态通常定义为dp[i][j]，表示区间[i,j]上的最优解是确定状态集合和状态转移规则区间DP的一般步骤状态机DP的一般步骤

1.定义状态dp[i][j]表示区间[i,j]的最优解

1.确定状态集合分析问题中可能的状态

2.确定状态转移方程通常考虑如何将大区间分解为小区间

2.定义状态通常是多维数组，如dp[i][state]

3.确定遍历顺序先计算小区间，再计算大区间

3.确定状态转移方程描述状态之间的转移关系区间DP的典型问题

4.初始化与边界条件确定初始状态的值状态机DP的典型问题最长回文子序列dp[i][j]表示s[i...j]中的最长回文子序列长度矩阵链乘法dp[i][j]表示矩阵链A[i...j]的最小乘法次数股票买卖问题不同的交易限制下的最大利润戳气球dp[i][j]表示戳破i,j区间内所有气球能获得的最大硬币数打家劫舍不能抢劫相邻房屋的最大金额石子合并dp[i][j]表示将区间[i,j]的石子合并成一堆的最小代价最大子数组和可以用状态机DP解决正则表达式匹配字符串与模式的匹配问题//石子合并问题function stoneMergestones{constn=stones.length;const sum=new Arrayn+

1.fill0;for leti=1;i=n;i++{sum[i]=sum[i-1]+stones[i-1];}const dp=Arrayn.fill.map=Arrayn.fillInfinity;for leti=0;in;i++{dp[i][i]=0;//单个石子不需合并}//区间长度for letlen=2;len=n;len++{//区间起点for leti=0;i=n-len;i++{//区间终点const j=i+len-1;//枚举分割点for letk=i;kj;k++{dp[i][j]=Math.mindp[i][j],dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i];}}}return dp

[0][n-1];}数学算法基础欧几里得算法与扩展GCD组合数与快速幂模运算技巧与应用欧几里得算法（辗转相除法）是计算两个整数最大公约数（GCD）的经典算法其核心思想是组合数Cn,k表示从n个元素中选择k个元素的方案数计算组合数常用公式Cn,k=n!/k!*n-模运算在处理大数计算、避免溢出等方面有重要应用模运算满足以下性质gcda,b=gcdb,a modb k!•a+b%m=a%m+b%m%m•a-b%m=a%m-b%m+m%m//最大公约数function gcda,b{return b===0a:gcdb,a%b;}//扩展//快速幂算法function fastPowbase,exponent,mod{let result=1;欧几里得算法function extGcda,b{if b===0{return[a,1,while exponent0{if exponent1{result=result*•a*b%m=a%m*b%m%m0];}const[d,x1,y1]=extGcdb,a%b;const x=y1;const base%mod;}base=base*base%mod;•a/b%m=a*b^m-2%m（当m为质数时）y=x1-Math.floora/b*y1;return[d,x,y];}exponent=1;}return result;}//组合数计算（使用逆元）function模运算在密码学、哈希函数、随机数生成等领域有广泛应用combinationn,k,mod{if kn return0;//计算阶乘及其逆元const fac=new Arrayn+1;const inv=new Arrayn+1;fac

[0]=inv

[0]=1;for leti=1;i=n;i++{fac[i]=fac[i-1]*i%mod;inv[i]=fastPowfac[i],mod-2,mod;//费马小定理求逆元}return fac[n]*inv[k]%mod*inv[n-k]%mod%mod;}扩展欧几里得算法可以求解ax+by=gcda,b的整数解，进而解决线性丢番图方程和模逆元问题素数与筛法素数是大于1的自然数中，只能被1和自身整除的数筛法是高效生成素数表的方法，主要有埃氏筛和线性筛两种位运算与数位DP位运算基础位运算在算法中的应用位运算是直接对二进制位进行操作的计算，它通常比普通算术运算更高效在算法中，位运算可以用于状态表示、优化计算等多种场景集合表示用一个整数的二进制位表示元素是否在集合中基本位运算操作状态压缩在动态规划中使用位运算表示状态快速乘除法使用移位运算代替乘除法与运算两位同为1时结果为1，否则为0位图使用位运算进行空间优化或运算|两位有一个为1时结果为1，否则为0异或特性应用解决只出现一次的数等问题异或运算^两位不同时结果为1，相同为0数位DP取反运算~0变1，1变0左移运算所有位向左移动，右侧补0数位DP是一种特殊的动态规划方法，用于解决与数字的位数相关的计数问题典型的数位DP问题包括右移运算所有位向右移动，左侧补符号位•计算满足特定条件的数字个数无符号右移所有位向右移动，左侧补0•数字游戏中的胜负判定常用位运算技巧•特定范围内数字的统计问题数位DP的一般步骤//判断奇偶性function isOddn{return n1===1;}//获取第i位（从0开始）function getBitn,i{return ni1;}//设置第i位为1function setBitn,i{return n|1i;}//清除第i位（设为0）function clearBitn,i{return n

1.将数字按位分解~1i;}//将第i位取反function flipBitn,i{return n^1i;}//统计二进制中1的个数function countOnesn{let

2.设计状态表示，通常包含位置、约束、已有特征等信息count=0;while n0{n=n-1;//清除最低位的1count++;}return count;}

3.设计状态转移方程

4.利用记忆化搜索优化贪心算法思想贪心算法核心思想反悔贪心贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法策略贪心算法在解决最优化问题时，通反悔贪心是贪心算法的一种扩展，它允许在某些情况下反悔之前的贪心选择，通过局部调整获得更优解反悔贪心通常用于解决一些标准贪心算法无常比动态规划更简单、更高效，但前提是问题满足贪心选择性质法解决的问题贪心算法的关键要素反悔贪心的基本思路贪心选择性质局部最优选择能导致全局最优解

1.先按照某种贪心策略做出选择最优子结构问题的最优解包含子问题的最优解

2.记录每次选择可能的反悔成本贪心算法的设计通常需要证明贪心策略的正确性，这往往是算法设计中最具挑战性的部分

3.当新的选择与之前的选择冲突时，考虑是否反悔之前的某个选择

4.通常使用优先队列维护反悔成本，便于决策典型贪心策略归纳贪心构造按权重排序如区间调度问题按结束时间排序贪心构造是一种特殊的贪心算法应用，它通过贪心策略直接构造出问题的解，而不是从一组候选解中选择这种方法常用于构造型问题，如生成特定性优先队列维护如Huffman编码、最小生成树质的数组、字符串等双重标准排序如活动选择问题差值最大化如最大利润问题比率排序如分数背包问题按价值/重量排序经典贪心问题及策略问题贪心策略活动选择按结束时间排序，优先选择结束早的活动Huffman编码优先合并频率最低的两个节点分数背包按价值/重量比排序，优先选择比值高的物品最小生成树Kruskal选择不形成环的最小权重边Dijkstra算法每次选择距离最小的未访问顶点贪心算法的证明技巧归纳法证明每一步贪心选择都不会导致次优解交换论证证明任何非贪心解都可以通过交换变成贪心解而不变差反证法假设存在比贪心解更优的解，然后推导出矛盾数学归纳法按问题规模逐步证明贪心策略的正确性常用高级数据结构并查集1树状数组2线段树3平衡树4跳表稀疏表5并查集Union-Find树状数组Binary IndexedTree并查集是一种树形数据结构，用于处理一系列不相交集合的合并及查询问题主要支持两种操作查找（Find）和合并（Union）树状数组，也称为Fenwick树，是一种支持单点修改和区间查询的数据结构，特别适合处理前缀和相关的问题核心操作核心操作Find确定元素属于哪个集合，通常返回集合的代表元素Update单点修改，时间复杂度Olog nUnion将两个集合合并为一个集合Query查询前缀和，时间复杂度Olog n优化技巧//树状数组实现class BIT{constructorn{this.n=n;this.tree=new Arrayn+

1.fill0;}//返路径压缩在Find操作中，将查找路径上的所有节点直接连接到根节点回x的最低位1lowbitx{return x-x;}//单点修改位置i增加delta updatei,delta{while i按秩合并总是将较小的树连接到较大的树上=this.n{this.tree[i]+=delta;i+=this.lowbiti;}}//查询前缀和[1,i]queryi{let sum=0;while i0{sum+=this.tree[i];i-=this.lowbiti;}return sum;}//查询区间和[l,r]queryRangel,r{return this.queryr-this.queryl-1;}}//并查集实现class UnionFind{constructorn{this.parent=Array.from{length:n},_,i=i;this.rank=new Arrayn.fill0;}//查找元素所在集合的代表元素findx{if this.parent[x]!==x{this.parent[x]=this.findthis.parent[x];//路径压缩}return this.parent[x];}//合并两个集合unionx,y{const rootX=this.findx;const rootY=this.findy;if rootX===rootY returnfalse;//按秩合并if this.rank[rootX]this.rank[rootY]{this.parent[rootX]=rootY;}else ifthis.rank[rootX]this.rank[rootY]{this.parent[rootY]=rootX;}else{this.parent[rootY]=rootX;this.rank[rootX]++;}return true;}//判断两个元素是否属于同一集合isConnectedx,y{return this.findx===this.findy;}}映射与字典树Trie哈希映射HashMap字典树Trie哈希映射是一种键值对集合，它使用哈希函数将键映射到桶或槽位，以便快速查找哈希映射在各种算法问题中广泛应用，特别是需要快速查找、插入和删除操作的场景字典树，也称为前缀树或Trie树，是一种树形数据结构，用于高效地存储和检索字符串数据集中的键相比于哈希表，Trie树的优势在于可以按字典序查找和处理字符串前缀哈希映射的特点字典树的特点平均时间复杂度查找、插入、删除均为O1最坏时间复杂度On，当发生严重哈希冲突时查找复杂度Om，m为字符串长度空间复杂度On空间复杂度OALPHABET_SIZE*m*n，n为字符串数量支持前缀查询可以快速找到具有特定前缀的所有字符串常见应用场景典型应用场景计数问题统计元素出现次数查找问题如两数之和、三数之和前缀匹配如自动补全、拼写检查去重问题快速判断元素是否已存在字符串集合操作快速判断字符串是否在集合中最长公共前缀查找字符串集合的最长公共前缀缓存实现如LRU缓存索引构建建立值到索引的映射字典序问题按字典序处理字符串//使用哈希映射解决两数之和问题function twoSumnums,target{const map=new Map;for leti=0;inums.length;i++{const complement=target-nums[i];if map.hascomplement{return[map.getcomplement,i];}map.setnums[i],i;}return[-1,-1];}算法竞赛题型分析数据结构题型动态规划题型搜索与枚举题型考察对基础和高级数据结构的理解与应用能力考察对子问题划分和状态转移方程设计的能力考察对搜索策略和剪枝技巧的掌握程度栈与队列表达式求值、单调栈、单调队列线性DP最长递增子序列、编辑距离深度优先搜索排列组合、回溯法堆与优先队列第K大元素、合并K个有序链表区间DP石子合并、戳气球广度优先搜索最短路、最小步数树与图树的遍历、最短路径、最小生成树背包DP01背包、完全背包、多重背包双向搜索从起点和终点同时搜索高级数据结构线段树、树状数组、并查集、Trie树状态压缩DP旅行商问题、集合划分启发式搜索A*算法、IDA*算法树形DP树的直径、树的最大独立集剪枝技巧可行性剪枝、最优性剪枝、记忆化数学与数论题型字符串题型贪心与构造题型考察对数学知识和算法的应用能力考察对字符串算法和数据结构的理解考察对问题本质的理解和解决方案的构造能力基础数论最大公约数、素数筛法字符串匹配KMP算法、Rabin-Karp算法经典贪心区间调度、Huffman编码组合数学排列组合、容斥原理字典树前缀统计、单词查找反悔贪心反悔策略优化概率与期望随机算法、概率DP后缀数组/树最长公共子串、重复字符串构造算法特定性质的序列构造博弈论Nim游戏、SG函数字符串哈希快速子串判断证明技巧交换论证、反证法线性代数矩阵运算、高斯消元回文串Manacher算法、回文子串双指针与滑动窗口二分查找、尺取法常见题型解题策略推荐题单审题分析仔细理解问题要求和约束条件LeetCode经典题目寻找类似尝试将问题归类到已知的典型问题•数组与排序1,15,56,215数据规模推算法根据数据规模推测可能的算法复杂度•链表21,23,142,206特例思考考虑简单情况，寻找规律•树与图94,104,236,207模型建立将实际问题抽象为数学或计算机模型•动态规划5,53,72,300算法选择根据问题特点选择适合的算法•贪心算法55,253,406,621优化实现考虑边界情况，优化时间和空间复杂度Codeforces热门算法题•Div2A/B基础语法与简单算法•Div2C/D中等难度，常见算法应用•Div2E/F高难度，需要深入的算法设计能力刷题与能力提升方法论刷题顺序与策略高效学习方法有效的刷题策略能够事半功倍，避免陷入盲目刷题的误区以下是推荐的刷题顺序和方法1深入理解而非记忆按难度递进不要仅仅记忆解法，而是要理解算法的本质和适用条件对于每个算法，思考为什么这样做？什么情况下适用？有哪些限制条件？入门阶段从简单题目开始，掌握基本数据结构和算法进阶阶段尝试中等难度题目，深入理解算法思想2实现和优化提高阶段挑战困难题目，锻炼解决复杂问题的能力专家阶段研究竞赛级题目，掌握高级算法和优化技巧亲自动手实现算法，不要仅看别人的代码尝试多种实现方式，比较时间和空间复杂度，思考如何优化按专题学习总结与反思专题学习比盲目刷题更有效，可以按以下顺序学习各类算法定期复习和总结，建立自己的知识体系对于解不出的题目，不要立即看答案，先尝试自己思考，然后参考提示，最后再看解法基础算法排序、二分查找、双指针数据结构数组、链表、栈、队列、哈希表、树搜索算法DFS、BFS、回溯法重复练习动态规划线性DP、区间DP、背包问题图论算法最短路径、最小生成树、拓扑排序高级数据结构并查集、树状数组、线段树数学算法数论、组合数学、概率字符串算法KMP、Trie树、后缀数组算法项目与实践案例算法在工程实践中的应用其他算法应用场景算法不仅是理论学习和面试题目，更是解决实际工程问题的重要工具在实际工作中，算法应用广泛，从日常开发到大型系统架构都离不开算法的支持以下是几个算法在工程实搜索引擎践中的典型应用场景倒排索引快速定位包含关键词的文档推荐系统PageRank基于图论的网页重要性排序算法推荐系统是互联网产品的核心功能之一，通过算法为用户提供个性化内容推荐相关性计算TF-IDF、BM25等算法衡量查询与文档的相关性拼写纠错编辑距离算法帮助纠正用户输入错误协同过滤基于用户或物品的相似性进行推荐数据压缩矩阵分解使用隐因子模型降维，捕捉用户和物品的潜在特征深度学习使用神经网络模型学习复杂的用户-物品交互模式Huffman编码根据字符频率优化编码长度实时推荐结合用户行为序列和上下文信息，使用强化学习等技术优化推荐策略LZ77/LZ78基于滑动窗口的无损压缩算法路径规划图像压缩DCT变换、小波变换等在JPEG等格式中的应用金融科技在导航系统、物流配送、机器人路径规划等场景中，路径算法起着关键作用Dijkstra算法单源最短路径问题，如导航系统中的最短路径查找风控模型使用决策树、随机森林等算法评估风险A*算法启发式搜索，在游戏AI和机器人路径规划中广泛应用高频交易毫秒级的算法决策系统旅行商问题物流配送中的路线优化，通常使用近似算法投资组合优化基于图论和运筹学的资产配置算法车辆路径问题多车辆、多约束的复杂路径规划，结合运筹学方法解决实践案例电商平台商品推荐系统某电商平台构建商品推荐系统的实践过程参考资料与模板库推荐推荐书籍代码模板库高质量的代码模板库可以大大提高算法实现效率，以下是一些推荐的开源模板库入门教材codeforces-go Go语言实现的算法模板库，包含常见数据结构和算法《算法图解》-Aditya Bhargava著，图解算法基础概念，适合零基础入门KACTL KTHRoyal Instituteof Technology的竞赛模板库《啊哈算法》-啊哈磊著，通俗易懂的算法入门书，侧重趣味性ACL AtCoderLibrary，日本AtCoder平台官方C++模板库《大话数据结构》-程杰著，以对话形式讲解数据结构，适合初学者OI-Wiki模板中文算法竞赛社区整理的代码模板《算法笔记》-胡凡、曾磊著，适合ACM/ICPC入门算法竞赛模板库包含各种常用算法的实现，适合ACM/ICPC备赛学习社区与交流平台进阶教材《算法导论》-Cormen等著，算法领域的经典教材，内容全面且深入《算法（第4版）》-Sedgewick著，配有Java实现，示例丰富《挑战程序设计竞赛》-秋叶拓哉等著，竞赛向算法教材《算法竞赛入门经典》-刘汝佳著，ACM/ICPC经典备考书籍专题深入《编程珠玑》-Jon Bentley著，经典算法思想案例分析《算法设计与分析基础》-Anany Levitin著，系统介绍算法设计技巧《算法竞赛进阶指南》-李煜东著，竞赛选手进阶必读《程序员代码面试指南》-左程云著，面试算法题详解优质在线资源灵茶山艾府优质算法博主，提供系统化学习资料OI Wiki开源的算法与竞赛编程知识库LeetCode-cn提供中文题解和讨论的刷题平台Codeforces全球最活跃的算法竞赛平台洛谷国内知名的算法学习和竞赛平台牛客网提供大量面试题和竞赛题力扣（LeetCode）讨论区各题解法讨论和分享知乎算法专栏众多算法专家分享经验和见解CSDN/博客园丰富的算法博客和教程GitHub大量开源的算法项目和学习资料算法竞赛Discord/QQ群实时交流和讨论视频课程MIT OpenCourseWare麻省理工的算法课程课程总结与学习建议算法学习是一个循序渐进的过程理论联系实际，模板活用坚持刷题与知识迁移从基础数据结构开始，逐步学习搜索、动态规划、图论等高级算法不理解算法的核心思想比记忆代码更重要掌握模板后，要学会灵活运用坚持每天刷题，培养算法思维注重题目之间的联系，学会举一反三要急于求成，打好基础比速成更重要算法能力的提升需要时间和大量和调整，而不是生搬硬套尝试将学到的算法应用到实际项目中，加深解题后反思总结，归纳相似问题的共性，建立自己的知识体系练习，保持耐心和恒心理解和记忆学习计划建议

1.基础阶段（1-2个月）•掌握基本数据结构数组、链表、栈、队列、哈希表、树•学习基础算法排序、二分查找、双指针•刷简单难度题目，建立信心

2.进阶阶段（2-3个月）鼓励参与竞赛与开源社区•深入学习图论算法BFS、DFS、最短路径、最小生成树参与算法竞赛和开源社区是提升算法能力的有效途径•学习动态规划基础线性DP、背包问题•掌握贪心算法的常见应用定期参加在线竞赛如LeetCode周赛、Codeforces比赛、牛客比赛等•刷中等难度题目，挑战自己尝试ACM/ICPC大学生程序设计竞赛，团队协作解决复杂问题

3.提高阶段（3-6个月）贡献开源项目为算法库、题解仓库等项目贡献代码•学习高级数据结构并查集、树状数组、线段树、Trie树分享和交流写博客、录制视频分享自己的学习心得•深入研究复杂动态规划区间DP、状态压缩DP、树形DP导师指导寻找算法导师或加入学习小组，互相促进•学习数学算法数论、组合数学、概率算法最后的寄语•挑战困难题目，参加在线竞赛

4.专家阶段（持续学习）算法学习是一段充满挑战但也充满乐趣的旅程它不仅能提升编程能力，还能培养解决复杂问题的思维方式保持好奇心和学习热情，享受算法带来的思维乐趣无论是为了面试、竞赛，还是提升自身能力，扎实的算法功底•研究竞赛级算法网络流、计算几何、字符串算法都将是你职业生涯中的宝贵财富•参与开源项目，贡献代码愿你在算法的世界中探索前行，不断突破自我！•尝试教授他人，巩固自己的知识•关注前沿算法研究，不断学习新知识。