蘑菇街2016研发工程师在线编程题

题目一  搬圆桌

现在有一张半径为r的圆桌,其中心位于(x,y),现在他想把圆桌的中心移到(x1,y1)。每次移动一步,都必须在圆桌边缘固定一个点然后将圆桌绕这个点旋转。问最少需要移动几步。
 输入描述:
一行五个整数r,x,y,x1,y1(1≤r≤100000,-100000≤x,y,x1,y1≤100000)
 输出描述:
输出一个整数,表示答案
输入例子:
2 0 0 0 4
 输出例子:
1

分析

该题目其实理解后很简单,如果圆心初始位置与末尾值之间的距离 是 2*r的整数倍,则反转该商的次数即可。否则必须额外多反转一次,注意类型必须选择long,否则会溢出~


AC代码



    /* 
    [编程题 - 1] 搬圆桌 
    现在有一张半径为r的圆桌,其中心位于(x,y),现在他想把圆桌的中心移到(x1,y1)。每次移动一步,都必须在圆桌边缘固定一个点然后将圆桌绕这个点旋转。问最少需要移动几步。 
     
    输入描述: 
    一行五个整数r,x,y,x1,y1(1≤r≤100000,-100000≤x,y,x1,y1≤100000) 
     
    输出描述: 
    输出一个整数,表示答案 
     
    输入例子: 
    2 0 0 0 4 
     
    输出例子: 
    1 
    */  
      
    #include <iostream>  
    #include <cstdlib>  
    #include <algorithm>  
      
    using namespace std;  
      
    long distance(long x0, long y0, long x1, long y1)  
    {  
        return static_cast<long>(sqrt((x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0)));  
    }  
      
    int main()  
    {  
        long r, x, y, x1, y1;  
        while (cin >> r >> x >> y >> x1 >> y1)  
        {  
            long dis = distance(x, y, x1, y1);  
              
            if ((dis % (2*r)) == 0)  
                cout <<(dis / (2 * r)) << endl;  
            else{  
                cout << (dis / (2 * r)) + 1 << endl;  
            }//else  
      
        }//while  
        //system("pause");  
        return 0;  
    }  



题目二 最大间隔

给定一个递增序列,a1 <a2 <...<an 。定义这个序列的最大间隔为d=max{ai+1 - ai }(1≤i<n),现在要从a2,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少?
 输入描述:
第一行,一个正整数n(1<=n<=100),序列长度;接下来n个小于1000的正整数,表示一个递增序列。

 输出描述:
输出答案。
 输入例子:
5
1 2 3 7 8
 输出例子:
4

分析

我的这道题的解决方法不好,时间复杂度O(n^2),完全是暴力解决的,主要是时间紧张,不能好好构思呀……||

AC代码



    /* 
    给定一个递增序列,a1 <a2 <...<an 。定义这个序列的最大间隔为d=max{ai+1 - ai }(1≤i<n),现在要从a2 ,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少? 
    输入描述: 
     
    第一行,一个正整数n(1<=n<=100),序列长度;接下来n个小于1000的正整数,表示一个递增序列。 
     
    输出描述: 
     
    输出答案。 
     
    输入例子: 
     
    5 
    1 2 3 7 8 
     
    输出例子: 
     
    4 
    */  
      
    #include <iostream>  
    #include <cstdlib>  
    #include <vector>  
    #include <climits>  
      
    using namespace std;  
    int maxD(vector<int> v)  
    {  
        if (v.empty())  
            return 0;  
      
        int len = v.size();  
        int maxDis = 0;  
        for (int i = 0; i < len - 1; ++i)  
        {  
            int d = v[i + 1] - v[i];  
            if (maxDis < d)  
                maxDis = d;  
        }//for  
        return maxDis;  
    }  
      
    int main()  
    {  
        int n;  
        while (cin >> n)  
        {  
            vector<int> v(n, 0);  
            for (int i = 0; i < n; ++i)  
                cin >> v[i];  
      
            int minDis = INT_MAX;  
            for (int j = 1; j < n; ++j)  
            {  
                vector<int> v2;  
                for (int i = 0; i < n; ++i)  
                {  
                    if (i == j)  
                        continue;  
                    else  
                        v2.push_back(v[i]);  
                }//for  
      
                int tmp = maxD(v2);  
                if (tmp < minDis)  
                    minDis = tmp;  
                v2.clear();  
            }//for  
      
            cout << minDis << endl;  
      
        }//while  
          
        //system("pause");  
        return 0;  
    }  



题目三 聊天

