数据结构面试大全(一) - [算法]

版权声明 ：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://lzhshen.blogbus.com/logs/20333778.html

1. 判断链表是否存在环型链表

问题：判断一个链表是否存在环，例如下面这个链表 就存在一个环：
例如 N1->N2->N3->N4->N5->N2 就是一个有环的链表，环的开始结点是 N5

这里有一个比较简单的解法。设置两个指针 p1 ， p2 。每次循环 p1 向前走一步， p2 向前走两步。直到 p2 碰到 NULL 指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。

struct link

{

   int data;

    link* next;

};

bool IsLoop(link* head)

{

    link* p1=head, *p2 = head;

     if (head ==NULL || head->next ==NULL) 

     {

          return false;

     }

    do{

        p1= p1->next;

        p2 = p2->next->next;

    } while(p2 && p2->next && p1!=p2);     

     if(p1 == p2)

          return true;

     else

          return false;

}

2, 链表反转

单向链表的反转是一个经常 被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为 5->4->3->2->1 。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的 下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：

struct linka {

     int data;

     linka* next;

};

void reverse(linka*& head)

{

     if(head ==NULL)

          return;

     linka*pre, *cur, *ne;

     pre=head;

     cur=head->next;

     while(cur)

     {

          ne = cur->next;

          cur->next = pre;

          pre = cur;

          cur = ne;

     }

     head->next = NULL;

     head = pre;

}

还有一种利用递归的方法。 这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所 以必须将函数的返回的节点的 next 域置为 NULL 。因为要改变 head 指针，所以我用了引用。算法的源代码如下：

linka* reverse(linka* p,linka*& head)

{

     if(p == NULL || p->next == NULL)

     {

          head=p;

          return p;

     }

     else

     {

          linka* tmp = reverse(p->next,head);

          tmp->next = p;

          return p;

     }

}

3, 判断两个数组中是否存在相同的数字

给定两个排好序的数组，怎 样高效得判断这两个数组中存在相同的数字？
这个问题首先想到的是一个 O(nlogn) 的 算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行 binary search 。用 C++ 实现代码如下：

bool findcommon(int a[],int size1,int b[],int size2)

{

     int i;

     for(i=0;i<size1;i++)

     {

          int start=0,end=size2-1,mid;

          while(start<=end)

          {

               mid=(start+end)/2;

               if(a[i]==b[mid])

                    return true;

               else if (a[i]<b[mid])

                    end=mid-1;

               else

                    start=mid+1;

          }

     }

     return false;

}

后来发现有一个 O(n) 算法。因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进 。推进的规则是比较两个 数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数 字，说明数组中没有相同的数字。

bool findcommon2(int a[], int size1, int b[], int size2)

{

     int i=0,j=0;

     while(i<size1 && j<size2)

     {

          if(a[i]==b[j])

               return true;

          if(a[i]>b[j])

               j++;

          if(a[i]<b[j])

               i++;

     }

     return false;

}

4, 最大子序列

问题：
给定一整数序列 A1 ， A2 ， ... An （可能有负数），求 A1~An 的一个子序列 Ai~Aj ，使得 Ai 到 Aj 的和最大
例如：
整数序列 -2, 11, -4, 13, -5, 2, -5, -3, 12, -9 的最 大子序列的和为 21 。
对于这个问题，最简单也是最容易想到 的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到 O(n^3) 。显然这种方法不是最优的，下面给出一个算法复杂度为 O(n) 的线性算法实现，算法的来源 于 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<size;i++)

     {

          v=0;

          for(j=i;j<size;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<size;i++)

     {

          temp_sum+=a[i];

          if(temp_sum>max)

               max=temp_sum;

          else if(temp_sum<0)

               temp_sum=0;

     }

     return max;

}

在这一遍扫描数组当中，从 左到右记录当前子序列的和 temp_sum ，若这个和不断增加，那么最大子序列的和 max 也不断增加 ( 不断更新 max) 。如果往前扫描中遇到负数， 那么当前子序列的和将会减小。此时 temp_sum 将会小于 max ，当然 max 也就不更新。如果 temp_sum 降到 0 时，说明前面已经扫描的那一段就可 以抛弃了，这时将 temp_sum 置为 0 。然后， temp_sum 将从后面开始将这个子段进行分析，若有比当前 max 大的子段，继 续更新 max 。这样一趟扫描结果也就出来了。

