存档

文章标签 ‘编程之美’

二分查找,你真的会吗?

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函数递归输出其中的一个最长递增子序列。

阅读全文...

字符串相似度(编辑距离)

2012年6月13日 4 条评论

---

个人认为,大部分情况下,DP寻找子问题还是“从后向前”比较直观一些,像这道题目,个人觉得《编程之美》对它的分析就有些别扭,它“从前向后”寻求的子问题使得状态转移矩阵的初始化变得不太方便,不过“从后向前”分析和从前向后效果和原理都是一样的,本节通过三种实现方式来加深理解。

定义字符串的相似度有很多种度量,像前面说的最长公共子序列就是其中的一种,本节所说的“编辑距离”也算是一种,简单来说,编辑距离就是将两个字符串变成相同字符串所需要的最小操作次数。所需的操作可能有:

  1. 修改一个字符(如把“a”替换为“b”)
  2. 增加一个字符(如把“abdd”变为“aebdd”)
  3. 删除一个字符(如把“travelling”变为“traveling”)

例如,对于“abcdefg”和“abcdef”两个字符串来讲,可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的“编辑距离”。如何计算两个字符串的“编辑距离”?

鉴于DP自底向上求解子问题的性质,我们还是对字符串从后向前分析,这样寻找编辑距离的子问题比较直观,而且分解的子问题使得递归做备忘录变得容易理解,也使得自底向上实现时对状态转移矩阵的初始化更为简便易懂。

寻找子问题时,我们完全可以像分析最长公共子序列那样分析这个问题,我觉得它们是灰常相似的,都是“从后向前”看,假设有两个串X=abcdaex,Y=fdfax,它们的最后一个字符是相同的,只要计算X[1,…,6]=abcdae和Y[1,…,4]=fdfa的距离就可以了;但是如果两个串的最后一个字符不相同,那么就可以进行如下的操作来达到目的(xlen和ylen是X串和Y串的长度):

阅读全文...

交换两段连续(不连续)内存

2011年9月4日 没有评论

在《编程珠玑,第二版》和《编程之美》中都有关于交换两段连续的内存块的题目,而且非常经典,交换两段连续内存块的问题又可以延伸到交换两段不连续内存块的问题,无论是哪种情况都需要一个基本操作:反转内存块

反转内存时,比较简单,可以两个指针同时走,也可以一个指针,随意,实现如下:

01 // reverse the memory block
02 // goal: |12345| -> |54321|
03 void * reverseMemory(void *pMemory, const size_t memSize)
04 {
05     if(NULL == pMemory) return pMemory;
06     if(memSize < 2)        return pMemory;
07
08     char * beg = static_cast<char *>(pMemory);
09     char * end = beg + memSize -1;
10     for(; beg < end; ++beg, --end)
11     {
12         char memTmp = *beg;
13         *beg = *end;
14         *end = memTmp;
15     }
16     return pMemory;
17 }

其中,函数的两个形参分别为要反转内存的起始地址和内存块的大小。返回值类型为void*,指向反转内存块的起始地址。

实现了反转内存块这一基本操作后,我们就可以用它来交换两段连续的内存,从而解决类似“数组循环移位”的问题。具体算法在编程珠玑和编程之美中都有详细介绍,这里简单说一下:

假设有连续的内存块M和N形如:|----M---|--------N---------|

  1. 首先反转内存块M:M’=reverse(M)
  2. 反转内存块N:N’=reverse(N)
  3. 对整个内存块M’ N’进行反转:(M’N’)’ = NM


阅读全文...