二分查找有序数组
昨天百度面试，问了这样一道题： 对于一个有序字符串数组，用二分法查找某一字符串是否存在于该字符串数组中。函数原型为： bool binarysearch(const vector
算法笔记-ag真人游戏
异质链表
程序中，用基类类型指针，可以生成一个连接不同派生类对象的动态链表， 即每个节点指针可以指向类层次中不同的派生类对象。 这种节点类型不相同的链表称为异质链表。 如：任务管理器，管理不同的进程 #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点最少需要多少步数？ ...
数组中只出现一次的数
问题一：在一个整数数组中，除了一个数之外，其他的数出现的次数都是两次，求出现一次的数，要求时间复杂度尽可能的小。例如数组{1,2,2,3,3,6,6},出现一次的数是1. 从题目的描述可以看出，数组中只有一个数字出现了一次，其他的数...
bitmap算法详解
所谓的bitmap就是用一个bit位来标记某个元素所对应的value，而key即是该元素，由于bitmap使用了bit位来存储数据，因此可以大大节省存储空间。 基本思想： 这此我用一个简单的例子来详细介绍bitmap算法的原理。假设...
布隆过滤器
如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速...
对一致性hash原理的理解
一致性hash算法解决的核心问题是，当solt数发生变化的时候能够尽量少的移动数据。该算法最早在《consistent hashing and random trees:distributed caching protocols for r...
哈希的应用（位图，布隆过滤器）
位图（整型） 1.面试题 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数 中。【腾讯】 遍历，时间复杂度o(n) 排序(o(nlogn))，利用二分查找: logn 位图解决 数据是否在给定的...