头条的实习笔试题答案

1.问题描述:

多个编辑对一篇论文进行评审,每个编辑找出若干个病句,用[s, t]表示,s代表病句起始位置,t代表病句终止位置。不同编辑找出的病句可能有重叠,如[1,5]和[2,7],可以合并为[1,7]。要求输入每个编辑找出的病句,输出合并后的所有病句,按病句的起始位置从小到大排序输出。


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int> > sentences;        // 病句,将各编辑找出的病句放在一个vector中

bool comp(vector<int> &a, vector<int> &b)
{
    return a[1] < b[1];
}

void main()
{
    int M;                            // 评审数量
    cin >> M;

    // 读取病句
    for (int i = 0; i < M; i++)
    {
        vector<int> sente(3);
        char c;
        do
        {
            sente[0] = 0;            // 辅助标记,0表示未被合并,1表示已被合并
            cin >> sente[1];        // 病句起始位置
            cin.get();                // ","
            cin >> sente[2];        // 病句终止位置
            c = cin.get();            // ";"
            sentences.push_back(sente);
        } while (c == ';');
    }

    // 合并病句
    for (int i = 0; i < sentences.size(); i++)
    {
        for (int j = i + 1; j < sentences.size(); j++)
        {

            if ((sentences[i][2] >= sentences[j][1] && sentences[i][2] <= sentences[j][2])
                || (sentences[j][2] >= sentences[i][1] && sentences[j][2] <= sentences[i][2]))    // 需要合并
            {
                sentences[j][1] = sentences[i][1] < sentences[j][1] ? sentences[i][1] : sentences[j][1];    // 新的起始
                sentences[j][2] = sentences[i][2] > sentences[j][2] ? sentences[i][2] : sentences[j][2];    // 新的终止
                sentences[i][0] = 1;        // 标记为已合并
                break;                        // 跳到下一个病句
            }
        }
    }

    // 排序
    sort(sentences.begin(), sentences.end(), comp);

    // 输出
    int flag = 0;                // 标记第一个病句
    for (int i = 0; i < sentences.size(); i++)
    {
        if (!sentences[i][0])
        {
            if (flag)
                cout << ";";
            flag = 1;
            cout << sentences[i][1] << "," << sentences[i][2];
        }
    }
    cin.get();
}



2.题目:

给 n 个正整数 a_1,…,a_n, 将 n 个数顺序排成一列后分割成 m 段,每一段的分数被记为这段内所有数的和,该次分割的分数被记为 m 段分数的最大值。问所有分割方案中分割分数的最小值是多少?

输入描述:
第一行依次给出正整数 n, m。
第二行依次给出n 个正整数 a1,…,an

示例:

输入
5 3
1 4 2 3 5
输出
5
说明
分割成 1 4 | 2 3 | 5 的时候三段的分数都为 5,得到分割分数的最小值。

备注:
对于所有的数据,有 m <= n <= 100000,0 <= ai
<= 2^39。


#include <iostream>
using namespace std;

int Judge(int data[], int sum, int m, int n);
int Binary_Search(int data[], int left, int right, int m, int n);


int main()
{
    int n = 0, m = 0;
    cin >> n >> m;

    int data[n];
    int max_num = 0;
    int sum = 0;

    int i = 0;

    for(i = 0; i < n ; i++)
    {
        cin >> data[i];
        if (data[i] > max_num)
        {
            max_num = data[i];
        }
        sum += data[i];
    }

    cout << Binary_Search(data, max_num, sum, m, n);

    return 0;
}

int Binary_Search(int data[], int left, int right, int m, int n)
{
    int mid = 0;

    while (left < right)
    {
        mid = left + (right - left) / 2;
        if (Judge(data, mid, m, n)) //满足划分,继续向左寻找
        {
            right = mid;//不减是因为无法确保减一之后的数是否满足划分
        }
        else    //不满足划分,继续向右寻找
        {
            left = mid + 1;
        }
    }

    return left;
}

int Judge(int data[], int mid, int m, int n)
{
    int cnt = 0;
    int sum = 0;

    for (int i = 0; i < n; i++)
    {
        if (sum + data[i] > mid) //累加和大于 mid,进行一次划分
        {
            sum = data[i];
            cnt++;
            if (cnt > m - 1)    //划分次数大于 m-1,不满足划分
            {
                return 0;
            }
        }
        else
        {
            sum += data[i];
        }
    }

    return 1;
}

3.给出红、黄、蓝三种颜色的盒子各有若干个(a、b、c),将其排成一排,要求相同颜色的盒子不能相邻,直到盒子用完或者没有合适颜色的盒子为止,输出总共有多少种排列方式?

例如:输入 红:a=1, 黄:b=1,蓝:c=1

输出为:6

例如:输入 红:a=1, 黄:b=2,蓝:c=1

输出为:8


#include<iostream>
#include<Windows.h>
using namespace std;

//判断是否有匹配颜色的盒子
bool isNomatch(int a, int b, int c, char r)
{
    switch (r)
    {
    case 'a':
        if (b > 0 || c > 0) return false;
        break;
    case 'b':
        if (a > 0 || c > 0) return false;
        break;
    case 'c':
        if (a > 0 || b > 0) return false;
        break;
    }
    return true;
}

//在第一个确定为红、黄、蓝盒子的情况下统计排列种类
void arrage(int a, int b, int c, char r, int &sortCount)
{
    if (a + b + c == 0 || isNomatch(a, b, c, r))
    {
        sortCount++;
        return;
    }
    if (a > 0 && r != 'a')
    {
        a--;
        arrage(a, b, c, 'a', sortCount);
        a++;
    }
    if (b > 0 && r != 'b')
    {
        b--;
        arrage(a, b, c, 'b', sortCount);
        b++;
    }
    if (c > 0 && r != 'c')
    {
        c--;
        arrage(a, b, c, 'c', sortCount);
        c++;
    }
}

//分别对第一个盒子为红、黄、蓝盒子的情况进程遍历累加其总共的排列数
int calculateCount(int a, int b, int c)
{
    int count = 0;
    char r;
    int t[3] = { a,b,c };
    for (int i = 0, r = 'a'; i < 3; i++, r++)
    {
        t[i]--;
        arrage(t[0], t[1], t[2], r, count);
        t[i]++;
    }
    return count;
}

//运行代码
int main()
{
    cout << calculateCount(1,2,1) << endl;
    system("pause");
    return 0;
}
---------本文结束,谢谢关注---------

本文标题:头条的实习笔试题答案

文章作者:XQ

发布时间:2019年01月09日 - 16:01

最后更新:2019年01月09日 - 16:01

原始链接:https://nblog.xq99.me/category/头条的实习笔试题答案/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

坚持原创技术分享,您的支持将鼓励我继续创作!