微软面试题汇总

题目（答案参考后面）：

1、有一个整数数组，请求出两两之差绝对值最小的值，记住，只要得出最小值即可，不需要求出是哪两个数。

2、平面上N个点，没两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点

平面上N个点，没两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。
先把N个点按x排序。
斜率k最大值为max(斜率(point[i],point[i+1]))    0 <=i <n-2。
复杂度Nlog(N)。
以3个点为例,按照x排序后为ABC,假如3点共线,则斜率一样,假如不共线,则可以证明AB或BC中,一定有一个点的斜率大于AC,一个点的斜率小于AC。

3、写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整型的函数）

5、怎样从顶部开始逐层打印二叉树结点数据？请编程。

7、在排序数组中，找出给定数字的出现次数。比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。

8、一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
注意：
- 5个数值允许是乱序的。比如： 8 7 5 0 6
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出现。
- 复杂度如果是O(n2)则不得分。

插入排序-》最大值-最小值<=4

9、一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。

答案：

1、

using System;
using System.Linq;
using System.Collections.Generic;
namespace ConsoleApplication1
{
    class Program
    {
        static Random Rand = new Random();

        static void Main(string[] args)
        {
            int count = 10000;
            List<int> Input = new List<int>();
//             for (int i = 0; i < count; i++)
//             {
//                 Input.Add(Rand.Next(int.MinValue, int.MaxValue));
//             }
            Input.Add(1); Input.Add(2); Input.Add(3); Input.Add(4); Input.Add(5); Input.Add(19);

            ulong re = PigeonNest(Input, ulong.MaxValue);
            Console.WriteLine(re);
            Console.WriteLine(ulong.MaxValue);
            Console.WriteLine(Input.Min());
        }

        //鸽巢原理。
        static ulong PigeonNest(List<int> List, ulong MinResult)
        {
            switch (List.Count)
            {
                case 0:
                case 1:
                    return MinResult;
                case 2:
                    return ABS(List[0], List[1]);
                default:
                    break;
            }
            int min = List.Min();
            //确定桶的大小。
            int width = (int)Math.Ceiling((double)(List.Max() - min) / List.Count);
            //不可能比1还小了。
            if (width == 1) { return 1ul; }
            //把数据丢到桶里。
            Dictionary<int, NumbersInfo> EachNestNum = new Dictionary<int, NumbersInfo>();
            foreach (int n in List)
            {
                int Key = Convert.ToInt32(Math.Ceiling((double)(n - min) / width));
                if (!EachNestNum.ContainsKey(Key))
                {
                    EachNestNum.Add(Key, new NumbersInfo(Key));
                }
                EachNestNum[Key].Add(n);
            }
            //找到所有桶里，和相邻两桶的最大最小值距离，三个数中最近的。
            foreach (int Key in EachNestNum.Keys)
            {
                MinResult = Min(MinResult, EachNestNum[Key].minresult(EachNestNum, MinResult));
            }
            return MinResult;
        }
        class NumbersInfo
        {
            public NumbersInfo(int k)
            { key = k; }
            private List<int> List = new List<int>();
            private int key;
            public int max = int.MinValue;
            public int min = int.MaxValue;
            public int count { get { return List.Count; } }
            public ulong minresult(Dictionary<int, NumbersInfo> EachNestNum, ulong re)
            {
                //在三个数中选最小的。  
                //当命中数大于1的时候，递归这个过程。由于迅速收敛，故复杂度忽略不计。
                if (List.Count > 1)
                {
                    re = PigeonNest(List, re);
                }
                if (EachNestNum.ContainsKey(key - 1))
                {
                    re = Min(ABS(EachNestNum[key].min, EachNestNum[key - 1].max), re);
                }
                if (EachNestNum.ContainsKey(key + 1))
                {
                    re = Min(ABS(EachNestNum[key].max, EachNestNum[key + 1].min), re);
                }
                return re;
            }
            public void Add(int x)
            {
                List.Add(x);
                if (x > max) { max = x; }
                if (x < min) { min = x; }
            }
        }


