经典数据结构面试题（含答案）

Programming Pearls一书。 在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推，我们就可以得到下面这个算法： int max_sub(int a[],int size) {

int i,j,v,max=a[0]; for(i=0;i

v=0;

for(j=i;j

v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1] if(v>max) max=v; } }

return max; }

那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现： int max_sub2(int a[], int size) {

int i,max=0,temp_sum=0; for(i=0;i

temp_sum+=a[i]; if(temp_sum>max) max=temp_sum; else if(temp_sum<0) temp_sum=0; }

return max; }

6,按单词反转字符串 并不是简单的字符串反转，而是按给定字符串里的单词将字符串倒转过来，就是说字符串里面的单词还是保持原来的顺序，这里的每个单词用空格分开。例如：

Here is www.fishksy.com.cn

经过反转后变为：

www.fishksy.com.cn is Here

如果只是简单的将所有字符串翻转的话，可以遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环。其实按照单词反转的话可以在第一遍遍历的基础上，再遍历一遍字符串，对每一个单词再反转一次。这样每个单词又恢复了原来的顺序。

char* reverse_word(const char* str) {

int len = strlen(str);

char* restr = new char[len+1]; strcpy(restr,str); int i,j;

for(i=0,j=len-1;i

char temp=restr[i]; restr[i]=restr[j]; restr[j]=temp; }

int k=0;

while(k

i=j=k;

while(restr[j]!=' ' && restr[j]!='' ) j++; k=j+1; j--;

for(;i

char temp=restr[i]; restr[i]=restr[j]; restr[j]=temp; } }

return restr; }

如果考虑空间和时间的优化的话，当然可以将上面代码里两个字符串交换部分改为异或实现。

例如将

char temp=restr[i]; restr[i]=restr[j]; restr[j]=temp; 改为

restr[i]^=restr[j];

restr[j]^=restr[i]; restr[i]^=restr[j];

7,字符串反转 我没有记错的话是一道MSN的笔试题，网上无意中看到的，拿来做了一下。题目是这样的，给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串的顺序不变。例如：

输入：第一个字符串: \

子串: \

输出： \

一般的方法是先扫描一边第一个字符串，然后用stack把它反转，同时记录下子串出现的位置。然后再扫描一遍把记录下来的子串再用stack反转。我用的方法是用一遍扫描数组的方法。扫描中如果发现子串，就将子串倒过来压入堆栈。

最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。源代码如下： #include #include #include using namespace std;

//reverse the string 's1' except the substring 'token'. const char* reverse(const char* s1, const char* token) {

assert(s1 && token); stack stack1;

const char* ptoken = token, *head = s1, *rear = s1; while (*head != '') {

while(*head!= '' && *ptoken == *head) {

ptoken++; head++; }

if(*ptoken == '')//contain the token {

const char* p;

for(p=head-1;p>=rear;p--) stack1.push(*p);

ptoken = token; rear = head; } else {

stack1.push(*rear); head=++rear; ptoken = token; } }

char * return_v = new char[strlen(s1)+1]; int i=0;

while(!stack1.empty()) {

return_v[i++] = stack1.top(); stack1.pop(); }

return_v[i]=''; return return_v; }

int main(int argc, char* argv[])

{cout<<\\

cout<

return 0; }

8, 删除数组中重复的数字 问题：一个动态长度可变的数字序列，以数字0为结束标志，要求将重复的数字用一个数字代替，例如：

将数组 1,1,1,2,2,2,2,2,7,7,1,5,5,5,0 转变成1,2,7,1,5,0 问题比较简单，要注意的是这个数组是动态的。所以避免麻烦我还是用了STL的vector。 #include #include using namespace std;

//remove the duplicated numbers in an intger array, the array was end with 0; //e.g. 1,1,1,2,2,5,4,4,4,4,1,0 --->1,2,5,4,1,0

void static remove_duplicated(int a[], vector& _st) {

_st.push_back(a[0]);

for(int i=1;_st[_st.size()-1]!=0;i++) {

if(a[i-1]!=a[i])

_st.push_back(a[i]); } }

当然如果可以改变原来的数组的话，可以不用STL，仅需要指针操作就可以了。下面这个程序将修改原来数组的内容。 void static remove_duplicated2(int a[])