菜鸟笔记双指针技巧
我认为双指针技巧还可以分为两类，一类是「快慢指针」，另一类是「左右指针」。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。 一、快慢指针的常见算法 快慢指针一般都初始化指向...
算法笔记 第15页
菜鸟
详解二分查找算法
我周围的人几乎都认为二分查找很简单，但事实真的如此吗？二分查找真的很简单吗？并不简单。看看 Knuth 大佬（发明 KMP 算法的那位）怎么说的： Although the basic idea of binary search is co...
C++求n个数的中位数
/* * 求n个数的中位数 - C++ - by Chimomo * * 对于一组有有限个数的数据来说，它们的中位数是这样的一种数：这群数据里的一半的数据比它大，而另外一半数据比它小。 * 计算有限个数的数据的中位数的方法是：把所有的同类数...
一个漂亮的打印二叉树的程序
写二叉树的程序时经常会遇到希望漂亮地把二叉树给输出，本文给出了一个小程序。 以下时打印的效果： // copyright @ L.J.SHOU Jan.16, 2014 // a fancy binary tree printer #ifn...
最短路径算法-----Dijkstra迪杰斯特拉算法
1 前言 本章介绍迪杰斯特拉算法。和以往一样，本文会先对迪杰斯特拉算法的理论论知识进行介绍，然后给出C语言的实现。后续再分别给出C++和Java版本的实现。 2 迪杰斯特拉算法介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于...
二分查找有序数组
昨天百度面试，问了这样一道题： 对于一个有序字符串数组，用二分法查找某一字符串是否存在于该字符串数组中。函数原型为： bool BinarySearch(const vector<string>& array, ...
异质链表
程序中，用基类类型指针，可以生成一个连接不同派生类对象的动态链表， 即每个节点指针可以指向类层次中不同的派生类对象。 这种节点类型不相同的链表称为异质链表。 如：任务管理器，管理不同的进程 #include "di...
二叉搜索树
二叉查找树定义 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所...
寻找丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number），例如：2,3,4,5,6,8,9,10,12,15,等，习惯上我们把1当做是第一个丑数。 写一个高效算法，返回第n个丑数。 最普通（也最耗时）的做法是从1开始遍历，然后判断这个...
菜鸟
蚂蚱跳跃问题
蚂蚱跳跃问题 题目大意： 一个蚂蚱最初位于坐标轴的原点，现在蚂蚱要跳跃到坐标轴的s点，跳跃规则是蚂蚱既可以往正方向跳跃，也可以往负方向跳跃，蚂蚱第一次跳跃1个单位，以后的跳跃步数在前一步的基础上加一。现在求蚂蚱跳跃到s点最少需要多少步数？ ...