- 博客(115)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 树（七）——哈夫曼树和哈夫曼编码
定义从树的根节点到任意节点的路径长度与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为WPL=∑i=1nwiliWPL=\sum^n_{i=1}w_il_iWPL=i=1∑nwiliWPL最小的二叉树称为哈夫曼树，也称最优二叉树构造给定n个权值分别为w1,w2,...,wnw_1, w_2,..., w_nw1,w2,...,wn的结点，构造哈夫曼树的算法描述如下:将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
2021-09-19 16:23:09
410
原创 树（六）——平衡二叉树
定义左右子树高度差的绝对值不超过1的二叉树称为平衡二叉树（Balanced Binary Tree），简称平衡树。平衡因子：节点左子树和右子树的高度差为该结点的平衡因子。平衡二叉树的平和因子值只能为-1，0，1。插入二叉排序树保证平衡的基本思想如下:每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位
2021-09-19 15:42:30
709
原创 树（五）——二叉排序树（BST）
定义二叉排序树是一棵具有如下特性的二叉树：若左子树非空，则左子树上所有节点的值均小于根节点的值若右子树非空，则右子树上所有节点的值均大于根节点的值左、右子树均为一棵排序二叉树二叉树的中序遍历可以得到一个递增的有序序列查找从根节点开始沿某个分支逐层向下比较。先跟根节点比较，如果值相等则查找成功若小于根节点的关键字，则再根节点的左子树上查找，否则在右子树上查找插入若原二叉树为空，则直接插入节点；否则，小于根节点的值，则插入到左子树，大于则插入到右子树上。插入的结点一定是一个新添的
2021-09-19 15:06:42
340
原创 树（四）——森林
众多的树的集合组成了森林树与二叉树的转换规则：节点的第一个孩子作为该节点的左孩子该节点相邻的右兄弟节点作为该节点的右孩子森林与二叉树的转换规则：每棵树转换为相应的二叉树每棵树的根节点视为兄弟关系，依次连接...
2021-09-19 14:26:02
565
原创 树（一）——二叉树
树树是n个节点的有限集。当n=0时，称为空树。在任意一颗非空树中应满足：有且仅有一个特定的称为根的节点当n>1时，其余节点可分为m个互不相交的有限集T1，T2，…，Tm，其中每个集合本身时一棵树，并且称为根的子树。其他术语如度、深度等等不做详细阐述性质树中的结点数等于所有节点的度数加1度为m的树中第i层之多有mi−1m^{i-1}mi−1个节点(i≥1i \geq 1i≥1)高度为h的m叉树至多有mh−1m−1\frac{m^h-1}{m-1}m−1mh−1个节点具有n个节点
2021-09-18 21:23:00
123
原创 树（三）——线索二叉树
基本概念遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点(第一个和最后一个结点除外）都有一个直接前驱和直接后继。传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含n个结点的二叉树中，有n+1n+1n+1个空指针。这是因为每个叶结点有2个空指针，每个度为1的结点有1个空指针，空指针总数为2n0+n12n_0+ n_12n0+n1，又n0=n2+1n_0 = n_2+ 1n0=n2+1，所以空指针总数为
2021-07-28 17:24:21
227
原创 树（八）——红黑树基本概念
红黑树是一种自平衡的二叉查找树二叉查找树的特点左子树上所有结点的值均小于或等于它的根结点的值。右子树上所有结点的值均大于或等于它的根结点的值。左、右子树也分别为二叉排序树。红黑树的特点节点是红色或黑色。根节点是黑色。每个叶子节点都会挂上两个NULL节点,且所有NULL节点都是黑的。每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个NULL节点的所有路径都包含相同数目的黑色节点。破坏的情况
2021-07-07 20:27:36
196
2
原创 树（九）——B和B+树
B-树(就是B树)Balance-Tree，多路平衡搜索树（并不是二叉）条件定义任何非叶子节点最多只能有MMM个儿子，且M>2M>2M>2根结点的儿子数为[2,M][2, M][2,M]；除根结点以外的非叶子结点的儿子数为[M/2,M][M/2, M][M/2,M]；每个结点存放至少⌊M2−1⌋\lfloor\frac{M}{2} -1\rfloor⌊2M−1⌋和至多M−1M-1M−1个关键字；（至少2个关键字）非叶子结点的关键字个数 = 指向儿子的指针个数-1；非叶子
2021-07-07 20:23:20
111
原创 基础排序代码
冒泡void BubbleSort(int *h,size_t len){ if(h==NULL) return; if(len<=1) return; for(int i = 0;i<len-1;i++){ for(int j = 0;j<len-1-i;j++){ if(h[j]>h[j+1]){ Swap(h[j],h[j+1]); }
2021-07-07 14:57:28
87
原创 动态规划(六)——总结
动态规划的核心思想就是存储之前操作的结果适用的情况如下：最优子结构性质。问题的最优解包含的子问题的解也是最优的，那么称该问题具有最优子结构性质。无后效性。即子问题的解一旦确定，就不再改变，不受之后、包含它的问题的求解决策影响子问题重叠性质。也就是有些子问题会被重复计算多次，动态规划就是利用这个性质，对每个子问题值计算一次。其余只需要进行查表即可一般有如下步骤问题拆分，找到问题之间的联系确定状态构成确定状态转换方程实现在问题拆分的过程中我们会涉及到一个或多个变量来表示当前所处的是
2021-07-07 14:53:12
105
原创 动态规划(五)——背包问题
问题背包问题的变体很多，这里主要分析三个类型：0-1背包，完全背包和多重背包。0-1背包问题有n件物品，每件物品有各自的重量和价值，现有一个一定容量的背包，问如何选择使背包物品价值最大分析最基础的方法是枚举，但时间复杂度为O(22)O(2^2)O(22)动态规划的可以将时间复杂度降为O(nm)O(nm)O(nm)设置一个二维数组dp[][],令dp[i][j]表示前i个物品装进容量为j的背包能获得的最大价值,则dp[n][m]就是问题的解对于容量为j的背包，如果不放入第i件物品，那么这
2021-07-06 23:54:27
2322
1
原创 动态规划(四)——最长公共子序列
问题在字符串S中按照先后顺序依次取出若干字符(不必连续),并将他们排列成一个新的字符串,这个字符串称为原字符串的子串。现在给定两个字符串S1和S2，求一个最长公共子串和其长度。分析最基础的方法就是枚举所有子序列，然后逐一判断子序列是否相同，时间复杂度O(nn+m)O(n^{n+m})O(nn+m)使用动态规划可将时间复杂度降为O(nm)O(nm)O(nm)设置二维数组dp[][],令 dp[i][j]表示以S1[i]作为结尾和以S2[j]为结尾的最长子序列的长度,最长为dp[n][m]当S1
2021-07-05 22:15:50
497
原创 动态规划(三)——最长递增子序列
问题给定一个序列{A1,A2,A3,...,An}\{A_1,A_2,A_3,...,A_n\}{A1,A2,A3,...,An},找出其中若干个元素(不必连续),构成新的子序列{Ax,...,Ay}\{A_x,...,A_y\}{Ax,...,Ay}使得∀x≤i<j≤y,有Ai<Aj\forall x\le i<j\le y ,有A_i<A_j∀x≤i<j≤y,有Ai<Aj。求最长递增子序列长度分析最基础的方法是枚举所有子序列，逐一判断，时间复杂
2021-07-05 17:34:15
143
原创 动态规划(二)——最大连续子序列和
问题给定一个序列{A1,A2,A3,...,An}\{A_1,A_2,A_3,...,A_n\}{A1,A2,A3,...,An},找出其中一个连续的子序列{Ai,Ai+1,...,Aj}\{A_i,A_i+1,...,A_j\}{Ai,Ai+1,...,Aj}使得这个连续的子序列的和最大分析最基础的方法就是枚举左右两个端点,计算其间的子序列之和,时间复杂度O(n3)O(n^3)O(n3)采用记录前缀的方法预处理Si=A1+⋅⋅⋅+AiS_i=A_1+\cdot \cdot \cdo
2021-07-05 15:55:23
221
原创 动态规划(一)——递推求解
基本思想动态规划和分治法有相似之处，也是将待求解问题分解成若干个子问题。与分治法不同的是，经动态规划划分的子问题往往不是相互独立的，如用分治法来解决这类问题，部分子问题会被重复计算多次。动态规划则是将已解决子问题的答案保存下来，在需要子问题答案的时候便可以直接获取，不需要重复计算，提高效率。经典问题（一）——递推求解最最经典的就是斐波那契数列用分治法使用递归完成，会重复计算多次，使用动态规划可以简化为如下vector<int> dp(MAXN);dp[0]=0;dp[1]=1;w
2021-07-05 15:15:10
391
原创 图论(五)——关键路径
原理AOE(Activity On Edge NetWork)图，以顶点表示事件，以有向边表示活动，以边上的权值表示该活动的持续时间。工程开始的顶点称为源点，该点的入度为0，如A；工程结束的顶点称为汇点，该点的出度为0，如点F。从源点到汇点的路径有多条，完成的事件有长短，且部分工作可以并行，那么拥有最长路径长度的路径影响了整个工程的完成时间，该路径称为关键路径，路径上的活动称为关键活动每个活动有最早的开始时间，即该活动的前序活动都已完成；也有最晚开始时间，即后序活动要按时完成，该活动的必须开始时间
2021-07-05 14:27:07
700
原创 图论(四)——拓扑排序
问题描述设一个有向无环图(DAG)，图中有多条有向边(U,V)(U,V)(U,V)。将图中所有的顶点排成一个线性序列，使得在该序列中顶点UUU都排列在顶点VVV之前。满足该要求的顶点序列，被称为满足拓扑序列，该过程成为拓扑排序方法从DAG图中选择入度为0的顶点,并输出从图中删除该入度为0的顶点及所有以它为起点的边重复1和2直到当前图为空,或者图中不存在入度为0的顶点。前者输出的序列为拓扑序列，后者说明图中存在环，没有拓扑序列例题题目描述有NNN个比赛队(1≤N≤500)(1\le N
2021-07-02 16:55:18
128
原创 图论(三)——最短路径
Dijkstra算法原理贪心和线性规划将顶点集分为S和TS：已经确定的顶点集合，初始只含源点sT：尚未确定的顶点集合反复从T中选取当前到源点s最近的顶点u，将顶点u加入集合S，然后对所有从u出发的边进行松弛操作1。这是典型的贪心策略，且该问题具备无后效性，所以可以收敛到最优解。算法步骤初始时，S只包含起点s；T包含除s外的其他顶点，且T中顶点的距离为"起点s到该顶点的距离"，不可达就是无穷大从T中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从T中移除顶点k。更新T中各个顶
2021-07-02 09:41:45
225
原创 图论(一)——并查集
原理将集合用树的形式表示,每个结点指向其父节点,只要在同一棵树上,就说明在同一个集合内功能判断任意两个元素是否属于一个集合(根结点相同在一个集合中)按照要求合并两个不同的集合(两棵树合并成一棵树)例题OJ描述某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？输入描述：测试输入包含若干测试用例。每个测试用例的
2021-06-29 21:24:47
102
原创 图论(二)——最小生成树
原理任何选择一些点属于集合A，剩余的点属于集合B，最小生成树必定存在一条权值最小的边，并且这条边的两个顶点分别属于集合A和集合B（即连通两个集合）算法步骤初始化所有顶点属于孤立的集合，即G为森林，每个节点为一棵树按照边权递增顺序遍历所有边，若遍历到的边的两个顶点仍分属不同的集合（该边即为连通这两个集合的边中权值最小的那条边），则确定改变为最小生成树上的一条边，并将该边两个顶点分属的集合合并遍历完所有边后，若原图连通，则被选取的边和所有顶点构成最小生成树；若原图不连通，最小生成树不存在例题O
2021-06-29 21:07:54
204
原创 接化发——递归和分治法
原理递归必需条件：子问题必须与原始问题相同，且规模更小不能无限制地调用本身，必须有一个递归出口分治思想：将一个复杂的问题分成两个或更多的子问题，子问题之间相互独立且与原问题相同或相似，重复分解，直至子问题可以简单地直接求解...
2021-06-29 15:01:39
102
原创 最优化——贪心策略
核心思想总是选择当前情况下最优的策略，能够得到局部最优解。但对于具备无后效性（即某个状态以前的过程不会影响以后的状态，只与当前状态有关）的问题，贪心策略可以获得全局最优解例子简单贪心有M的资源a，跟N个商人交换资源b，...
2021-06-28 16:29:55
307
原创 数学问题(七)——矩阵和矩阵快速幂
方法使用二维数组存储矩阵矩阵的基础操作有相加，相乘，转置矩阵的幂以乘法为基础操作，矩阵快速幂的基础思想和普通快速幂相同，只不过初始量不是1，是单位矩阵代码相加和转置都非常简单，在此展示较为常用乘法#define MAX 10struct Matirx{ int matrix[10][10]; int col, row; Matrix(int c, int r):col(c),row(r) {};}Matrix Multiply(Matrix x, Matirx y){ Mat
2021-06-24 20:46:28
113
原创 数学问题(六)——快速幂
方法对指数进行分解比如求282^828,可以分解为 8=4+4，4=2+2，2=1+1，只需要累乘三次就可以得到282^828的值代码求aba^bab末尾的三位数,其中MOD=1000int FastExponentiation(int a, int b){ int answer = 1; while (b != 0) { if (b % 2 == 1) { answer *= a; ans
2021-06-24 17:28:09
88
原创 数学问题(五)——分解质因数
方法要求质因数，那么先要有质因数，所以可以先采用筛法获取素数数组最简单的就是依次进行试除，如果可以整除则记录该因数代码
2021-06-24 10:40:57
284
原创 数学问题(四)——素数
方法最基础就是使用小于该整数的所有整数去试着整除这个数nnn进一步,将尝试范围缩小到n\sqrt{n}n使用筛法，找出范围内的所有素数找到一个素数，就将它的所有倍数均标记为非素数若遍历到某个数是，若未被任何小于它的素数标记为非素数，则它为素数代码基础方法比较简单，就不贴出来筛法bool isPrime[MAX]; // 标记数组vector<int> prime; // 素数数组void Initial(){ for (int i = 0; i
2021-06-23 17:18:55
127
原创 数学问题(三)——最大公约数和最小公倍数
方法最大公约数辗转相除法若整数g为a,b(不同时为0)的公约数,则g满足a=g×l,b=g×m,其中l,m为整数a=b×k+r,其中k为整数,r为a除以b后的余数由上述三个公式可推出g×l=g×m×k+r⇒r=g×(l−m×k)若整数g为a,b(不同时为0)的公约数,则g满足 \\a = g \times l,b = g \times m,其中l,m为整数\\a = b \times k + r,其中k为整数,r为a除以b后的余数\\由上述三个公式可推出g \times l = g \tim
2021-06-23 16:36:14
124
原创 c++字符串逆序——头插方式构建和调用reverse()对比
菜鸡出没，大佬莫喷起因在做一道题时产生疑问，有构建字符串的过程如下(是抽象后的,不是原题):string s;// 类似头插for(int i = 0; i < 10; i++){ s = i + s;}然后在<algorithm>头文件是提供了逆序的函数string s;//类似尾插for(int i = 0; i < 10; i++){ s += i;}reverse(s.begin(), s.end());那么问题来了，哪个更快呢？有什么本质上
2021-06-23 00:10:14
267
1
原创 数学问题(一)——进制转换
解法就是基础的求模和整除运算，但一般都会涉及大整数的转换，所以要注意字符串的操作，当然十进制以上的就更不用说了大数处理问题课参照我的另一篇博客——数学问题(二)——大数处理例题OJ链接描述将M进制的数X转换为N进制的数输出。输入描述：输入的第一行包括两个整数：M和N(2<=M,N<=36)。下面的一行输入一个数X，X是M进制的数，现在要求你将M进制的数X转换成N进制的数输出。输出描述：输出X的N进制表示的数。示例1输入：10 211输出：1011备注：注意
2021-06-22 20:49:30
179
原创 数学问题(二)——大数处理
虽然也算不上传统的数学问题，但是在计算的过程中是需要处理的，一般会涉及四则运算，那么就算作是数学问题吧。解法首先使用字符或整型数组存储大整数// 不妨设最大长度为1000# define MAX_LEN 1000struct BigNumber{ int number[MAX_LEN]; int len; BigNumber(){ memset(number, 0, sizeof(number)); } };此外，我们不妨假设大整数使用的是十进制#define WEIGHT
2021-06-22 20:22:16
180
原创 云服务器（自己开发用的）无法访问的原因
问题情形在浏览器输入地址，持续一段时间后也无法访问可能的情况网络不好或者访问的是国外的服务器云服务器没有开放相应的端口号防火墙没有开放相应的端口号firewall-cmd --add-port=xx/tcp --permanentfirewall-cmd --reload没有添加正确的映射（后缀）可能运行的程序中的映射为/hello,但是只输入了xxx.xxx.xxx.xxx:80...
2021-06-17 11:18:46
442
原创 服务器环境搭建——安装Nginx
环境操作系统：Centos7.6Nginx：1.19.10步骤下载并上传安装包官网解压tar -zxvf nginx-1.19.10.tar.gz安装所需要的依赖yum install gcc-c++yum install -y pcre pcre-develyum install -y zlib zlb-develyum install -y openssl openssl-devel创建makeFile文件进入解压出的文件夹中./configure \--pref
2021-06-17 09:38:57
153
原创 服务器SSH保持连接
方法修改sshd配置文件步骤去掉TCPKeepAlive yes的注释去掉注释#ClientAliveInterval 0#ClientAliveCountMax 3修改ClientAliveInterval 30 ClientAliveCountMax 86400第一行为客户端每隔多少秒向服务发送一个心跳数据第二行为客户端多少秒没反应,服务器自动断掉连接重启服务systemctl restart sshd...
2021-06-16 12:41:48
141
原创 服务器环境搭建——安装Redis
环境操作系统：Centos7.6Redis：6.2.4步骤下载Redis直接官网下载上传服务器，或wget下载。放到自己想安装的目录。wget https://download.redis.io/releases/redis-6.2.4.tar.gz解压tar -zxvf redis-6.2.4.tar.gz基本环境安装yum install gcc-c++ -y安装进入解压目录（Redis Home）输入指令make#继续输入命令，指定安装目录/usr/l
2021-06-15 17:39:51
1297
原创 服务器环境搭建——安装mysql
环境操作系统：64位的Centos7.6mysql：8.0.25步骤下载rpm并上传到服务器去官网下载对应操作系统的rpm包。我是centos7，选择第二个。当然有了链接也可以使用wegt指令，避免上传的步骤安装RPM安装包yum localinstall mysql80-community-release-el7-3.noarch.rpm下载安装MySQLyum install mysql-community-server开启服务systemctl start mysqld
2021-06-15 16:55:04
1678
2
原创 服务器环境搭建——安装Java运行环境
选择我服务器的操作系统是64位的Centos7.6，选择安装jdk1.8步骤下载安装包去官网下载相应的压缩包将安装包通过ftp传到服务器上，我将压缩包放在了/usr/local中解压tar -xvf jdk-8u291-linux-x64.tar.gz为了方便输入和记忆,可以修改一下目录名mv jdk1.8.0_291/ jdk1.8/设置环境变量vi /etc/profile在文件中添加如下内容#set java environmentJAVA_HOME=/usr/local
2021-06-15 15:32:42
3586
1
原创 已知二叉树先序遍历和后序遍历序列，求可能的中序遍历序列及方案数
分析参考理论依据在参考中,这里简单说明一下假设先序遍历序列为Pre,后序遍历的序列为Post记其中一个结点为v,则在Pre中存在以v为开头的最长后缀Pv使得在Post中有以v为结尾的最长前缀Sv与Pv中元素相同假设先序遍历序列为Pre,后序遍历的序列为Post\\记其中一个结点为v,则在Pre中存在以v为开头的最长后缀P_v\\使得在Post中有以v为结尾的最长前缀S_v与P_v中元素相同假设先序遍历序列为Pre,后序遍历的序列为Post记其中一个结点为v,则在Pre中存在以v为开头的最长后缀
2021-06-02 15:31:37
1882
1
原创 markdown页内跳转
方法一、使用目录如CSDN的@[TOC](目录标题)目录标题方法一、使用目录方法二、html标签方法二、html标签在需要跳转的地方加上相应的标签如<span id="method1"></span>在相应的位置添加跳转指令[...](#method1)method1...
2021-06-01 10:47:04
164
学堂在线作业.pdf
2020-05-24
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人