寻找丑数
把只包含质因子2、3和5的数称作丑数（ugly number），例如：2,3,4,5,6,8,9,10,12,15,等，习惯上我们把1当做是第一个丑数。 写一个高效算法，返回第n个丑数。 最普通（也最耗时）的做法是从1开始遍历，然后判断这个...
算法笔记-ag真人游戏
蚂蚱跳跃问题
蚂蚱跳跃问题 题目大意： 一个蚂蚱最初位于坐标轴的原点，现在蚂蚱要跳跃到坐标轴的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 位图解决 数据是否在给定的...
八大排序算法及其优化
常见的排序算法 1. 直接插入排序 （1）算法基本思想 （2）特性总结： 元素集合越接近有序，直接插入算法的时间效率越高 时间复杂度：o(n^2) 空间复杂度：o(1)，它是一种稳定的排序算法 稳定性：稳定 （3）代码实现： void in...