面试题选（2）

算法

---

1.判断两个链表是否相交(未完成）

题目： 给出两个单链表的头指针，判断两个链表是否相交，并求出第一个相交节点。
分析： 假设两个链表长度为N和M，暴力解法是两链表节点一一比对，时间复杂度$\Theta(N*M)$，当N和M很大时，则需要亚二次解法。注意到这样一个事实：如果两链表有相交，那么从第一个相交节点之后，两链表完全相同。设链表相交部分长度为K，则首先遍历两链表得到各自长度N和M，假设N>=M,则第一个相交节点一定在后M个节点中。且第一个相交节点距尾节点距离也一样长，所以将长链表指针先指到第（N-M）个节点（首节点设为0节点）与短链表头指针对齐，然后两链表指针可同时走一步并比较，时间复杂度为$\Theta(N+M)$。
扩展：当链表有环怎么办？

2.判断整数序列是否为二叉树的后序遍历

题目： 输入一个整数序列，判断其是否为某二叉树的后序遍历结果（此后续遍历可能为树的某一个子树）。
分析： 利用一个事实：根节点一定在后续遍历的最后，且根节点左子树在前部分，右子树紧跟左子树在后部分，最后一个是根节点。所以给定一个序列，要判断是否为以root为根节点的后序遍历，经两步：1.根据后序遍历最后元素，在二叉树中找到此后序遍历的根节点r，如果不在二叉树中，则返回false；2.若找到根节点r，则可将后序遍历序列分为三部分：r的左子树，r的右子树，r。左子树与右子树的分界点即r的左儿子。3.对左子树和右子树递归判断。

/*
Filename: IsLRD.cpp
Function: 
bool IsLRD(IsLRD( int A[], int length, Node* root )
输入一个整数序列，判断其是否为某二叉树的
后序遍历结果（此后续遍历可能为树的某一个子树）
Details: 递归实现
*/
#include <iostream>
using namespace std;
struct Node
{
    int m_nElement;
    Node* m_pLeft;
    Node* m_pRight;
};
/**********************主要函数************************/
bool IsLRD( int A[], int length, Node* root );
bool IsLRD_Core( int A[], int length, Node* pTree );
/*****************************************************/
/*
    在以root为根节点的二叉树中，找到值为element的节点
*/
Node* FindInTree( Node* root, int element );
/*
    在长度为length的数组A中找到值element的位置（0起点）
*/
int FindInArray( int A[], int length, int element );
/*
    创建一棵树，根节点的左子树只有左儿子，右子树只有右儿子
                *
              /   \
             *     *
            /       \
           *         *
*/
Node* create_tree( int n );
/*
    创建一个值为i的节点
*/
Node* create_node( int i );
int main()
{
    int A[] = { 5,3,1,6,4,2,0};
    int length = sizeof(A)/sizeof(int);
    Node *root;
    root = create_tree( 7 );
    if( IsLRD( A, length, root ) )
        cout<<"right"<<endl;
    else
        cout<<"wrong"<<endl;
}
bool IsLRD( int A[], int length, Node* root )
{
    if( root==NULL || A==NULL || length<=0 )
        return false;
    Node *pTree = NULL;
    pTree = FindInTree( root, A[length-1] );
    if( pTree==NULL )
        return false;
    return IsLRD_Core( A, length, pTree );
}
bool IsLRD_Core( int A[], int length, Node* pTree )
{
    // 同时满足时，才说明此树为空，并在原后序遍历序列中没有其位置
    if( length<=0 && pTree==NULL )
        return true;
    //二者只满足一个，表示pTree为空却在原后序遍历中有位置，或者pTree
    //不为空，在原后序遍历中却没有位置
    if( length<=0 || pTree==NULL )
        return false;
    //根节点不对
    if( pTree->m_nElement != A[length-1] )
        return false;
    // i是左子树的根节点在原后序遍历中的位置
    int i = -1;
    if( pTree->m_pLeft != NULL )
    {
        //如果没有找到返回-1，说明左子树不空却在A中找不到，false！
        i = FindInArray( A, length-1, pTree->m_pLeft->m_nElement );
        if( i==-1 )
            return false;
    }
    return ( IsLRD_Core( A, i+1, pTree->m_pLeft ) 
            && IsLRD_Core( A+i+1, length-i-2, pTree->m_pRight ) );
}
Node* FindInTree( Node* root, int element )
{
    if( root==NULL )
        return NULL;
    Node *pTree = root;
    while( pTree!=NULL )
    {
        if( pTree->m_nElement > element )
            pTree = pTree->m_pLeft;
        else if( pTree->m_nElement < element )
            pTree = pTree->m_pRight;
        else
            break;
    }
    return pTree;
}
int FindInArray( int A[], int length, int element )
{
    if( A==NULL || length<=0 )
        return -1;
    int i;
    for( i=0; i<length; i++ )
        if( A[i] == element )
            break;
    if( i==length )
        return -1;
    return i;
}
Node* create_tree( int n )
{
    Node* head = NULL;
    Node* left = NULL;
    Node* right = NULL;
    for( int i=0; i<n; )
    {
        if( head==NULL )
        {
            head = create_node( i++ );
            left = head;
            right = head;
        }
        else
        {
            left->m_pLeft = create_node( i++ );
            right->m_pRight = create_node( i++ );
            left = left->m_pLeft;
            right = right->m_pRight;
        }
    }
    return head;
}
Node* create_node( int i )
{
    Node *tmp = new Node;
    if( !tmp )
        return NULL;
    tmp->m_nElement = i;
    tmp->m_pLeft = tmp->m_pRight = NULL;
    return tmp;
}

3. 输入一个已经按升序排序过的数组A和一个数字M,在数组中查找两个数，使得它们的和正好是输入的那个数字M

题目： 要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字M，全部输出。
分析： 蛮力解法一般都不是好的解法。本题主要是该数组已经是升序排列，这个好处就大了。两个指针指向数组头和尾，分别为h和t，在h<t的约束下，如果A[h]+A[t]>M，则t--，若A[h]+A[t]<M，则h++，A[h]+A[t]=M，则输出A[h]和A[t]，并继续h++,t--。思想类似于二分查找，毕竟排序是为了能够更方便的查找。

/*
Filename: FindNumberWithSum.cpp
Function: bool FindNumberWithSum( int A[], int length, int sum )
输入一个已经按升序排序过的数组A和一个数字M,
在数组中查找两个数，使得它们的和正好是输入的
那个数字M。要求时间复杂度是O(n)。如果有多对
数字的和等于输入的数字M，全部输出。
Details:
*/
#include <iostream>
using namespace std;
/*
   函数功能：在长为length的数组A中，找到两个数的组合，
   其和为sum，要求输出所有正确的组合
   返回值：bool类型，如果找不到正确的组合，
   则返回false，否则返回true。
*/
bool FindNumberWithSum( int A[], int length, int sum );
int main()
{
    int A[] = {1,2,4,6,7,8,9,11};
    int length = sizeof(A)/sizeof(int);
    if(!FindNumberWithSum( A, length, 21 ))
        cout<<"No result!"<<endl;
}
bool FindNumberWithSum( int A[], int length, int sum )
{
    if( A==NULL || length<=0 )
        return false;
    if( length>=2 && ( (A[length-1]+A[length-2]<sum)
                || (A[0]+A[1]>sum) ) )
        return false;
    int i=0, j=length-1;
    bool bResult = false;
    while( i<j )
    {
        if( A[i]+A[j] < sum )
            i++;
        else if ( A[i]+A[j] >sum )
            j--;
        else
        {
            cout<<A[i]<<" "<<A[j]<<endl;
            i++; j--;
            bResult = true;
        }
    }
    return bResult;
}

4.输入整数n和m，从数列1,2，...n中随意取几个数，使其和等于m，要求输出所有正确组合（未完成）

分析：中兴面试题。是基本背包问题。

5.反转单链表

题目：就地反转，即要求空间复杂度$\Theta(1)$。

/*
Filename: ReverseList.cpp
Function: 
ListNode* ReverseList( ListNode* head )
反转链表，要求空间复杂度为O(1)
Details: 
*/
#include <iostream>
using namespace std;
struct ListNode
{
    int m_nElement;
    ListNode *m_pNext;
};
/*
    反转链表
*/
ListNode* ReverseList( ListNode* head );
/*
    创建链表，头--尾的序列为 1...n
*/
ListNode* BuildList( int n );
/*
    顺序打印链表
*/
void PrintList( ListNode* head );
int main()
{
    ListNode* head = BuildList(10);
    PrintList( head );
    ListNode* new_list = ReverseList( head );
    PrintList( new_list );
}
ListNode* ReverseList( ListNode* head )
{
    if( head==NULL )
        return NULL;
    ListNode *first, *second, *third;
    first = second = head;
    third = NULL;
    while( first!=NULL )
    {
        first = second->m_pNext;
        second->m_pNext = third;
        third = second;
        second = first;
    }
    return third;
}
ListNode*  BuildList( int n )
{
    if( n<=0 )
        return NULL;
    ListNode* head = NULL;
    ListNode *list, *tmp;
    for(int i=1; i<=n; i++)
    {
        if( head==NULL )
        {
            head = new ListNode;
            head->m_nElement = i;
            if( head==NULL )
                return NULL;
            list = head;
        }
        else
        {
            tmp = new ListNode;
            if( tmp == NULL )
                return NULL;
            tmp->m_nElement = i;
            list->m_pNext = tmp;
            list = list->m_pNext;
        }
    }
    return head;
}
void PrintList( ListNode* head )
{
    if( head==NULL )
        return;
    ListNode* pList = head;
    while( pList!=NULL )
    {
        cout<<pList->m_nElement<<" ";
        pList = pList->m_pNext;
    }
    cout<<endl;
}

6.合并两个排序的链表

题目： 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。要求空间复杂度为O(1)。
分析： 第一是复杂的指针操作多，第二是有循环和递归两种实现。循环实现代码较复杂，递归的代码结构更清晰。个人认为在链表上使用递归不可取，若链表长度过长，会有因过度调用产生的时间消耗以及可能产生栈溢出的风险。递归在树结构上使用比较好，因为其调用次数一般和树的深度成线性关系，而树的深度一般都较小。

/*
Filename: MergeSortedList.cpp
Function: 
ListNode* MergeSortedList( ListNode *list1, ListNode *list2 );
输入两个递增排序的链表，合并这两个链表并使新链表中
的节点仍然是递增排序的。要求空间复杂度为O(1)。
Details: 有递归和循环两种实现
*/
#include <iostream>
using namespace std;
struct ListNode
{
    int m_nElement;
    ListNode *m_pNext;
};
/*************************循环实现**************************/
ListNode* MergeSortedList( ListNode *list1, ListNode *list2 );
/*************************递归实现**************************/
ListNode* MergeSortedListR( ListNode *list1, ListNode *list2 );
/*
    用长为length的数组X的数据创建链表
*/
ListNode* create_list( int X[], int length );
/*
    顺序打印链表
*/
void PrintList( ListNode* head );
int main( )
{
    int A[] = {1,3,5,7,9};
    int B[] = {2,4,6,8,10};
    int length_A = sizeof(A)/sizeof(int);
    int length_B = sizeof(B)/sizeof(int);
    ListNode* list1 = create_list( A, length_A );
    ListNode* list2 = create_list( B, length_B );
    PrintList( list1 );
    PrintList( list2 );
    //ListNode* list_result = MergeSortedList( list1, list2 );
    ListNode* list_result = MergeSortedListR( list1, list2 );
    PrintList( list_result );
}
ListNode* MergeSortedList( ListNode *list1,ListNode *list2 )
{
    if( list1==NULL )
        return list2;
    else if( list2==NULL )
        return list1;
    ListNode *head = NULL;
    //p1和p2是头节点的那条链表上的指针，h1是另一条链表的指针
    ListNode *p1 , *p2, *h1 ;
    p1 = p2 = h1 = NULL;
    if( list1->m_nElement <= list2->m_nElement )
        head = list1;
    else
        head = list2;
    p1 = head;
    p2 = p1->m_pNext;
    h1 = ( head==list1 ? list2: list1 );
    while( h1!=NULL && p2!=NULL )
    {
        if( p2->m_nElement <= h1->m_nElement )
        {
            p1 = p2; p2 = p2->m_pNext;
        }
        else
        {
            p1->m_pNext = h1;
            h1 = h1->m_pNext;
            p1->m_pNext->m_pNext = p2;
            p1 = p1->m_pNext;
        }
    }
    if( p2==NULL )
        p1->m_pNext = h1;
    return head;
}
ListNode* MergeSortedListR( ListNode *list1, ListNode *list2 )
{
    if( list1==NULL )
        return list2;
    else if( list2==NULL )
        return list1;
    ListNode *pMergeHead = NULL;
    if( list1->m_nElement <= list2->m_nElement )
    {
        pMergeHead = list1;
        pMergeHead->m_pNext = MergeSortedListR( 
            list1->m_pNext, list2 );
    }
    else
    {
        pMergeHead = list2;
        pMergeHead->m_pNext = MergeSortedListR( 
            list1, list2->m_pNext );
    }
    return pMergeHead;
}
ListNode*  create_list(int X[], int length )
{
    if( X==NULL || length<=0 )
        return NULL;
    ListNode* head = NULL;
    ListNode *list, *tmp;
    for(int i=0; i<length; i++)
    {
        if( head==NULL )
        {
            head = new ListNode;
            head->m_nElement = X[i];
            if( head==NULL )
                return NULL;
            list = head;
        }
        else
        {
            tmp = new ListNode;
            if( tmp == NULL )
                return NULL;
            tmp->m_nElement = X[i];
            list->m_pNext = tmp;
            list = list->m_pNext;
        }
    }
    return head;
}
void PrintList( ListNode* head )
{
    if( head==NULL )
        return;
    ListNode* pList = head;
    while( pList!=NULL )
    {
        cout<<pList->m_nElement<<" ";
        pList = pList->m_pNext;
    }
    cout<<endl;
}

7.用最简单,最快速的方法计算出下面这个圆形是否和正方形相交

题目：给出一个圆形的圆心$r$与半径$R_{y}$，一个正方形的四个顶点$A_{i}$,1<=i<=4,的坐标，判断两者是否相交。
分析：我能想到最简单也是最暴力的方法就是求出圆心到正方形四条边（线段，不是直线）的最短距离$d$，$d$若小于等于$R_{y}$则相交。所以主要的函数应该是求一点到一条线段的最短距离。

/*
Filename: SquareIntersectCircle.cpp
Function:
Details:
*/
#include <iostream>
#include <math.h>
using namespace std;
#ifndef MIN
#define MIN( a, b )  (a)>(b)?(b):(a) 
#endif
struct cPoint
{
    double x;
    double y;
};
struct Line_Segment
{
    cPoint A;
    cPoint B;
};
struct Circle
{
    cPoint Center;
    double Radius;
};
struct Square
{
    cPoint p[4];
};
typedef Line_Segment Segment;
bool IsIntersect( Circle c, Square s );
double DistancePS( cPoint p, Segment s );
double dist( cPoint a, cPoint b );
int main()
{
    Circle c;
    Square s;
    c.Center.x = 3;
    c.Center.y = 3;
    c.Radius = 1.5;
    s.p[0].x = 0;
    s.p[0].y = 0;
    s.p[1].x = 2;
    s.p[1].y = 0;
    s.p[2].x = 2;
    s.p[2].y = 2;
    s.p[3].x = 0;
    s.p[3].y = 2;
    if( IsIntersect( c, s ) )
        cout<< "The square is intersect with the circle!"<<endl;
    else
        cout<< "The square is not intersect with the circle!"<<endl;
}
bool IsIntersect( Circle c, Square s )
{
    bool bResult = false;
    int i=0;
    Segment line;
    for( ; i<4; i++ )
    {
        line.A.x = s.p[i%4].x;
        line.A.y = s.p[i%4].y;
        line.B.x = s.p[(i+1)%4].x;
        line.B.y = s.p[(i+1)%4].y;
        if( DistancePS( c.Center, line ) <= c.Radius )
        {
            bResult = true;
            break;
        }
    }
    return bResult;
}
double DistancePS( cPoint p, Segment s )
{
    cPoint intersection;
    cPoint line_gradient;
    cPoint tmp;
    line_gradient.x = s.A.x - s.B.x;
    line_gradient.y = s.A.y - s.B.y;
    tmp.x = p.x - s.A.x;
    tmp.y = p.y - s.A.y;
    intersection.x = s.B.x * line_gradient.x;
    intersection.y = s.B.y * line_gradient.y;
    double ratio ;
    ratio = ( tmp.x * line_gradient.x ) + ( tmp.y * line_gradient.y );
    ratio /= ( intersection.x + intersection.y );
    if( ratio>=0 && ratio<=1 )
    {
        intersection.x = s.A.x + ratio * s.B.x;
        intersection.y = s.A.x + ratio * s.B.y;
        return dist( p, intersection );
    }
    return MIN( dist( p, s.A ), dist( p, s.B ) );
}
double dist( cPoint a, cPoint b )
{
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

8.在字符串中找出连续最长的数字串

题目：在字符串中找出连续最长的数字串,并把这个最长数字串付给其中一个函数参数 outputstr所指内存,返回outputstr,将其长度保存在变量length中。
分析：思路清晰简单，用两个变量start和end标识数字串的开头和结尾索引即可。

/*
Filename: LongestNumberString.cpp
Function: char* continumax( char *inputstr, int *length )
在字符串中找出连续最长的数字串,并把这
个最长数字串付给其中一个函数参数 outputstr
所指内存,返回outputstr,将其长度保存在变量length中。
Details:
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
using namespace std;
char* continumax( char *inputstr, int *length );
int main()
{
    char inputstr[]="I'm so happy in 2014, \
        and my birthday is 19901120.";
    char *outputstr = NULL;
    int length =0;
    outputstr = continumax( inputstr, &length );
    //cout<<" Longest number string is: "<<outputstr<<endl;
    printf("Longest nmumber string is %d : %s \n",length, outputstr );
}
char* continumax( char *inputstr, int *length )
{
    if( inputstr==NULL )
        return 0;
    int start=0, end=0;
    int s_max=0, e_max=0;
    int max_length=0;
    int str_length = strlen( inputstr );
    for( ; end<str_length; )
        if( inputstr[end]<='9' && inputstr[end]>='0' )
            end++;
        else
        {
            if( end-start > max_length )
            {
                max_length = end-start;
                s_max = start;
                e_max = end-1;
            }
            start = ++end;
        }
    if( end-start > max_length )
    {
        max_length = end-start;
        s_max = start;
        e_max = end-1;
    }
    *length = max_length;
    char *outputstr;
    if( outputstr==NULL )
        outputstr = (char*) malloc( sizeof(char)*(max_length+1) );
    for( int i=0; i<max_length; i++ )
        outputstr[i] = inputstr[i+s_max];
    outputstr[max_length] = '\0';
    return outputstr;
}

9.跳台阶问题(递归)

题目:一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级。
求总共有多少总跳法,并分析算法的时间复杂度。
分析：假设跳n级台阶有$f(n)$种跳法，则可以推出$f(n+1)=f(n)+f(n-1)$。归结到底是Fabinocci数列问题。

10.整数的二进制表示中 1 的个数(运算)

题目:输入一个整数,求该整数的二进制表达中有多少个 1。
例如输入 10,由于其二进制表示为 1010,有两个 1,因此输出 2。
分析:这是一道很基本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。
思路1：简单的思路是从最低位检验到最高位，如果int是32位，则需检验32次。
思路2：这里用到一个技巧，即对于整数m，m-1会将m最低位的1置0并将比最低位的1更低位的所有0变为1，如二进制1100，减1后变为1011.$(m \& m-1)$会将最低位的1置0.这种方法所需检验次数为整数m中1的个数。

/*
Filename: NumbersBit1.cpp
Function: int NumbersBit1( int n ); int Numbers2Bit1( int n );
输入一个整数,求该整数的二进制表达中有多少个 1,
例如输入 10,由于其二进制表示为 1010,有两个 1,
因此输出 2
Details: 两种实现
*/
#include <iostream>
using namespace std;
int NumbersBit1( int n );
int Numbers2Bit1( int n );
int main()
{
    cout<<NumbersBit1( 64 )<<endl;
    cout<<Numbers2Bit1( 64 )<<endl;
}
int NumbersBit1( int n )
{
    int num = 0;
    int i=1;
    while( i )
    {
        if( n & i )
            num++;
        i = i<<1;
    }
    return num;
}
int Numbers2Bit1( int n )
{
    int num = 0;
    while( n )
    {
        num++;
        n = n & n-1;
    }
    return num;
}