蓄水池抽样算法 (reservoir sampling algorithm)
蓄水池抽样算法简介 蓄水池抽样算法是随机算法的一种，用来从n个样本中随机选择k个样本，其中n非常大（以至于n个样本不能同时放入内存）或者n是一个未知数。其时间复杂度为o(n)，包含下列步骤 (假设有一维数组 s, 长度未知，需要从中随机选择...
算法笔记-ag真人游戏
寻找多数元素
令a[1...n]是一个整数数列，a中的整数a如果出现的次数多于[n/2]，那么称a为多数元素。 有一个比较漂亮的求解法，我们用归纳法导出这个算法，这个算法的实质是基于下面的观察结论。 观察结论：在原序列中去除两个不同的元素后，那么原序列中...
无序数组中找第k大的数
类快排算法 leetcode215 由于只要求找出第k大的数，没必要将数组中所有值都排序。 快排中的partition算法，返回key在数组中的位置的cnt（相对于left的偏移量），如果cnt正好等于k，那么问题则得到解决；如果cnt小于...
一致性哈希算法原理
一致性hash算法背景 一致性哈希算法在1997年由麻省理工学院的karger等人在解决分布式cache中提出的，设计目标是为了解决因特网中的热点(hot spot)问题，初衷和carp十分类似。一致性哈希修正了carp使用的简单哈希算...
布隆过滤器(bloom filter)的原理和实现
什么情况下需要布隆过滤器？ 先来看几个比较常见的例子 字处理软件中，需要检查一个英语单词是否拼写正确 在 fbi，一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里，一个网址是否被访问过 yahoo, gmail等邮箱垃圾邮件过滤功能 这几...
sunday 字符串匹配算法(c 实现)
简介： sunday算法是daniel m.sunday于1990年提出的一种字符串模式匹配算法。其核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符...
找出字符串中的最长回文子串 - 马拉车算法
问题： 找出字符串中的最长回文子串 思路： 举例分析下，例如 ”abadaba“ 这个字符串的计算 1、从左往右遍历，整个字符串，把每个字符和字符间的空隙当作回文的中心，然后向两边扩展来找到最长回文串，这种情况下默认得对每一个字符进行计算，...
c 矩阵转置
c 矩阵转置 看了很多网山有关矩阵转置的代码，大部分还用了中间变量，本人亲测矩阵转置代码无误，望对广大c 初学者有所帮助！ 题目如下： 写一个函数，使给定的一个二维数组（3x3）转置，即行列互换。 input 一个3×3的矩阵 outp...
排序算法汇总
在笔试面试的过程中，常常会考察一下常见的几种排序算法，包括冒泡排序，选择排序，插入排序，希尔排序，快速排序，堆排序归并排序等7种排序算法，下面将分别进行讲解： 1.冒泡排序 所谓冒泡排序法，就是对一组数字进行从大到小或者从小到大排序的一种算...
递归算法时间复杂度分析
时间复杂度： 一般情况下，算法中基本操作重复的次数就是问题规模n的某个函数f（n），进而分析f（n）随n的变化情况并确定t（n）的数量级。这里用‘o’来表示数量级，给出算法时间复杂度。 t（n）=o（f（n））； 它表示随问题规模n的...