        static ulong ABS(int x, int y)
        {
            //三分。
            switch (x.CompareTo(y))
            {
                case -1:
                    return (ulong)y - (ulong)x;
                case 1:
                    return (ulong)x - (ulong)y;
            }
            return 0ul;

        }

        static ulong Min(ulong x, ulong y)
        {
            if (x > y) { return y; }
            return x;
        }
    }
}

2、

平面上N个点，没两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。
先把N个点按x排序。
斜率k最大值为max(斜率(point[i],point[i+1]))    0 <=i <n-2。
复杂度Nlog(N)。
以3个点为例,按照x排序后为ABC,假如3点共线,则斜率一样,假如不共线,则可以证明AB或BC中,一定有一个点的斜率大于AC,一个点的斜率小于AC。

3、

long strtoint(char *str,int length){
    if(length > 1) {
        return str[0]=='-' ? strtoint(str, length-1)*10-(str[length-1]-'0') : strtoint(str, length-1)*10+str[length-1]-'0';
    } else {
        return str[0]=='-' ? -1/10 : str[0]-'0';
    }
}

4、

#include <iostream>

using namespace std;

typedef struct Node
{
    int v;
    struct Node *lchild;
    struct Node *rchild;
}Node;

void Insert(Node *&n, int v) {
    if (NULL == n)
    {
        n = (Node*)malloc(sizeof(Node));
        n->v = v; n->lchild = n->rchild = NULL;
        return;
    }
    if (v < n->v)
    {
        Insert(n->lchild, v);
    }
    else
    {
        Insert(n->rchild, v);
    }
}

void Print(Node *r)
{
    if (NULL == r)
    {
        return;
    }
    Print(r->lchild);
    cout << r->v << endl;
    Print(r->rchild);
}

Node *root = NULL;

void Print1(int a[], int low, int high)
{
    if (low > high)    return;
    int mid = (low+high)/2;
    Insert(root, mid);
    Print1(a, low, mid-1);
    Print1(a, mid+1, high);
}

int main()
{
//     Node *root = NULL;
//     for (int i = 0; i < 3; i++)
//     {
//         Insert(root, i);
//     }

    int a[6];
    for (int i = 0; i < 6; i++)
    {
        a[i] = i;
    }

    Print1(a, 0, 5);

    // Êä³ö²éÕÒ¶þ²æÊ÷
    Print(root);

    return 0;
}

5、

void Print2(Node *root)
{
    queue<Node*> q;
    q.push(root);

    while(!q.empty())
    {
        Node *t = q.front();
        q.pop();
        cout << t->v;
        if (t->lchild) q.push(t->lchild);
        if (t->rchild) q.push(t->rchild);
    }
    cout << endl;
}

6、

#include <iostream>

using namespace std;

int div1(const int x, const int y) {
    int left_num = x;
    int result = 0;
    while (left_num >= y) {
        int multi = 1;
        while (y * multi <= (left_num>>1)) {
            multi = multi << 1;
        }
        result += multi;
        left_num -= y * multi;
    }
    return result;
}

int main()
{
    cout << div1(11, 3) << endl;
    return 0;
}

7、

#include <iostream>

using namespace std;

void equal_range1(int a[], int len, int x)
{
    int low=0, high=len-1;
    int mid;
    while (low<=high)
    {
        mid=(low+high)/2;
        if (x==a[mid]) {cout << mid << endl; break;}
        else if (x<mid) high=mid-1;
        else low=mid+1;
    }
    if (low>high)
    {
        cout << "ûÓÐÕÒµ½" << x << endl;
    }
    else
    {
        int k=mid-1;
        while (k>=0&&a[k]==x)
        {
            cout << k-- << endl;
        }
        k=mid+1;
        while (k<=len-1&&a[k]==x)
        {
            cout << k++ << endl;
        }
    }
}

int main()
{
    int a[] = {1,2,2,2,2,3,4};
    equal_range1(a, 7, 2);
    return 0;
}

8、

9、

void find1(Node *h, int value1, Node *&r)
{
    if (NULL==h)
    {
        return;
    }
    if (value1 >= h->v)
    {
        find1(h->rchild, value1, r);
    }
    else
    {
        r=h;
        find1(h->lchild, value1, r);
    }
}