札记之PHP实现AVL树(平衡二叉树)
定义：
一棵AVL树需要满足以下的条件:
它的左子树和右子树都是AVL树。
左子树和右子树的高度差不能超过1。
性质:
一棵n个节点的AVL树的其高度保持在O(log2(n))。
一棵n个节点的AVL树的平均搜索长度保持在O(log2(n))。
一棵n个节点的AVL树删除一个结点做平衡化旋转所
...
札记之PHP实现字典树(Trie)
Posted on
|
In
数据结构，算法
我们每天百度搜索的时候，输入一个字符，搜索框下会展示前缀相似的搜索提示，这个是怎么做到的呢？？？
定义
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计，它的优点是：最
...
札记之PHP实现KMP算法
Posted on
|
In
数据结构，算法
定义KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。
部分算法比较 [克努斯-莫里斯-普拉特算法即KMP算法]令 m 为模式的长度， n 为要搜索的字符串长度， k为字母表
...
札记之PHP实现BM算法
Posted on
|
In
数据结构，算法
暴力匹配（BF）算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较，直到得出最后的匹配结果。
问题
有两个字符串，S1是母串，S2是子串，要在
...
札记之PHP实现动态规划01背包问题
Posted on
|
In
数据结构，算法
背包问题:有一个背包，容量为4磅，现有如下物品；
要求装入的物品不能重复；
要求达到的目标为装入的背包的总价值最大，并且重量不超出；
物品
重量
价格
吉他
1
1500
音箱
4
3000
电脑
3
2000
动态规划的原理
动态规划与分治法类似，都是把大问题拆
...
札记之PHP实现Dijkstra算法[广度搜索]
Posted on
|
In
数据结构，算法
上一篇采用的是优先队列实现，这篇用广度搜索实现，从图示+代码层更好理解了
图示
算法思路定义三个数组
$visited: 记录各个顶点是否访问过1表示访问过,0未访问;
$preVisited: 每个下标对应的值为前一个顶点下标[可以访问到任何顶点的最短路径];
$distance: 记录出发顶
...
curl发送json请求
Posted on
|
In
curl
跟计费部门对接，存管系统返回给他们的数据格式跟之前不一样，但是让他们重推又很麻烦，干脆自己模拟推送，自己解析了
CURL 发送json请求1curl -i -X POST -H "'Content-type':'application/json'" -d '{"details":
...
札记之PHP实现八皇后
Posted on
|
In
数据结构，算法
题目：
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
PHP代码实现123456789101112131415161718192021222324252
...
札记之PHP实现Dijkstra算法[优先队列]
Posted on
|
In
数据结构，算法
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
图示
算法思路
指定一个节点，例如我们要计算 ‘A’ 到其他节点的最短路径；
定义两个数组（$distance，$pre
...
札记之PHP实现图的广度优先遍历(BFS)
Posted on
|
In
数据结构，算法
基本思想
从图中的某个顶点V出发访问并记录；
依次访问顶点V的邻接顶点w1、w2……wk；
分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，直到图中所有已被访问过的顶点的邻接点都被访问到；
重复第3步，直到图中所有顶点都被访问完为止。
存储结构
实现方式邻接表非递归实现
广度优先算法：采
...