二叉树的遍历

二叉树定义 有一个根节点; 除根节点外,其他每个节点都与其唯一的父节点相连; 从根节点到其他每个节点都有且仅有一条路径; 如果每个节点最多有两个子节点,我们就称这样的树为二叉树 二叉树遍历 树的遍历分为先序遍历、中序遍历和后序遍历。 初次学习树的遍历时比较难理解这几个定义到底是什么意思,是根据什么来定义先后和中的? 其实是根据根节点调用位置定义的。 所谓...

猫扑素数

前言 关于猫扑素数,首先我有2个定义不明白: 什么是素数? 怎么才算猫扑素数? 或许弄清这两个问题就方便下手了。 素数 说素数不懂,但是换个说法,质数,应该很多人就明白了。 百科里这样定义:质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数,这样的数称为质数。 这样一下子就明朗起来了,质数的定义...

算法之朴素模式匹配

0x00 前言 不论英文还是中文,在看文章时经常会遇到查找某个单词或字组的时候,把一篇文章看作是一个大的字符串,要查找的内容作为子串,这种在大串中查找子串的操作叫做串的模式匹配。 我们知道了这种行为叫串的模式匹配,但我们不清楚的是到底如何匹配,具体的操作是什么? 0x01 我如何操作 在我看来要从大串中寻找子串,最直接的方法就是从大串起始位置开始,挨个字符比...

两个栈实现队列功能

0x00 前言 用2个栈实现队列,首先要明白栈和队列的区别:栈是FILO,队列是FIFO。明白了这两点就比较容易实现了。 0x01 分析 栈是一端开口,队列是两端开口,如果要让栈实现队列功能,需要2个栈一个负责进数据,一个负责出数据。为了保证出数据的顺序,在出数据栈不为空时,入数据的栈中数据不能往出数据的栈里存。 0x02 实现 在2个栈数据都为空时注意...

设计一个有获取元素最小值getMin的栈

0x00 前言 栈可以看成一个瓶子,只有一个口,另一端被封底。这样数据进出都只能从一个口经过。这样就导致的一个直接结果就是数据FILO问题。要找到栈中最小数据,单靠一个栈不能完成,需要外部提供辅助。 0x01 分析 一个存好数据的栈,要从里面找到最小数值,不可避免的要把数据出栈,然后进行对比。这时有个问题就来了,找到最小数值后,其他数据还有用吗?换句话说,其...

算法排序之快速排序

实现目标 本例中希望通过快速排序,使得数组最终按非递减顺序排列。 数组初始值为:{ 156, 141, 35, 94, 88, 61, 111 } 数组最终值为:{ 35, 61, 88, 94, 111, 141, 156 } 实现分析 快排是根据分治思想, ①选取一个基数, ②将无序数组分为大小两个数组,其中一个数组值全都比基数小,另一个数组值全都比...

算法查找之二分查找

实现目标 查看24是否在数组{ 8,14,24,28,30,31,32 }中, 如果在数组中则返回数组元素下标,否则返回-1 。 数组下标从0开始,查找24时最终返回下标2。 实现分析 说明 二分法前提是数组是有序的; 要查找的数我们称为关键值 阐述实现 在一个有序数组中二分查找一个数,数组长度为n。 1、设置左右下标变量:left,right,...

算法排序之交换排序

实现目标 本例中希望通过交换排序,使得数组最终按非递减顺序排列。 数组初始值为:{ 156, 141, 35, 94, 88, 61, 111 } 数组最终值为:{ 35, 61, 88, 94, 111, 141, 156 } 实现分析 说明 希望数组按非递减顺序排列,我们可以得到两点消息:1、数组中可能会有重复的元素,所以才说是非递减。2、排序后...