A和B是好友,他们经常在空闲时间聊天,A的空闲时间为[a1 ,b1 ],[a2 ,b2 ]..[ap ,bp ]。B的空闲时间是[c1+t,d1 +t]..[cq +t,dq +t],这里t为B的起床时间。这些时间包括了边界点。B的起床时间为[l,r]的一个时刻。若一个起床时间能使两人在任意时刻聊天,那么这个时间就是合适的,问有多少个合适的起床时间?
输入描述:
第一行数据四个整数:p,q,l,r(1≤p,q≤50,0≤l≤r≤1000)。接下来p行数据每一行有一对整数ai,bi(0≤ai<bi≤1000)表示a的时间表,接下来p行每行一对整数ci,di(0≤ci,di≤1000)表示b的时间表。保证ai+1>bi,ci+1>di
输出描述:
输出答案个数
输入例子:
2 3 0 20
15 17
23 26
1 4
7 11
15 17
输出例子:
20

分析

厘清题意,要找出[l,r]中可以使得,A,B两人有共同空闲时间进行聊天的数的个数。

AC代码

    /* 
    A和B是好友,他们经常在空闲时间聊天,A的空闲时间为[a1 ,b1 ],[a2 ,b2 ]..[ap ,bp ]。B的空闲时间是[c1 +t,d1 +t]..[cq +t,dq +t],这里t为B的起床时间。这些时间包括了边界点。B的起床时间为[l,r]的一个时刻。若一个起床时间能使两人在任意时刻聊天,那么这个时间就是合适的,问有多少个合适的起床时间? 
    输入描述: 
     
    第一行数据四个整数:p,q,l,r(1≤p,q≤50,0≤l≤r≤1000)。接下来p行数据每一行有一对整数ai,bi(0≤aii+1>bi,ci+1>di 
     
    输出描述: 
     
    输出答案个数 
     
    输入例子: 
     
    2 3 0 20 
    15 17 
    23 26 
    1 4 
    7 11 
    15 17 
     
    输出例子: 
     
    20 
    */  
    #include <iostream>  
    #include <cstdlib>  
    #include <vector>  
    #include <algorithm>  
      
    using namespace std;  
      
    struct Time{  
        int start;  
        int end;  
      
        Time(int s, int e) :start(s), end(e){}  
        ~Time(){}  
    };  
      
    bool cmp(const Time &t1, const Time &t2)  
    {  
        return t1.start < t2.start;  
    }  
      
    bool isCommon(const Time &t1, const Time &t2)  
    {  
        if (t1.end < t2.start || t2.end < t1.start)  
            return false;  
        return true;  
    }  
      
    /*判断t是否可以使得a,b在任意时刻聊天*/  
    bool isValid(vector<Time> aTimes, vector<Time> bTimes, int t)  
    {  
        if (aTimes.empty() || bTimes.empty())  
            return false;  
        int aLen = aTimes.size(), bLen = bTimes.size();  
      
        vector<Time> times(aTimes.begin(), aTimes.end());  
        for (int i = 0; i < bLen; ++i)  
        {  
            bTimes[i].start += t;  
            bTimes[i].end += t;  
            times.push_back(bTimes[i]);  
        }//for  
      
        sort(times.begin(), times.end(), cmp);  
      
        for (int i = 0; i < aLen + bLen -1; ++i)  
        {  
            for (int j = i + 1; j < aLen + bLen; ++j)  
            {  
                if (isCommon(times[i], times[j]))  
                    return true;  
            }//for    
        }//for  
        return false;  
    }  
      
    int main()  
    {  
        int p, q, l, r;  
        while (cin >> p >> q >> l >> r)  
        {  
            vector<Time> aTimes, bTimes;  
            /*读取a的空隙时间*/  
            for (int i = 0; i < p; ++i)  
            {  
                int s, e;  
                cin >> s >> e;  
                Time time(s, e);  
                aTimes.push_back(time);  
            }//for  
      
            /*读取b的空隙时间*/  
            for (int i = 0; i < q; ++i)  
            {  
                int s, e;  
                cin >> s >> e;  
                Time time(s, e);  
                bTimes.push_back(time);  
            }  
      
            int count = 0;  
            for (int i = l; i <= r; ++i)  
            {  
                if (isValid(aTimes, bTimes, i))  
                    count += 1;  
            }//for  
      
            cout << count << endl;  
        }//while  
    }  



题目四 投篮游戏

