笔试题-蒲公英云

搜狗2017年校招笔试编程题题目：

在一个圆形上的若干点，点的位置以角度的形式表示，（0-360），输入若干的点的位置，点的距离以劣弧对应角度表示，求距离最远的两个点的角度多大？（输入的数据是从小到大的顺序）
自己写的正确率不是100%
有个同学分享了复杂度O(n)的解法

void farest() {
    int n;
    cin >> n;
    double* angle = new double[n];
    for (int i = 0; i < n; i++) {
        cin >> angle[i];
    }
    double result = 0;
    if (angle[n - 1] - angle[0] <= 180)
        result = angle[n - 1] - angle[0];
    else{
        int l = 0, r = 1;   
        while (l < r) {
            while (r < n&&angle[r] - angle[l] <= 180)//r右移，找到第一个相差大于180的位置
                ++r;
            if (l < r)
                result = max(result, angle[r - 1] - angle[l]);//更新此时的最大角度差
            //l左移，找到第一个相差小于180的位置
            while (l < r&&l < n&&angle[r] - angle[l]>=180)
                ++l;
            if (l > 0 && r < n)
                result = max(result, 360-(angle[r] - angle[l-1]));
        }
    }
    cout << fixed << setprecision(8) << result << endl;
}

迅雷2017年校招笔试编程题：

字符串问题：
输入：1->2->3->4->5
输出：2->1->4->3->5
输入：1->2->3->4
输出：2->1->4->3
注意：数字是int类型
因为Python有split函数，所以我就直接用啦

def reverseStr():
    s = raw_input()
    numbers = map(int,s.split("->"))
    for i in range(1,len(numbers),2):
        numbers[i],numbers[i-1]=numbers[i-1],numbers[i]
    return "->".join(str(i) for i in numbers)

C++，用了之前自己编写split函数

vector<string> splitString(const string& s, const string& c) {
    vector<string> v;
    int start = 0;
    int end = s.find(c);
    while (string::npos != end) {
        v.push_back(s.substr(start, end-start));
        start = end + c.size();
        end = s.find(c,start);
    }
    if (start != s.length())
        v.push_back(s.substr(start));
    return v;
}
void reverseStr() {
    string s;
    cin >> s;
    if (s.size() < 4)
        cout << s << endl;
    string c = "->";
    vector<string> vs = splitString(s, c);
    string res = "";
    for (int i = 0; i < vs.size(); i += 2) {
        if (i + 1 < vs.size()) {
            res += vs[i + 1] + c + vs[i];
            if (i + 1 < vs.size() - 1)
                res += c;
        }
        else
            res += vs[i];
    }
    cout << res << endl;
}

百度2017年校招笔试编程题：

选择题 30道自然语言处理、数据结构。。
问答题 1道自然语言处理不会
设计题 1道推荐手机品牌设计推荐系统照着专利写了
编程题：
1）字符串处理
“W” “E”构成的字符串，W代表西边的房子，E代表东边的房子，字符串划分成部分，要求分错边的房子数最少
动态规划
dp[i]=dp[i-1]-1 s[i]==’W’
dp[i]=dp[i-1]+1s[i]==’E’

void splitHouse() {
    string s;
    cin >> s;
    int W = 0;
    int E = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'W')
            ++W;
        if (s[i] == 'E')
            ++E;
    }
    int* dp = new int[s.size()+1]();
    dp[0] = W;
    dp[s.size()] = E;
    int minC = W < E ? W : E;
    for (int i = 1; i <= s.size(); i++) {
        if (s[i - 1] == 'W')
            dp[i] = dp[i - 1] - 1;
        if (s[i - 1] == 'E')
            dp[i] = dp[i - 1] + 1;
        minC = minC < dp[i] ? minC : dp[i];
    }
    cout << minC << endl;
}

2)连分数
输入两个字符串表示连分数X,Y。判断X,Y的大小关系。
只过了80%应该是浮点数的问题。

double continuedfraction2fraction(string& s)
{
    int i = 1;
    vector<int> a;
    while (i<s.size()) {
        if (isdigit(s[i])) {
            int v = 0;
            while (isdigit(s[i])) {
                v *= 10;
                v += s[i] - '0';
                i++;
            }
            a.push_back(v);
        }
        else
            i++;
    }
    if (a.size() == 1)
        return a[0];
    else {
        int n, d;
        n = a.back();
        d = 1;
        a.pop_back();
        while (a.size() != 0) {
            swap(n, d);
            n = a.back() * d + n;
            a.pop_back();
        }
        //cout << d << " " << n << endl;
        return double(d) / n;
    }
}
void compareTwo() {
    string A, B;
    //cin >> A;
    //cin >> B;
    getline(cin, A);
    getline(cin, B);
    double v1 = continuedfraction2fraction(A);
    double v2 = continuedfraction2fraction(B);
    if (v1 < v2)
        cout << ">" << endl;
    else
        cout << "<" << endl;
}

