`

数据结构面试大全

阅读更多
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;
}
分享到:
评论

相关推荐

    数据结构面试大全 面试 算法

    本资料集“数据结构面试大全”显然是为准备面试者提供了一个全面的资源库,包含了各种知名企业的真实面试题目,以及数据结构的基础知识。 1. **数组**:是最基本的数据结构,提供了随机访问元素的能力。面试中可能...

    数据结构面试大全—数据结构面试一网打尽

    数据结构面试大全旨在帮助求职者全面准备这方面的知识,确保在面试中能够应对自如。 1. **数组**:数组是最基本的数据结构,它允许在固定位置存储相同类型的数据。面试中可能会问到数组的特性,如直接访问、连续...

    java和数据结构面试大全

    "java和数据结构面试大全"这个资源显然旨在帮助求职者全面准备这一领域的面试问题。以下是一些关键的知识点,涵盖了这两个主题: 1. **数据结构**: - **数组**:是最基础的数据结构,提供了固定大小且通过索引...

    数据结构面试大全.rar

    在面试中,数据结构是衡量程序员能力的重要标准,因为它们直接影响到程序的性能、可读性和可维护性。对于任何从事编程工作的人来说,掌握数据结构的基本原理和应用是至关重要的。 首先,我们来看看一些常见的数据...

    数据结构面试大全.pdf

    数据结构面试大全.pdf

    Java常见数据结构面试题(带答案)

    "Java常见数据结构面试题(带答案)" 以下是对Java常见数据结构面试题的知识点总结: 栈和队列 * 栈和队列的共同特点是只允许在端点处插入和删除元素。 * 栈通常采用的两种存储结构是线性存储结构和链表存储结构...

    数据结构面试宝典数据结构面试宝典

    "数据结构面试宝典"旨在帮助求职者掌握这一领域的关键知识,提高面试的成功率。 在数据结构中,常见的类型包括数组、链表、栈、队列、树、图、哈希表等。每种数据结构都有其独特的特点和适用场景。 1. **数组**:...

    数据结构面试题目大全

    本资源“数据结构面试题目大全”旨在帮助求职者全面准备与数据结构相关的笔试和面试问题,确保他们在面对这类挑战时能够游刃有余。 数据结构主要涉及如何在计算机中有效地存储和组织数据,以便进行高效的访问和修改...

    数据结构面试题

    面试中常见的数据结构题目包括但不限于:实现特定数据结构(如自平衡树)、分析时间复杂度和空间复杂度、解决实际问题(如使用数据结构优化算法)。此外,面试官可能还会询问如何使用数据结构优化已有的解决方案,...

    各大公司数据结构面试题集锦

    本资料“各大公司数据结构面试题集锦”汇聚了多个知名公司的面试题,涵盖了C和C++语言,旨在帮助求职者充分准备面试。 首先,我们来了解一下基础的数据结构类型: 1. 数组:是最基本的数据结构,它将元素存储在...

    Java 数据结构 面试用

    在准备Java面试的过程中,数据结构是必不可少的知识领域。数据结构是计算机存储、组织数据的方式,它直接影响到程序的效率和性能。本资料包主要聚焦于Java实现的数据结构,旨在帮助面试者深入理解并掌握这些核心概念...

    数据结构+C++面试题

    数据结构与C++在面试中是两个至关重要的领域,它们是计算机科学的基础,也是软件工程师必备的技能。本文将深入探讨这两个主题中的关键知识点,并结合面试题的形式进行讲解。 首先,我们来关注数据结构。数据结构是...

    刀疤鸭之数据结构面试题

    在给定的文件中,“刀疤鸭之数据结构面试题”涉及了大量的数据结构相关的问题,这些问题覆盖了多种数据结构类型和算法,包括树、图、数组、链表和栈等。 1. 二元查找树转换为双向链表: 二元查找树(BST)是一种...

    典型数据结构面试题

    ### 数据结构面试题详解 #### 1. 单链表插入操作 在单链表中,在节点`p`前插入节点`s`(值为`e`)的操作涉及到指针的重新指向。正确的步骤是先找到`p`节点的前一个节点`q`,然后更新指针,使得`q-&gt;next`指向`s`,再...

    数据结构面试常用经典问题

    这里我们聚焦于“数据结构面试常用经典问题”,通过分析《数据结构与算法经典问题解析:Java语言描述(原书第2版)》这本书中的内容,我们可以深入探讨几个关键知识点。 1. **数组**:数组是最基础的数据结构,它...

    c 数据结构 面试题 算法 面试题

    本资源包聚焦于C语言实现的数据结构面试题,旨在帮助应聘者准备相关面试,提升对数据结构和算法的理解。 一、链表 链表是一种线性数据结构,与数组不同,它在内存中不是连续存储的。每个节点包含数据和指向下一个...

    阿里谷歌数据结构笔试面试精讲PPT及数据结构参考书

    本资料包聚焦于“阿里”和“谷歌”这两个全球知名科技公司的数据结构笔试和面试题目,旨在帮助求职者准备相关面试,提升数据结构理解和应用能力。 首先,让我们深入探讨《数据结构与算法分析C++描述第三版中文.pdf...

Global site tag (gtag.js) - Google Analytics