有一个投篮游戏。球场有p个篮筐,编号为0,1...,p-1。每个篮筐下有个袋子,每个袋子最多装一个篮球。有n个篮球,每个球编号xi 。规则是将数字为xi 的篮球投到xi 除p的余数为编号的袋里。若袋里已有篮球则球弹出游戏结束输出i,否则重复至所有球都投完。输出-1。问游戏最终的输出是什么?
输入描述:
第一行两个整数p,n(2≤p,n≤300)。p为篮筐数,n为篮球数。接着n行为篮球上的数字xi(0≤xi≤1e9)
输出描述:
输出游戏的结果
输入例子:
10 5
0
21
53
41
53
输出例子:
4

AC代码


    /* 
    有一个投篮游戏。球场有p个篮筐,编号为0,1...,p-1。每个篮筐下有个袋子,每个袋子最多装一个篮球。有n个篮球,每个球编号xi 。规则是将数字为xi 的篮球投到xi 除p的余数为编号的袋里。若袋里已有篮球则球弹出游戏结束输出i,否则重复至所有球都投完。输出-1。问游戏最终的输出是什么? 
     
    输入描述: 
     
    第一行两个整数p,n(2≤p,n≤300)。p为篮筐数,n为篮球数。接着n行为篮球上的数字xi(0≤xi≤1e9) 
     
    输出描述: 
     
    输出游戏的结果 
     
    输入例子: 
     
    10 5 
    0 
    21 
    53 
    41 
    53 
     
    输出例子: 
     
    4 
    */  
    #include <iostream>  
    #include <cstdlib>  
    #include <vector>  
      
    using namespace std;  
      
    int main()  
    {  
        int p, n;  
        while (cin >> p >> n)  
        {  
            vector<int> balls(n, 0);  
            for (int i = 0; i < n; ++i)  
                cin >> balls[i];  
      
            /*存储篮筐编号0~p-1中球的个数*/  
            vector<int> numbers(p, 0);  
            int i = 0;  
            for (i = 0; i < n; ++i)  
            {  
                int t = balls[i] % p;  
                if (numbers[t] > 0)  
                {  
                    cout << i+1 << endl;  
                    break;  
                }//if  
                ++numbers[t];  
            }//for  
            if (i == n)  
                cout << "-1" << endl;  
        }//while  
      
        system("pause");  
        return 0;  
          
    }  




题目五 回文串

给定一个字符串,问是否能通过添加一个字母将其变为回文串。
 输入描述:
一行一个由小写字母构成的字符串,字符串长度小于等于10。
 输出描述:
输出答案(YES\NO).
 输入例子:
coco
 输出例子:
YES

分析

这道题悲剧了。虽然做过不少回文,但是依然没有找到解决思路。。。

在其它地方看到一种思路:既然能通过增加一个字符变成回文串,那一定也可以通过删除一个字符变成回文串。用一个循环,每次循环依次删掉一个字符,然后检查新串是否是回文串,看起来简单方便许多。
果然,这样简便多了~~~

AC代码



    /* 
    [编程题-5] 回文串 
    给定一个字符串,问是否能通过添加一个字母将其变为回文串。 
     
    输入描述: 
    一行一个由小写字母构成的字符串,字符串长度小于等于10。 
     
    输出描述: 
    输出答案(YES\NO). 
     
    输入例子: 
    coco 
     
    输出例子: 
    YES 
    */  
      
    #include <iostream>  
    #include <cstdlib>  
    #include <string>  
    #include <algorithm>  
      
    using namespace std;  
      
    /*判断是否为回文串*/  
    bool isPalindrome(const string &str)  
    {  
        string s = str;  
        reverse(s.begin(), s.end());  
        return s == str;  
    }  
      
    int main()  
    {  
        string str;  
        while (cin >> str)  
        {  
            if (str.empty() || str.length() == 1)  
                cout << "YES";  
            else  
            {  
                int len = str.length();  
                string tmp;  
                bool ret = false;  
                for (int i = 0; i < len; ++i)  
                {  
                    tmp = str.substr(0, i) + str.substr(i + 1);  
                    if (isPalindrome(tmp))  
                    {  
                        ret = true;  
                        break;  
                    }//fi  
                }  
                if (ret)  
                    cout << "YES" << endl;  
                else  
                    cout << "NO" << endl;  
            }  
        }//while  
      
        return 0;  
    }  



个人资料
bjchenli
等级:8
文章:260篇
访问:22.0w
排名: 3
推荐圈子
推荐
欢迎关注 “BAT笔试面试” 微信公众号
全栈面试题,你想要的都在这^_^
上一篇: 携程2016研发工程师笔试题
下一篇:华为2016校园招聘上机笔试题
猜你感兴趣的圈子:
IT校招圈
标签: 篮球、btimes、y1、圆桌、atimes、面试题