【转】经典面试题

北极的。鱼

浏览: 159023 次
性别:
来自: 上海

最近访客更多访客>>

collen7788

zzc125

tianxizhong

kelly_zsl

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

数据结构

转自：http://blog.csdn.net/fanzitao/article/details/7930801

字符串转化为数字

注意：处理正负号，可以处理正负号，字母打头，-+打头，以及其中字符串中间含有非法字符的情况。
bool change(char *str,int &num)
{
     num = 0;
     int mul = 1;
     if(*str=='-'||*str=='+')
     {
          if(*str=='-')
              mul = -1;
          str++;
          if(*str=='\0')//防止出现”-“,”+”的情况
              return false;
     }
     while(*str!='\0'&&*str>='0'&&*str<='9')//对照0~9在ASCII中的编号
     {
          num = num*10+*str-'0';
          str++;
     }
     if(*str=='\0')
     {
          num = mul*num;
          return true;
     }
     else 
         return false;
}

说白了，就是取出字符串中每个字符，然后对比其在ASCII中的编号，如果是落在0~9之间，就是对应的数字。然后在开始的时候，要判断下正负。

有一个整数数组，请求出两两之差绝对值的最小值

#include<iostream>
#include<algorithm>
using namespace std;
int a[] = {-3,4,2,7,25,0,8,-2};
int main()
{
    int len =sizeof(a)/sizeof(int);
    //sort(a,a+len);//排序以后就不是原数组了
    int min =50;
    for(int i=len-1; i>0;i--)
    {
        min = (abs(a[i]-a[i-1])>min)?min:abs(a[i]-a[i-1]);
    }
    cout<<"min "<<min<<endl;
    getchar();
    return 0;
}

全排列

首先考虑bac和cba这二个字符串是如何得出的。显然这二个都是abc中的 a 与后面两字符交换得到的。然后可以将abc的第二个字符和第三个字符交换得到acb。同理可以根据bac和cba来得bca和cab。

因此可以知道 全排列就是从第一个数字起每个数分别与它后面的数字交换，也可以得出这种解法每次得到的结果都是正确结果，所以复杂度为 O(n!)。找到这个规律后，递归的代码就很容易写出来了：

static void Main(string[] args)
{
    char[] s = "abc".ToCharArray();
    AllRange(s, 0, 3);
    Console.WriteLine("\n\n总数为{0}", resultcount);

    Console.ReadLine();
}

static int resultcount = 0;
static void Swap(ref char a, ref char b)
{
    char temp = a;
    a = b;
    b = temp;
}
//length 为数组长度
static void AllRange(char[] list, int start, int length)
{
    if (start == length)
    {
        for (int i = 0; i < length; i++)
        {
            Console.Write("{0}", list[i]);
        }
        Console.WriteLine();
        resultcount++;
    }
    else
    {
        for (int i = start; i < length; i++)//从第一个数开始，每个数都和后面的数交换
        {
            Swap(ref list[start], ref list[i]);
            AllRange(list, start + 1, length);
            Swap(ref list[start], ref list[i]);
        }
    }
}

链表相交问题

转自：http://blog.csdn.net/hackbuteer1/article/details/7583102

红色虚线框中的节点为待求节点。

首先使用第2个题目中的快、慢指针来判断链表是否存在环，若不存在结束。
若链表中存在环，我们从链表头、与两个指针的相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇的第一个点为环的入口点。
代码如下：

// 找到环的第一个入口点  
LinkList* FindLoopPort(LinkList *head)  
{  
    LinkList *pslow = head;  
    LinkList *pfast = head;  
    while(pfast != NULL && pfast->next != NULL)  
    {  
        pslow = pslow->next;        // 每次前进一步  
        pfast = pfast->next->next;  // 每次前进二步  
        if(pslow == pfast)          // 两个指针相遇，说明存在环  
            break;  
    }  
    if(pfast == NULL || pfast->next == NULL)    // 不存在环  
        return NULL;  
    pslow = head;  
    while(pslow != pfast)  
    {  
        pslow = pslow->next;        // 每次前进一步  
        pfast = pfast->next;        // 每次前进一步  
    }  
    return pslow;       // 返回环的入口点  
}

分析：当pfast若与pslow相遇时，pslow肯定没有走遍历完链表，而pfast已经在环内循环了n圈(1<=n)。假设pslow走了s步，则pfast走了2s步（pfast步数还等于s 加上在环上多转的n圈），设环长为r，则：

2s = s + nr 　　s= nr
设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。　　

a+x=s , a+x+nr = 2s 则 a + x = nr 　则　a + x = (n – 1)r +r = (n-1)r + L - a 　　a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。
小结：链表是数据结构中最基本的，也是面试中常考的，与链表相关的题目也变化多端，只要基础扎实，多积累一些处理类似问题的技巧，面试时便能应对自如。

