基础算法之动态规划

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。
把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,属于过程优化的范畴,在现在的很多程序处理过程中广泛运用,直接正题吧,概念性的可以百度更深入了解,
今天我先来点简单的例子:

来一道题:找出给定字符串中的最长回文串;
回文串:即对称串,比如aaabbb、adda、a,除了字符本身外,回文串一定是偶数个字符,是基于中心对称的.
我们试试最常规的写法(暴力):
遍历每一个起始位置,再遍历每一个结束位置,再遍历每一个起始到结束位置的字符判断是不是回文,balabalalalalalalalla….时间复杂度O(n^3)
还是放弃吧…

下面看看动态规划的处理方式:
dp[i][j]=0表示子串[i,j]不是回文串。dp[i][j]=1表示子串[i,j]是回文串
则:
状态转移方程:dp[i,j]{=dp[i+1,j-1],if(s[i]==s[j]) || =0,if(s[i]!=s[j])}

我们把当前状态转移到了他的子集,这样就好处理了许多;

public static void main(String[] args) {
String s = “aaabbbbbbaaasss”;
if(s.length() <=1) //字符长度小于等于1,直接输出
System.out.println(s);
int maxLength = 0;
int start = 0;//记录最长回文串的开始位置
int[][] dp = new int[s.length()][s.length()];//二维数组,用于状态转移
for (int i = 0; i < s.length(); i++) {//初始化能保证[i,i]第i个位置到第i个位置即单个字符一定是回文串,如果[i,i+1]也等的话也一并初始化
dp[i][i] = 1;
if(i<s.length()-1 && s.charAt(i)==s.charAt(i+1))
{
dp[i][i+1]=1;
start=i;
maxLength=2;
}
}
for (int l = 3; l <= s.length(); l++) {//遍历所有的子串长度
for (int i = 0; i <= s.length()-l; i++) {//遍历所有长度的起始位置
int j = i + l – 1;//那么计算出子串的结束位置就该是它了
if(dp[i+1][j-1] == 1 && s.charAt(i)==s.charAt(j)){//对每个子串向前回溯,如果当前的起止位置字符相等并且向里缩进的子串是回文串,那么当前的起止串一定也是回文串
dp[i][j]=1;//当前的起止串标记为回文串
maxLength=l;//记录最大长度(如果有更长的,之前的就会被覆盖)
start=i;//记录每个长度的起始位置
}
}
}
if(maxLength >= 2)
System.out.println(s.substring(start,maxLength));
else
System.out.println(“没有最长回文!!!”);
}
动态规划处理这个问题的时间复杂度O(n^2),比之前快了很多,但是这个例子不够形象,我们从最简单的地方入手:

我们看一个数塔问题:TIM图片20170913144601

图片不清晰,再描述下问题:要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
状态转移方程dp [i] = max(dp[左孩子] , dp[右孩子]) + dp[i]
public static void main(String[] args) {
int[][] dp= {//初始化数塔
{9,0,0,0,0},
{12,15,0,0,0},
{10,6,8,0,0},
{2,18,9,5,0},
{19,7,10,4,16}
};
for(int i = 4; i > 0; i–) {
for (int j = 0; j < i; j++) {
dp[i – 1][j] += dp[i][j] > dp[i][j + 1] ? dp[i][j] : dp[i][j + 1];//如果左边比右边大,那么只加左孩子,反之加右孩子
//每次加完之后的值都会赋给上一层,直到dp[0][0],这样总能保证和最大
}
}
System.out.println(dp[0][0]);
}

暂时就这些吧,下次再补充~~~

互联网人应该了解的一个数据结构Bloom Filter

先贴上已经写得非常好的一篇文章:http://blog.csdn.net/jiaomeng/article/details/1495500

Bloom Filter是一个用于标记和查找标记的一种数据结构,因为设计精妙,也有人认为它是一种算法。

它设计的大体思路是通过hash值来对一个二进制位的存储“条”上打上标记,同样判断是否已经存在时,只需要通过位运算进行匹配判断便可。

这里存在三种误判:1是因为存储空间的限制(根据使用的具体业务量计算或大致判断得出)导致可能存在多个hash值映射到了同一个(或一批:一批是指采用了拆分的方式将一个hash映射到了多个点)位置,导致误判;2是上一点中的拆分式的映射,导致位置标记覆盖速度加快,就可能存在某个hash映射到的几个点刚好是其他多个不同hash标记的点的组合;3是因为hash碰撞而导致两个字符串在Bloom Filter中存在相互误判。

这三种误判是不能完全避免的,只能是优化它,所以提取这三点中的关键部分-hash值,对其进行优化。于是,我们需要根据多套hash算法,计算出多个hash,将这些hash值都做标记,验证是否存在时,则需要所有的hash值都通过。通过这种方式,我们能很大幅度的减小误判。

因为Bloom Filter是存在误判的,所以我们只能使用于一些性能要求较高,但对准确率要求不高的场景。例如,我们可以做一个随机抽题的功能,就可以用它来标记那些已经抽过的题。