存档

文章标签 ‘二分查找’

二分查找,你真的会吗?

2012年10月6日 19 条评论

---

面试常让写二分查找或其扩展的程序,以前总觉得很简单,但是真动手写起来,细节很多,容易出错的地方也很多,真是秒杀眼高手低的利器,本节就二分查找以及相关扩展程序都实现一下,同时将可能出错的地方以及需要注意的细节也一并说明,水平有限,欢迎补充。

内容如下:

1)二分查找元素key的下标,如无 return -1

2)二分查找返回key(可能有重复)第一次出现的下标,如无return -1

3)二分查找返回key(可能有重复)最后一次出现的下标,如无return -1

4)二分查找返回刚好小于key的元素下标,如无return -1

5)二分查找返回刚好大于key的元素下标,如无return -1

注:以上所有问题可能出错的地方以及需要注意的细节说明在代码注释中。

直接上代码:

阅读全文...

最长递增子序列(LIS)

2012年6月17日 16 条评论

---

最长递增子序列又叫做最长上升子序列;子序列,正如LCS一样,元素不一定要求连续。本节讨论实现三种常见方法,主要是练手。

题:求一个一维数组arr[i]中的最长递增子序列的长度,如在序列1,-1,2,-3,4,-5,6,-7中,最长递增子序列长度为4,可以是1,2,4,6,也可以是-1,2,4,6。

方法一:DP

像LCS一样,从后向前分析,很容易想到,第i个元素之前的最长递增子序列的长度要么是1(单独成一个序列),要么就是第i-1个元素之前的最长递增子序列加1,可以有状态方程:

LIS[i] = max{1,LIS[k]+1},其中,对于任意的k<=i-1,arr[i] > arr[k],这样arr[i]才能在arr[k]的基础上构成一个新的递增子序列。

代码如下:在计算好LIS长度之后,output函数递归输出其中的一个最长递增子序列。

阅读全文...