已知先序或后序已经中序，构造二叉树

转自：http://www.cnblogs.com/bmrs/archive/2010/08/19/slovetree.html

这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的，证明略。

一、已知二叉树的前序序列和中序序列，求解树。

1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

二、已知二叉树的后序序列和中序序列，求解树。

1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。

3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

举例说明：根据已知求解二叉树

中序序列 HLDBEKAFCG
后序序列 LHDKEBFGCA

1、在后序序列LHDKEBFGCA中最后出现的元素为A，HLDBEK|A|FCG
2、在后序序列LHDKEB中最后出现的元素为B，HLD|B|EK|A|FCG
3、在后序序列LHD中最后出现的元素为D，HL|D|B|EK|A|FCG
4、在后序序列LH中最后出现的元素为H，H|L|D|B|EK|A|FCG
5、在后序序列KE中最后出现的元素为E，H|L|D|B|E|K|A|FCG
5、在后序序列FGC中最后出现的元素为C，H|L|D|B|E|K|A|F|C|G
6、所有元素都已经定位，二叉树求解完成。

A
              /     \
             B       C
            / \     /  \
           D  E     F   G
          /    \
         H      K                    
          \                         
           L

代码如下：

Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1 /*
    功能: 1.利用树的前序和中序序列创建树
          2.利用树的后序和中序序列创建树
*/
#include <iostream>
#include <cstring>
using namespace std;

char pre[50] = "ABDHLEKCFG";        //前序序列
char mid[50] = "HLDBEKAFCG";        //中序序列
char post[50] = "LHDKEBFGCA";        //后序序列

typedef struct _Node
{
    char v;
    struct _Node *left;
    struct _Node *right;
}Node, *PNode;

void PostTravelTree(PNode pn);        //树的后序递归遍历
void PreTravelTree(PNode pn);        //树的前序递归遍历
void PreMidCreateTree(PNode &pn, int i, int j, int len);        //利用前序中序序列创建树
void PostMidCreateTree(PNode &pn, int i, int j, int len);        //利用后序中序序列创建树
int Position(char c);                //确定c在中序序列mid中的下标,假设树的各个节点的值各不相同


int main() 
{ 
    PNode root1 = NULL, root2= NULL;

    PreMidCreateTree(root1, 0, 0, strlen(mid));
    PostTravelTree(root1); cout<<endl;    
    PostMidCreateTree(root2, strlen(post)-1, 0, strlen(mid));
    PreTravelTree(root2); cout<<endl;    

    return 0;
}


int Position(char c)
{
    return strchr(mid,c)-mid;
}


/*  利用前序中序序列创建树,参考了http://hi.baidu.com/sulipol/blog/item/f01a20011dcce31a738b6524.html
 *的实现,代码十分简洁,竟然只有短短的"令人发指"的8行,递归实在太彪悍了!!!!!!!!!!!!!!!!!!!!!
 *        i: 子树的前序序列字符串的首字符在pre[]中的下标
 *        j: 子树的中序序列字符串的首字符在mid[]中的下标
 *      len: 子树的字符串序列的长度
 */
void PreMidCreateTree(PNode &pn, int i, int j, int len)
{
    if(len <= 0)
        return;
    
    pn = new Node;
    pn->v = pre[i];
    int m = Position(pre[i]);//先序首字符在中序中的位置
    PreMidCreateTree(pn->left, i+1, j, m-j);//i+1为当前结点在先序中的位置，j为中序的开始结点位置，m-j为中序里左子树字符串长度
    PreMidCreateTree(pn->right, i+(m-j)+1, m+1, len-1-(m-j));//len-1-(m-j)为右子树字符串长度
}


/*  利用后序中序序列创建树
 *        i: 子树的后序序列字符串的尾字符在post[]中的下标
 *        j: 子树的中序序列字符串的首字符在mid[]中的下标
 *      len: 子树的字符串序列的长度
 */
void PostMidCreateTree(PNode &pn, int i, int j, int len)
{
    if(len <= 0)
        return;

    pn = new Node;
    pn->v = post[i];
    int m = Position(post[i]);//后序首字符在中序中的位置
    PostMidCreateTree(pn->left, i-1-(len-1-(m-j)), j, m-j);//注意参数:m-j左子树的长度,len-1-(m-j)右子树的长度
    PostMidCreateTree(pn->right, i-1, m+1, len-1-(m-j));
}


void PostTravelTree(PNode pn)        //后序递归遍历
{
    if(pn)
    {
        PostTravelTree(pn->left);    
        PostTravelTree(pn->right);
        cout<<pn->v<<" ";
    }
}


void PreTravelTree(PNode pn)        //前序递归遍历
{
    if(pn)
    {
        cout<<pn->v<<" ";
        PreTravelTree(pn->left);    
        PreTravelTree(pn->right);
    }
}