总结几个面试题

最近参见了几个公司的实习面试，也参考了其他同学面试时遇到的一些问题，在此总结一下。

PS：今天去的面试，面试官很nice，虽然很多不会，但至少并没有很难为我，本文只求攒人品了（可能有些问题比较老）。

问题：

1、从2、3、4、5、6五个数字中每次取出三个不同的数字组成三位数，求所有三位数的和。
2、s(m,n)表示把m个有区别的球放到n个相同的盒子中，且无一空盒，其不同的方案数。
3、约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
4、单向链表反转。
5、n个相同的物品，分成M堆，每堆至少一个，求方案数。比如4个物体分成两堆，（1、3）和（2、2）共两种方案。
6、求一个数组中第二大的数。

答案：可能有更好答案，但这里的答案可能不是最优的，但一定是对的（VS2010）.

1、解：形如**2的数共有A(4,2)个，当这些数相加时，由“2”产生的和是A(4,2)*2；形如*2*的数也有A(4,2)个，当这些数相加时，由“2”产生的和是A(4,2)*20；形如2**的数也有A(4,2)个，当这些数相加时，由“2”产生的和应是A(4,2)*200．这样在所有三位数的和中，由“2”产生的和是A(4,2)*2*111．同理由3/4/5/6产生的和分别是A(4,2)*3*111,A(4,2)*4*111，因此所有三位数的和是A(4,2)*111*(2+3+4+5+6)=26640．

2、第二类斯特林数，也很是体现了动态规划的思想。

#include <iostream>
using namespace std;
const int N=100;
int data[N][N];
int fun(int m, int n)
{
    memset(data, 0, sizeof(data));
    data[0][0] = 1;
    for(int i=1; i<=m; i++)
    {
        int minValue;
        if(i>n)minValue = n;
        else minValue=i;
        for(int j=1; j<=minValue; j++)
        {
            data[i][j] = data[i-1][j-1] + j*data[i-1][j];
        }
    }
    return data[m][n];
}

int main()
{
    cout << fun(6,2)<<endl;
}

3、链表的解决方案

#include <iostream>
using namespace std;

typedef struct node
{
    int value;
    struct node * next;
} Node, *List;

void createlist(List *head, int n)
{
    List p, q;
    int i=1;
    *head = (List)malloc(sizeof(Node));
    p=*head;
    p->value = i;
    for(i=2;i<=n;i++)
    {
        q= (List)malloc(sizeof(Node));
        q->value=i;
        p->next=q;
        p=q;
    }
    p->next = *head;
}

void deletelist(List *head,int n)
{
    List cur,pre;
    cur=pre=*head;
    int i=1;
    while(1)
    {
        if(i==n)
        {
            pre->next = cur->next;
            printf("%d
", cur->value);
            free(cur);
            cur = pre->next;
            i=1;
        }
        pre = cur;
        cur = pre->next;
        i++;
        if(pre == cur)
        {
            printf("%d
", cur->value);
            free(cur);
            break;
        }
    }
}

int main()
{
    List sefu;
    int M=4,N=3;
    createlist(&sefu, M);
    deletelist(&sefu, N);
    return 0;
}

4、常见问题，程序实现

#include <iostream>
using namespace std;

typedef struct node
{
    int value;
    struct node *next;
}Node, *List;

void createlist(List *head, int n)
{
    List p,q;
    *head = (List)malloc(sizeof(Node));
    p=*head;
    p->value = 0;
    for(int i=1;i<n;i++)
    {
        q = (List)malloc(sizeof(Node));
        q->value = i;
        p->next = q;
        p = q;
    }
    p->next = NULL;
}

void reverselist(List *head)
{
    List cur,pre,post;
    pre = cur = *head;
    bool first = true;
    while(cur->next)
    {
        if(first)
        {
            post = cur->next;
            cur->next = NULL;
            first = false;
        }
        else
        {
            post = cur->next;
            cur->next = pre;
        }
        pre = cur;
        cur = post;
    }
    cur->next = pre;
    *head = cur;
}
void printlist(List *head)
{
    List p;
    p=*head;
    while(p)
    {
        printf("%d
",p->value);
        p = p->next;    
    }
}
int main()
{
    List test;
    createlist(&test, 10);
    printlist(&test);
    reverselist(&test);
    printlist(&test);
    return 0;
}

5、这个问题让我不由想起了“八皇后”问题。

#include <iostream>
using namespace std;

int N,M,a[100],count =0;
void fun(int k)
{
    if(k>M)
    {
        for(int i=1; i<=M; i++)
        {
            cout <<a[i] <<"	";
        }
        cout<<endl;
        count++;
    }
    else
    {
        //sum
        int sum = 0;
        for(int i=1;i<k;i++)
        {
            sum+=a[i];
        }

        for(int i=a[k-1];i<=(N-sum);i++)
        {
            if(k==M)
            {
                i=N-sum;
                if(a[k-1]>i)break;
            }
            a[k]=i;
            fun(k+1);
        }
    }
}
int main()
{
    N=10,M=5;
    a[0]=1;
    fun(1);
    cout<<count<<endl;
    return 0;
}

6、老问题了吧

#include <iostream>
using namespace std;

int secMax(int a[],int len)
{
    int max1,max2;
    if(a[0]>a[1])
    {
        max1 = a[0];
        max2 = a[1];
    }
    else
    {
        max1 = a[1];
        max2 = a[0];
    }

    for(int i=2; i<len; i++)
    {
        if(a[i] > max1)
        {
            max2 = max1;
            max1 = a[i];
        }
        else if(a[i] > max2)
        {
            max2 = a[i];
        }
    }
    return max2;
}
int main()
{
    int a[6]={6,2,7,4,5,1};
    cout << secMax(a,6)<<endl;
    return 0;
}

可能不同的问题对应不同的大类，有不同的思想和技巧，这里就不总结了（论思想，一个问题就要讲一篇博客）。有错误请大家反馈，不喜勿骂。