2018平安科技校园招聘

5道编程题
（1）翻转数字相加
输入： 123 456
输出：975

void reverseNumAdd(){
    string a;
    string b;
    cin>>a>>b；
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    cout<<atoi(a)+atoi(b)<<endl;
}

（2）largest rectangle in histogram 直方图中最大的矩形面积（leetcode原题）
leetcode 84. Largest Rectangle in Histogram
（3）还是leetcode原题
leetcode 127. Word Ladder
（4）求一个无序数组中最小的k个数，保持原有顺序输出
算是剑指offer原题吧，要求尽量O(n)的复杂度

（5）顺时针打印矩阵元素
剑指offer原题，看这里

360校园招聘

很坑啊，选择题30道几乎全是给一段程序求输出结果，字太小，没有缩进，看到崩溃，而且涵盖了C++,java,shell,python各种语言。。。
编程题三道，只来得及做出一道，第二题没写完orz
（1）游乐园问题
一张游乐园的票可以玩t分钟，给一个数组表示n个项目，ai代表第i个项目的时间，求最长可以玩多久。
四舍五入是个0-1背包问题。
除了时间最长的那个项目，共n-1个项目，总时间t-1来求解最优值。
剩余的最后一分钟去玩最长时间的项目。

void playTime() {
    int t, n;
    cin >> n >> t;
    int* time = new int[n]();
    for (int i = 0; i < n; i++)
        cin >> time[i];
    sort(time, time + n);
    vector<vector<int>> dp(n, vector<int>(t, 0));
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <t; j++) {
            if (time[i-1] > j)
                dp[i][j] = dp[i - 1][j];
            else {
                if (dp[i - 1][j - time[i-1]] + time[i-1] > dp[i - 1][j])
                    dp[i][j] = dp[i - 1][j - time[i-1]] + time[i-1];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[n-1][t-1]+time[n-1] << endl;
}

（2）障碍的个数
小明玩一个游戏，如果连续三个障碍物的高度是非递减序列，那么视为一个障碍。
给一个数组A[n]，n比较大。
一共m个查询，[l,r]，要你给出[l,r]间有多少个障碍。m也比较大。

每次查询都去计算一遍是不可行的。
所以我设想的方案是：
首先遍历A数组，找出所有的非递减序列，并存储左右边界
对于m中每个查询L,R，在存储的非递减序列总判断是否有交集，然后障碍个数=交集非递减序列长度-2
大致长这样吧，没得测试了

void queryP() {
    int n;
    scanf("%d", &n);
    int* high = new int[n]();
    for (int i = 0; i < n; i++)
        scanf("%d", high[i]);
    int m;
    scanf("%d", &m);
    int** que = new int*[m];
    for (int i = 0; i < m; i++)
        que[i] = new int[2]();
    for (int i = 0; i < m; i++)
        scanf("%d %d", que[m][0],que[m][1]);
    vector<int>left;
    vector<int>right;
    int l = 0, r = 0;
    int i = 0;
    while(i<n-2) {
        if (high[i] <= high[i + 1])
            ++r;
        else {
            left.push_back(l);
            right.push_back(r);
            l = i + 1;
        }
        ++i;
    }
    int len = left.size();
    for (int i = 0; i < m; i++) {
        int count = 0;
        for (int j = 0; j < len; j++) {
            int l = max(que[i][0], left[j]);
            int r = min(que[i][1], right[j]);
            if (r - l > 2)
                count += r - l;             
        }
        cout << count << endl;
    }
}

（3）大约是个最短路径问题，没细看

TP_LINK

测评 60分钟专业知识
数据结构选择题 3道编程
1）数组第二大的数
一轮比较就可以了

int find_sec_max(int data[], int count) {
    if (count < 2)//数组长度小于2，不存在第2大的
        return -1;
    int first = INT_MIN, second = INT_MIN;
    for (int i = 0; i < count; i++) {
        if (data[i] > first) {
            second = first;
            first = data[i];
        }
        else if (data[i] > second&&data[i] < first)
            second = data[i];
    }
    cout << second << endl;
    return second;
}