分类目录归档:数据结构和算法

B+树学习笔记

不知道你有没有这样的困惑,B+树的资料看了很多,依旧对B+树没有一个具象的认识。我也是这么走过来的,所以希望这篇笔记能帮到你。

一、演化阶段
你或许知道,或许不知道。B+树是由二叉树不断演化过来的。
大致的演化路线如下:
二叉查找树 -> 平衡二叉树 -> B树 -> B+树。

为了说清楚B+说,我们很有必要搞清楚演化过程中每个阶段的特点。
继续阅读

数组不连续取数问题(不连续取糖果)

回想最初遇到这个问题的时候,题面描述如下:

有连续编号的盒子内放着数量不等的糖果,有个强盗来打劫,不允许从两个相邻的盒子中取走糖果,问最多能获取到多少颗糖果。

起初还以为是leetcode上的分糖果问题,其实不一样。后来遇到了leetcode打家劫舍方知是这题,出题人很巧妙的包装了问题。

一、思路:
具象分析这个问题,可以如下表述:
给定一个维数组,长度为N。不允许取连续的两个数,求取到数字的最大和

例:输入:[1,3,5,2,1,9,4,3,7]
答案为:1+5+9+7=22
继续阅读

N盏灯问题

N盏灯问题是个很有意思的问题,是一个数学题,也是一个编程题。

这个问题,有很多不同的叫法
0、N个人开关N盏灯问题
1、开关灯问题

一、问题描述:
有N盏灯放在一排,从1到N依次顺序编号。有N个人,也从1到N顺序编号。1号将灯全部关闭,2号将凡是2的倍数的灯全部打开;3号将3的倍数的灯全部作相反操作(该灯如为打开,则将它关闭;如关闭,则将灯打开)。以后的人,都和3号操作一样,将凡是自己序号倍数的灯作相反操作。第N个人操作完之后,一共有几盏灯亮着?

二、问题分析
灯编号: 1->N
人编号: 1->N
开始灯都关着
灯 % 人 == 0 按一次开关
第N个人操作后,亮个的灯的个数
继续阅读

堆及堆排序PHP实现

一、什么是堆

堆是一种数据结构,特殊的树形数据结构。常见的堆有二叉堆、二项式堆、斐波拉契堆等。
堆这种数据结构主要用来实现两个功能:堆排序和优先队列。

PHP SPL中有堆这种数据结构(SplHeap),及优先队列(SplPriorityQueue)。

二、细说二叉堆

这里细说的堆排序使用的是二叉堆,那么二叉堆是什么样的呢
二叉堆是一颗完全二叉树(维基百科提到还有可能是近似完全二叉树,很不理解),节点和双亲节点维持着固定的关系,要么节点的值都大于双亲节点,要么节点的值都小于双亲节点,并且每个节点的左右子树都是二叉堆。【完全二叉树及堆的图,可参考知乎专栏,传送门
特点:
0、节点都大于双亲节点的二叉堆叫大顶堆。
1、节点都小于双亲节点的二叉堆叫小顶堆。
2、二叉堆一般用一维数组来存储。
3、二叉堆一个节点的左右孩子没有顺序。
4、有n个元素的二叉堆,最后一个非叶节点为n/2 -1
继续阅读

PHP基于Trie实现敏感词检索

算法:
* 0、构建Trie树
* 1、遍历目标字符串中的每一个字符,如果字符不存在,继续下一个。
* 2、如果字符存在,从该字符下一个字符开始遍历,匹配成功后直接返回匹配字符长度,然后跳过这个长度并不是+1, 算是优化了【匹配到一个词后直接返回,没有往下找最长】,否则回到第1步
* 3、重复1-2
继续阅读

排序之插入排序

一、原理
插入排序原理,通过构建有序序列,对于未排序的数据部分,在已排序的序列中从后往前扫描,找到相应的位置,逐个元素插入。类似于打扑克牌,取牌的过程。

二、算法
0、从第一个元素开始,认为该元素已被排序。
1、取下一个元素,在已经排序的元素序列中从后往前扫描。【取下一个元素这个表述特别赞,如果用第二个元素就不好表达后面的插入了】
2、如果该元素大于新元素,则后移该元素。
3、重复步骤2,直到找到小于、等于新元素的位置。
4、将新元素插入到该位置后。
5、重复步骤1-4。
继续阅读

PHP实现括号匹配检查

思考这样一个经典的问题,检查一个字符串中的括号(只有括号)是否匹配?

很多年前在面试的时候被问到这个问题,自己想到的是用正则来处理,具体实现的时候又无法兼容全部情况。

事后知道用栈就能很容易的处理。栈是一种特殊的线性表,只能在一端进行插入和删除操作,具有后进先出的特点。

实现算法:
0、遍历字符串,判断括号类型
1、如果是左括号,添加到数组中
2、如果是右括号,从数组中取出最后一个元素,没有元素或不匹配验证失败;匹配这删除元素,继续
3、遍历完后,检查数组是否为空,为空则验证成功,否则验证失败。
继续阅读