目录 最小生成树的解题 prim算法 举例说明（来自代码随想录） 题目：53.寻宝 Kruskal算法 举例说明（来自代码随想录） 题目：53.寻宝 最小生成树的解题 最小生成树类型的题目主要用于解决所有节点的最小连通子图的问题，即：以最小的成本（边的权值）将图中所有节点链接到一起。 最小生成树可以使用prim算法，也可以使用kruskal算法计算出来。 prim算法 prim算法的核心有三步： 第一步，选距离生成树最近节点。 第二步，最近节点加入生成树。 第三步，更新非生成树节点到生成树的距离（即更新minDist数组） 其中，minDist数组最为重要，用来...
目录 110.字符串接龙 105.有向图的完全可达性 DFS BFS 106.岛屿的周长 解法一 解法二 110.字符串接龙 题目链接：https://kamacoder.com/problempage.php?pid=1183文章讲解：https://programmercarl.com/kamacoder/0110.字符串接龙.html题目状态：看题解 思路： 输入部分: 读取单词数量(n)。 读取起始单词beginStr和目标单词endStr。 读取并存储单词集合strSet。 辅助数据结构: visitMap:记录每个单词是否被访问过，以及路径长度。...
唉 突然想到为什么一直不记点什么呢。人家基本上每周都会写博客，自己有些方面这么菜，学了忘忘了学，怎么还有理由什么都不记下来呢？也不一定要给自己看啊，也想写干货为社区做点贡献吧！ 刚开始开坑也不知道自己会记些啥，所以先想到什么记什么了，多了之后会分类。 \(2024.08.09\)更新：每个问题的三个参数分别为(提出时间，问题来源，解答来源)。 1.(,abc240G,) 坐标轴上从原点走\(i\)步走到距离原点为\(j\)的点的方案数为？ \([(i\gej)\wedge(2\midij)]\large\binom{i}{\frac{ij}{2}}\) \(i\ltj\)来不及，\(2\nmi...
题目大意 有\(d\)张图，\(n\)个点，\(m\)次操作，每一次操作在第\(k\)张图上在\((u,v)\)之间连一条无向边，求每一次操作后的所有满足在\(d\)张图上全部联通的点对数量。\(d\leq200,n\leq5\times10^3,m\leq10^6\) 思路 对于本题，发现只要一个点对\((u,v)\)在每一个图中都被加入到了同一个集合里即为合法。则直接考虑维护\(d\)个并查集。所以设\(f_{u,i}\)表示\(u\)在第\(i\)个图中所属的集合，则只要所有的\(f_{u,i},i\in[1,d]\)全部相等即可。所以我们维护一个哈希表示\(u\)的所有图的所属集合，之...
目录 108.冗余连接 109.冗余连接II 108.冗余连接 题目链接：https://kamacoder.com/problempage.php?pid=1181文章讲解：https://www.programmercarl.com/kamacoder/0108.冗余连接.html题目状态：看题解 思路： 构建并查集，然后通过并查集来判断节点，若当前这对节点(s,t)在同一个集合中，那么输出这对节点即可达到题目要求，否则，就将s和t合并到同一个集合中。 代码： include<iostream> include<vector> usingname...
目录 红黑树 简述 性质/规则 主要规则: 推导性质: 红黑树的基本实现 structRBTreeNode classRBTree 红黑树的插入 红黑树插入修正前言 什么时候需要变色: 变色的基础: 为什么需要旋转与变色 变色: 旋转 需要修正的所有情况 先认识最简单的情况 1.叔叔是红色结点 注意: 2.没有叔叔结点 3.叔叔是黑色结点 所有结构的基础衍生结构（以左为例） 简单情况衍生 二级修正的情况衍生 总结： 插入修正代码实现 红黑树 简述 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Blac...
目录 并查集模板 107.寻找存在的路径 并查集模板 原理： 并查集主要有两个功能： 将两个元素添加到一个集合中。 判断两个元素在不在同一个集合。 模板代码： intn=1005;//n根据题目中节点数量而定，一般比节点数量大一点就好 vector<int>father=vector<int>(n,0);//C里的一种数组结构 //并查集初始化 voidinit(){ for(inti=0;i<n;i){ father[i]=i; } } //并查集里寻根的过程 intfind(intu){ returnufather[u]?u:father...
A369(abc369A) 题目大意 给定两个数\(a,b\)，问有多少个整数\(x\)，使得\(a,b,x\)经过某种排列后成为等差数列， 解题思路 就三种情况：\(xab\)，\(axb\)，\(abx\)，三种情况都求出来，然后放到set去重即为答案。中间的情况要判断是否是实数。 神奇的代码 include<bits/stdc.h> usingnamespacestd; usingLL=longlong; intmain(void){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); inta,b; cin>...
概述 跳跃表(SkipList)是链表加多级索引组成的数据结构。链表的数据结构的查询复条度是O(N)。为了提高查询效率，可以在链表上加多级索引来实现快速查询。跳跃表不仅能提高搜索性能。也能提高插入和删除操作的性能。索引的层数也叫作跳跃表的高度 查找 在跳跃表的结构中会首先从顶层开始查找，当顶层不存在时向下一层查找，重复此查找过程直到跳跃到原始链表。如图所示，在[1,3,4,10,1,20]的链表中查找10，首先从二级索引中查找，由于1和4都比10小，因此接着在一级索引查找，由于10大于4小于11，因此接着向下查找，原始链表中4的下一个节点10便是需要查找的数据 插入 首先按照查找流程找...
目录 拓扑排序 题目：117.软件构建 dijkstra（朴素版） 题目：47.参加科学大会 dijkstra算法和prim算法的区别 dijkstra（堆优化版） 题目：47.参加科学大会 拓扑排序 拓扑排序概括来说就是给出一个有向无环图，把这个有向无环图转成线性的排序，就叫拓扑排序。 使用广度优先搜索（BFS）即可。 如上图，当我们做拓扑排序的时候，优先找入度为0的节点，只有入度为0，它才是出发节点。 拓扑排序的过程： 找到入度为0的节点，加入结果集。 将该节点从图中移除。 循环以上两步，直到所有节点都在图中被移除了。 结果集的顺序，就是我们想要的拓扑排序...
中英文关键词抽取 欢迎使用中英文关键词抽取工具，本工具支持多种关键词抽取算法，帮助用户从文本中快速提取重要信息。下图展示了我们所支持的关键词抽取算法： 介绍 本工具提供多种关键词抽取算法，满足不同需求。支持的算法如下： TF-IDF：通过词频和逆文档频率来衡量词汇的重要性。 TextRank：基于图算法的无监督关键词抽取方法。 KeyBERT：结合BERT模型的关键词抽取技术，能捕捉语义相关性。 Word2Vec：利用词向量表示来进行关键词提取。 LDA：一种基于主题模型的关键词抽取方法。 使用方法 1、TF-IDF fromkeyword_extractimportKe...
概述 红黑树（Red-BlackTree，R-BTree）是一种自平衡的二叉查找树，在红黑树的每个节点都多出一个存储位表示节点的颜色，颜色只能是红（Red）或者黑（Black）。 红黑树的特性如下： 每个节点或者是黑色的，或者是红色的 根节点是黑色的 每个叶子节点都是黑色的，这里的叶子节点指的是最底层的空节点，即图中值为null的节点，讨论时一般将其省略，值为null的根节点在红黑树中不看作叶子节点 如果一个节点是红色的，则它的子节点必须是黑色的 从任一个节点到叶子节点的所有路径下都包含相同数量的黑色节点 有了上面的几个性质作为限制，即可避免二叉查找树退化成单链表的情况。而有了性质4和性...
数值型数组特征值统计： 简单示例： 求总和与均值： 给定数组arr={4,5,6,1,9}，求其总和、平均值并输出。 求解代码： publicclassTest{ publicstaticvoidmain(String[]args){ int[]arr={4,5,6,1,9}; //求总和、均值 intsum=0;//因为0加上任何数都不影响结果 for(inti=0;i<arr.length;i){ sum+=arr[i];//求总和 } doubleavg=(double)sum/arr.length;//求平均值 System.out.println("sum="+sum);/...
ARaiseBothHands(abc370A) 题目大意 给出Snuke举的左右手情况，如果只举左手，输出Yes，如果只举右手，输出No，否则输出Invalid。 解题思路 逐一判断即可。 神奇的代码 include<bits/stdc.h> usingnamespacestd; usingLL=longlong; intmain(void){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); intl,r; cin>>l>>r; if(l1&&r0) cout<<"...
目录 Floyd算法 题目：97.小明逛公园 A算法 题目：126.骑士的攻击 最短路算法总结 Floyd算法 Floyd算法用于求解多源最短路问题（求多个起点到多个终点的多条最短路径）。在前面学习的dijkstra算法、Bellman算法都是求解单源最短路的问题（即只能有一个起点）。 注意：Floyd算法对边的权值正负没有要求，都可以处理。 Floyd的核心思想是动态规划。 动态规划的五部曲： 确定dp数组（dptable）以及下标的含义。 确定递推公式。 dp数组如何初始化。 确定遍历顺序。 举例推导dp数组。 根据动态规划的五部曲来解释Floyd算法的遍历...
目录 Bellman_ford算法 模拟过程 题目：94.城市间货物运输I Bellman_ford队列优化算法（又名SPFA） 模拟过程 题目：94.城市间货物运输I Bellman_ford算法之判断负权回路 题目：95.城市间货物运输II Bellman_ford算法之单源有限最短路 题目：96.城市间货物运输III Bellman_ford算法 Bellman_ford算法解决的问题和dijkstra朴素版要解决的问题类似，唯一不同的是dijkstra解决的问题中边的权值不能为负数，而Bellman_ford算法要解决的问题是带负权值的单源最短路问题。 ...
JPEG文件除了图像数据之外，还保存了与图片相关的各种信息，这些信息通过不同类型的TAG存储在文件中。 TAG JPEG通过TAG标记压缩书记之外的信息。所有的TAG都包含一个TAG类型，TAG类型大小为两个字节，位于一个TAG的最前面。TAG类型的第一个字节一定为0xFF 以下是部分常见的TAG类型 TAG类型 数值 备注 SOF0SOF3SOF5SOF7SOF8SOF11SOF13SOF15 FFC0FFC3FFC5FFC7FFC8FFCBFFCDFFCF 不同的编码模式对应不同的SOF，详见JPEG标准TableB.1。本文以常见的SOF0为研究对象 DHT FFC4 ...
要求 给定一个二叉树root，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。如下图所示的二叉树最大深度为5. 解题思路 与94题类似，采用递归调用遍历子节点。在基本结构中，节点的最大深度等于根深度（1）加上左右较大深度，左右较大的深度可以一直递归至最小根节点。 实现代码 intmaxDepth(TreeNoderoot){ intdepth=0; if(root) { depth; intdepthLeft=0; intdepthRight=0; if(root->left) depthLeft=maxDepth(root->left); if(...
基本概念 二叉树 二叉树的结构如上图所示，由一系列左-中-右节点组成的树状数据结构，其基本结构如下所示，由一个中间节点向左右分叉成两个节点，故称二叉树。 中序遍历 看二叉树基本的结构左-中-右三个节点，中间为Root，左边为Left，右边为Right。按顺序排列的话有C(3,2)=6种，其中左右，右左算法类似。以中间Root为参考，固定左-右，则排序左-中-右为中序遍历，中-左-右为先序遍历，左-右-中为后序遍历。 解题思路 题目要求中序遍历，即对于所有的节点，都是左-中-右的顺序遍历所有节点，考虑到二叉树结构本身的特殊性，采用指针依次访问，比较难以遍历全局。考虑到整棵树本身可以看作一...
2024秋季PAT认证甲级(题解A-D) 写在前面 这一次PAT甲级应该是最近几次最简单的一次了，3个小时的比赛差不多30分钟就ak了（也是拿下了整场比赛的rk1），下面是题解报告，每个题目差不多都是20-30行代码，难度在洛谷普及组左右（cf1000-1200分） A.A-1HappyPatting 题目描述 The"HappyPatting"gameistoarrangethechildrenintonrows,withmpeopleineachrow.Whenthegamestarts,eachchildwillreceiveadigitalcommandonhis/hermobile...