Pistachio's Blog

Later equals never.

BFS

1. 定义树的BFS：从根节点开始，从左到右，从上到下进行的层次遍历；图的BFS：从根节点出发，找与该结点相邻的所有结点，如此类推，一层层遍历。图没有根结点，就得找一个点作为根节点。例如是A，则找与A相连距离1条边的结点，有B、C；再找与A距离2条边的结点有D、E；最后与A距离为3的结点有F。故BFS的遍历顺序为：ABCDEF 注意，取的点不同，有不同的遍历结......

Posted by Liao on 2019-08-31

并查集

一. 定义并查集 (Disjoint set) 是一种树型数据结构，用于处理一些不相交集合的合并及查询问题，或者检查图上是否存在环。 Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 Union：将两个子集合并成同一个集合。性质：同一个集合的任意两个顶点相连会形成环二. 分析int find(int x):通过递归查找元素所在的根节点。 void unio......

Posted by Liao on 2019-08-28

DFS

1. 定义深度优先搜索算法（DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。由于在不同节点上选择可以很多种，因此DFS的结果不唯一。通常使用递归or栈来实现DFS。 2.过程DFS的过程类似于栈的结构：后进先出，从根节点开始，把处理过的节点弹出栈，把出栈元素的邻接点放入栈......

Posted by Liao on 2019-08-24

STL之map

一定义C++中map提供的是一种键值对容器，里面的数据都是成对出现的。每一对中的第一个值称之为关键字(key)，每个关键字只能在map中出现一次；第二个称之为该关键字的对应值。 map的底层实现时红黑树，查询的时间复杂度时log(n) 1map<type,type> mymap; 二声明1#include<map> 三插入操作1.通过inset插入 1234......

Posted by Liao on 2019-08-16

STL之set集合

一定义 set A; set中的元素已排好序 set中的元素不重复二用法 A.insert(item); A.earse(item); //删除元素item A.clear(); //清空set A.empty(); A.size() A.find(k); A.lower_bound(k) ......

Posted by Liao on 2019-08-15

优先队列

优先队列一. 定义优先队列不再遵循先入先出的原则，而是分为两种情况：最大优先队列，无论入队顺序，当前最大的元素优先出队。最小优先队列，无论入队顺序，当前最小的元素优先出队。因此可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。优先队列的入队和出队的时间复杂度和二叉堆结点上浮下沉的一样，都是O(logn)，n为队列元素个数 priorit......

Posted by Liao on 2019-08-14

编程小知识

1）字符变数字：str[i]-‘0’123int num = 123;string s = to_string(num);cout << s[0]-'0'<<endl; 2）char *strncpy(char *dest,const char *src,size_t n)把str所指向的字符串复制最多n个字符到dest 1234567891......

Posted by Liao on 2019-07-24

队列基本用法

牛客上做的一个题目：https://ac.nowcoder.com/acm/contest/258/A 以样例为例： 123456输入3 71 2 1 5 4 4 1输出 5 容量为3，文章长度为7，第二行为文章内容。依题意，检索到相同的就为同一个单词，当单词数量大于容量的时候，软件会清空最早存入内存的单词，腾出单元，存放新单词。因此符合队列先进先出的特点。 1234567891011......

Posted by Liao on 2019-07-24

git的常用操作

git常用操作github上传laravel项目123456789git initgit remote add origin git@github.com:pistachioL/xxx.gitgit add .git commit -m "xxxx"git push origin master -f 删除远程关联 git remote rm origin 创建新分支......

Posted by Liao on 2019-07-12

树

2019蓝桥杯校内选拔一题一棵包含有2019个结点的树，最多包含多少个叶结点？解法1：首先他问“最多”，当然便是完全二叉树（满二叉树）了。记i为树的层数，由完全二叉树的性质可得，结点总数为$$2^i-1$$，叶子结点总数为$$2^(i-1)$$，列出等式即可计算出。解法2：二叉树的性质：叶子结点 = 度为2的结点数 + 1 当二叉树叶子结点最多时，即度为2的结点数最多......

Posted by Liao on 2019-07-12