5, 找出单向链表的中间结点

这道题和解 判断链表是否存在环 ，我用的是非常类似的方法，只不过结束循环的条件和函数返回值不一样罢了。设置两个指针 p1 ， p2 。每次循环 p1 向前走一步， p2 向前走两步。当 p2 到达链表的末尾时， p1 指向的时链表的 中间。

link* mid(link* head)

{

       link* p1,*p2;

       p1=p2=head;

       if(head==NULL || head->next==NULL)

              return head;

       do {

              p1=p1->next;

              p2=p2->next->next;

       } while(p2 && p2->next);

       return p1;

}

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<j;i++,j--)

     {

          char temp=restr[i];

          restr[i]=restr[j];

          restr[j]=temp;

     }

     int k=0;

     while(k<len)

     {

          i=j=k;

          while(restr[j]!=' ' && restr[j]!='\0' )

               j++;

          k=j+1;

          j--;

          for(;i<j;i++,j--)

          {

               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 的笔试题，网上无意中看到的，拿来做了一下。题目是这样的，给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串 的顺序不变。例如：
输入： 第一个字符串 : "This is fishsky 's Chinese site: http://www.fishsky.com.cn/cn"
子串 : "fishsky"
输出： "nc/nc.moc.fishsky.www//:ptth :etis esenihC s'fishsky si sihT"
一般的方法是先扫描一边第一个字符串，然后用 stack 把它反转，同时记录下子串出现的位置。然后再扫描一遍把记录下来的子串再用 stack 反转。我用的方法是用一遍扫描数组的方法。扫描中如果发现子串，就将子串倒过来压入堆栈。
最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。源代码如下：

#include <iostream>

#include <cassert>

#include <stack>

using namespace std;

//reverse the string 's1' except the substring 'token'.

const char* reverse(const char* s1, const char* token)

{

       assert(s1 && token);

       stack<char> stack1;

       const char* ptoken = token, *head = s1, *rear = s1;

       while (*head != '\0')

       {

              while(*head!= '\0' && *ptoken == *head)

              {

                 ptoken++;

                 head++;

              }

              if(*ptoken == '\0')//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]='\0';

       return return_v;

}

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

{

       cout<<"This is 
fishsky
 's Chinese site: http://www.
fishsky
.com.cn/cn\n";

       cout<<reverse("This is 
fishsky
's Chinese site: http://www.
 fishsky
.com.cn/cn","
 fishsky
 ");

       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 <iostream>

#include <vector>

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<int>& _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[])

{

       if(a[0]==0 || a==NULL)

              return;

       int insert=1,current=1;

       while(a[current]!=0)

       {

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

              {

                 a[insert]=a[current];

                 insert++;

                 current++;

              }

              else

                 current++;

       }

       a[insert]=0;

}

9, 如何判断一棵二叉树是否是平衡二叉树

问题：判断一个二叉排序 树是否是平衡二叉树
解决方案：
根据平衡二叉树的定义，如果 任意节点的左右子树的深度相差不超过 1 ，那这棵树就是平衡二叉树。
首先编写 一个计算二叉树深度的函数，利用递归实现。

template<typename T>

static int Depth(BSTreeNode<T>* pbs)

{

       if (pbs==NULL)

              return 0;

       else

       {

              int ld = Depth(pbs->left);

              int rd = Depth(pbs->right);

              return 1 + (ld >rd ? ld : rd);

       }

}

下面是利用递归判断左右 子树的深度是否相差 1 来判断是否是平衡二叉树的函数：

template<typename T>

static bool isBalance(BSTreeNode<T>* pbs)

{

       if (pbs==NULL) 

              return true;

       int dis = Depth(pbs->left) - Depth(pbs->right);

       if (dis>1 || dis<-1 )

              return false;

       else

              return isBalance(pbs->left) && isBalance(pbs->right);

}