算法基础13 树与图的深度优先遍历与广度优先遍历
树与图的存储「存储方式:」
邻接矩阵
邻接表(常用)
123456//邻接表int h[N], e[N * 2], ne[N * 2], idx;void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
树与图的深度优先遍历遍历就根据邻接表遍历方式进行。
1234567891011--------模版---------------// 需要标记数组st[N], 遍历节点的每个相邻的便void dfs(int u) { st[u] = true; // 标记一下,记录为已经被搜索过了,下面进行搜索过程 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { dfs(j); } }}
树的重心给定一颗树,树中包含 n个结点(编号 1∼n)和 n−1条无向边。 ...
Hexo收录百度and必应
1.步骤「优化文章链接:」
我们首先看没有优化的文章链接,按照日期+文章标题,但是这样有一个非常严重的错误,如果我们更改文章标题,那么文章原来的链接就会改变,而搜索引擎会不会收录稳定性不高的文章,同时访客也无法长期访问。
我们需要安装插件:
1npm install hexo-abbrlink --save
在hexo主配置文件中修改:
1permalink: posts/:abbrlink.html
修改完毕后: 为数字形式
「百度站长工具设置:」
点击链接:站点管理_站长工具_百度搜索资源平台 (baidu.com)
然后 站点管理—> 添加网站—>自己填写信息进行验证。
「安装插件:」
123npm install hexo-baidu-url-submit --savenpm install hexo-generator-sitemap --save npm install hexo-generator-baidu-sitemap --save
「修改配置文件:」
在hexo主配置文件中新增
12345baidu_url_submit: c ...
Hexo--Butterfly修改CDN加快页面访问速度
1.主要原因在Butterfly主题中有时会发现页面速度加载较慢,这时打开 开发者工具发现,是有一些引用资源的引用地址访问太慢导致,解决办法是替换引用资源的地址即可。
2.解决办法在Butterfly的主题配置文件 _config.yml中,注意不是hexo的配置文件,是主题配置文件,打开拉到最下面,找到CDN这一项,然后找到 option,把加载不出来的文件链接进行替换即可。
详细参数可访问Butterfly官方文档:Butterfly 安裝文檔(四) 主題配置-2 | Butterfly
全局修改「思路:」全局修改可以将所有引用文件替换成一个服务厂商的,这里介绍替换为elemecdn。
「参考:」06_Hexo-elemecdn 加速 Butterfly 第三方资源 | Mycpen
「步骤:」
修改 themes/butterfly/scripts/events/cdn.js,增加 elemecdn 字段
1elemecdn: `https://npm.elemecdn.com/${name}${ve ...
算法基础12 深度优先搜索+广度优先搜索
1.DFS—深度优先搜索排列数字给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
输入格式 共一行,包含一个整数 n。
输出格式按字典序输出所有排列方案,每个方案占一行。
数据范围
11≤n≤7
输入样例:
13
输出样例:
1234561 2 31 3 22 1 32 3 13 1 23 2 1
「完整代码:」
1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>using namespace std;const int N = 10;int n;int path[N];bool st[N];void dfs(int x){ // 如果x到达最后一层,就进行输出 if(x == n) { for(int i = 0; i < n;i++) { cout << p ...
算法基础11 哈希表
1.模拟散列表开放寻址法「解题思路:」 用2 ~ 3倍的空间来存储,这样一般不会发生溢出问题。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <bits/stdc++.h>using namespace std;const int N = 200003,null = 0x3f3f3f3f;int h[N];// find 函数:如果是 x在h中不存在,则返回其该插入的位置// 如果存在,则返回其所在的位置int find(int x){ int k = (x % N + N) % N; while(h[k] != null and h[k] != x) { k++; if(k == N) { k = 0; } } return k; ...
算法基础10 堆
1.堆排序测试数据
根节点不包含字符,除根节点外的每一个子节点都包含一个字符。从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。每个节点的所有子节点包含的字符互不相同。通常在实现的时候,会在节点结构中设置一个标志,用来标记该结点处
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <bits/stdc++.h>using namespace std;// 手写一个堆// 1.插入一个数// 2.求集合当中的最小值// 3.删除最小值// 4.删除任意一个元素// 5.修改任意一个元素const int N = 100010;int n, m;int h[N], cnt;void down(int u){ int t = u; if (u * 2 <= cnt and h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 &l ...
算法基础09 合并集合
1.合并集合1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int arr[N];int find(int x){ if (arr[x] != x) { arr[x] = find(arr[x]); } return arr[x];}int main(){ int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { arr[i] = i; } while (m--) { char c1; int a, b; ...
算法基础08 tire树
1.tire树「tire数定义:」
什么是Trie树Trie树,又叫字典树、前缀树(Prefix Tree)、单词查找树 或 键树,是一种多叉树结构。如下图:
上图是一棵Trie树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质:
根节点不包含字符,除根节点外的每一个子节点都包含一个字符。从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。每个节点的所有子节点包含的字符互不相同。通常在实现的时候,会在节点结构中设置一个标志,用来标记该结点处是否构成一个单词(关键字)。
可以看出,Trie树的关键字一般都是字符串,而且Trie树把每个关键字保存在一条路径上,而不是一个结点中。另外,两个有公共前缀的关键字,在Trie树中前缀部分的路径相同,所以Trie树又叫做前缀树(Prefix Tree)。
「变量介绍:」
123C++int arr[N][30], cnt[N], idx; // 二维数组 N 对应字符串最大长度,30对应 26个字的26种状态,这里稍微增大 ...
算法基础07 字符串比较大小问题
C++ string字符串比较方法详解字符串可以和类型相同的字符串相比较,也可以和具有同样字符类型的数组比较。
Basic_string 类模板既提供了 >、<、==、>=、<=、!= 等比较运算符,还提供了 compare() 函数,其中 compare() 函数支持多参数处理,支持用索引值和长度定位子串进行比较。该函数返回一个整数来表示比较结果。如果相比较的两个子串相同,compare() 函数返回 0,否则返回非零值。
compare()函数类 basic_string 的成员函数 compare() 的原型如下:
123456PLAINTEXTint compare (const basic_string& s) const;int compare (const Ch* p) const;int compare (size_type pos, size_type n, const basic_string& s) const;int compare (size_type pos, size ...
算法基础06 kmp字符串匹配算法
1.kmp 字符串匹配「kmp算法介绍:」
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1]。
字符串的模式匹配是一种常用的运算。所谓模式匹配,可以简单地理解为在目标(字符串)中寻找一个给定的模式(也是字符串),返回目标和模式匹配的第一个子串的首字符位置。通常目标串比较大,而模式串则比较短小。
简洁来说,就是在较长的字符串S中寻找子串P是否存在以及多少个的问题。
「实现思路:」
朴素做法:可以使用暴力枚举,但是时间复杂度高,耗时。
优化做法:使用ne[]数组存储子串P最大匹配后缀与最匹配大前缀的下标。
如果遇到不匹配,则跳到P子串与当前位置元素匹配的最大前缀位置。
这么说可能很抽象,画图表示。
假如以上 S (长传)与 P(子串)
先让P匹配自己,让每一 ...