美团网2014笔试算法题汇总

1.链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现。

#include <iostream>  
using namespace std;  
  
struct ListNode  
{  
    int m_nValue;  
    ListNode *m_pNext;  
};  
  
ListNode* CreateList(int val)  
{  
    ListNode *pHead = new ListNode;  
  
    pHead->m_nValue = val;  
    pHead->m_pNext = NULL;  
  
    return pHead;  
}  
  
void InsertNode(ListNode **pHead, int val)  
{  
    ListNode *pNode = new ListNode;  
    pNode->m_nValue = val;  
    pNode->m_pNext = NULL;  
  
    while ((*pHead)->m_pNext != NULL)  
    {  
        (*pHead) = (*pHead)->m_pNext;  
    }  
  
    (*pHead)->m_pNext = pNode;  
    (*pHead) = pNode;  
}  
  
void PrintList(ListNode *pHead)  
{  
    while (pHead != NULL)  
    {  
        cout<<pHead->m_nValue<<" ";  
        pHead = pHead->m_pNext;  
    }  
    cout<<endl;  
}  
  
ListNode* Reverse(ListNode *pHead)  
{  
    if (pHead == NULL || pHead->m_pNext == NULL)  
    {  
        return pHead;  
    }  
  
    ListNode *pPre = NULL;  
    ListNode *pCurrent = pHead;  
    ListNode *pPost = pHead->m_pNext;  
  
    while (pCurrent->m_pNext != NULL)  
    {  
        pCurrent->m_pNext = pPre;  
        pPre = pCurrent;  
        pCurrent = pPost;  
        pPost = pPost->m_pNext;  
    }  
    pCurrent->m_pNext = pPre;  
  
    return pCurrent;  
}  
  
  
  
ListNode* ReverseList(ListNode *pHead, int k)  
{  
    if (pHead==NULL || pHead->m_pNext==NULL)  
    {  
        return pHead;  
    }  
  
    ListNode *pPre = NULL;  
    ListNode *pCurrent = pHead;  
    ListNode *pPost = pHead->m_pNext;  
    ListNode *pStart = NULL;  
    ListNode *pEnd = NULL;  
  
    int n = 0;  
    pEnd = pCurrent;  
    pEnd->m_pNext = NULL;  
    while (pPost != NULL)  
    {  
        ++n;  
        if (n == (k+1))  
        {  
            pStart = pPre;  
            pEnd->m_pNext = ReverseList(pCurrent, k);  
  
            return pStart;  
        }  
        else  
        {  
            pCurrent->m_pNext = pPre;  
            pPre = pCurrent;  
            pCurrent = pPost;  
            pPost = pPost->m_pNext;  
        }  
    }  
  
    pCurrent->m_pNext = pPre;  
    pStart = Reverse(pCurrent);  
    return pStart;  
}  
  
int main()  
{  
    ListNode *pHead = NULL;  
    ListNode *head = NULL;  
    int n;  
    cout<<"输入链表中节点的个数 n："<<endl;  
    cin>>n;  
    cout<<"请输入n个整数值："<<endl;  
    for (int i=0; i<n; ++i)  
    {  
        int data;  
        cin>>data;  
  
        if (pHead == NULL)  
        {  
            pHead = CreateList(data);  
            head = pHead;  
        }  
        else  
        {  
            InsertNode(&pHead, data);  
        }  
    }  
  
    int k;  
    cout<<"请输入k:"<<endl;  
    cin>>k;  
    head = ReverseList(head, k);  
    PrintList(head);  
  
    system("pause");  
    return 0;  
}  

2.一个函数access(),调用频率不能超过R次/sec，用程序实现一个函数，当超过R次/sec时返回access false，不超过时返回success

#define false 0  
#define success 1  
int getcurrentms()  
{  
  struct timeval tv;  
  gettimeofday(&tv,NULL);  
  return tv.tv_sec*1000+tv.tv_usec/1000; //得到毫秒数  
}  
  
bool count_access()  
{  
  static int count=0;  
  static int time_ms_old=0,time_ms_now;  
  if(count==0)  
  {  
    time_ms_old=getcurrentms();  
  }  
  count++;  
  access();  
  if(count>=R)  
  {  
    time_ms_now=getcurrentms();  
    if(time_ms_now-time_ms_pld>=1000)  
        return false;  
    else  
        return success;  
  }  
  return success;  
}  

4.利用两个栈，模拟queue

#include <iostream>  
#include <stack>  
using namespace std;  
  
template <class T>  
class Queue  
{  
public:  
    Queue()  
    {  
    }  
    ~Queue()  
    {  
    }  
  
    void add(const T& t);  
    T remove();  
private:  
    stack<T> s1;  
    stack<T> s2;  
};  
  
template <class T>  
void Queue<T>::add(const T& t)  
{  
    s1.push(t);  
}  
  
template <class T>  
T Queue<T>::remove()  
{  
    if (s2.size() <= 0)  
    {  
        while (s1.size() > 0)  
        {  
            T t = s1.top();  
            s2.push(t);  
            s1.pop();  
        }  
    }  
  
    if (s2.size() == 0)  
    {  
        throw new exception("empty queue");  
    }  
  
    T t = s2.top();  
    s2.pop();  
  
    return t;  
  
}  
  
int main()  
{  
    Queue<char> q;  
  
    q.add('A');  
    q.add('B');  
    q.add('C');  
    cout<<q.remove()<<endl;  
    cout<<q.remove()<<endl;  
    cout<<q.remove()<<endl;  
  
    system("pause");  
    return 0;  
} 

5.求两个字符串的最长公共子串

public class MaxConString {  
  
    /** 
     * 计算两字符串最大公共字符串长度 
     */  
    public static void main(String[] args) {  
  
        char[] s1 = "jiajiangayaoyao".toCharArray();            //测试数据  
        char[] s2 = "jiangyaoyao".toCharArray();  
        int c = new MaxConString().getCount(s1, s2);  
        System.out.println("两字符串的共同字符串长度为:"+c);  
          
    }  
  
    private int getSubCount(char[] s1,char[] s2, int i ,int j){//计算两字符串从s1的第i位置s2的第j位置的之后字符串长度  
                                                                //如“abc”和“ab”则返回conut为2  
        int count=1;  
        while(++i<s1.length&&++j<s2.length&&s1[i]==s2[j]){  
            count++;  
        }  
        return count;  
    }  
      
    private int getCount(char[]s1,char[]s2){                //计算两字符串的共同字符串长度  
        int count = 0;  
        for(int i=0;i<s1.length;i++)  
            for(int j=0;j<s2.length;j++)  
                if(s1[i]==s2[j]){  
                      
                    if(this.getSubCount(s1, s2, i, j)>count)  
                    count = this.getSubCount(s1, s2, i, j);  
                }  
        return count;     
    }  
}