2020年 暑期实习 字节跳动 后台开发与客户端开发笔试题（第二场 完整版）

2020年4月12日，19:00开始考试，笔试时间为两个小时，一共四道编程题。

第一道 编程题

题目描述：存在两个长度相等数列a和b，其中存储的是正整数，判断有没有一个操作能使a数列变化成b数列。
操作：在数列a中选取一个区间a[l] - a[r]，对这个区间中的所有数字加上一个正整数k。
其中，1 <= l <= r <= n，k >= 0。
输入描述：

• 输入：
• $t$t： 表示$t$t组数据；
• $n_1$n1​: 表示数列的长度；
• $x_1$x1​ $x_2$x2​ $x_3$x3​ … $x_n$xn​
• $y_1$y1​ $y_2$y2​ $y_3$y3​ … $y_n$yn​
• $...$...
• 输出：
• YES 或者 NO

实例描述：

输入：

• 2
• 6
• 3 7 1 4 1 2
• 3 7 3 6 3 2
• 5
• 1 1 1 1 1
• 1 2 1 3 1

输出：

• YES
• NO

解题思路：
首先分析题目，核心问题是如何判断这个操作能不能使数列a变化为b。作者首先想到用一个栈来存储数列a，相当于一个指针同时遍历数列a和数列b，如果相同位置上的数列a与数列b相等，则压入栈中。直到遇到不相等的两个元素，第一次遇到则把两个元素的差值放入变量tt中（也就是k值），之后再遇到不相等的两个元素则判断差值是否等于tt，等于则压入栈中，否则不压入栈中。一直一直遍历到数列的最后一个元素。最后判断栈中的元素数目是否与数列a相等，如果相等，则YES，元素数目不相等则NO。
其次，需将输入输出与题目要求匹配。
代码如下：

#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
bool opp(vector<int> a,vector<int> b);//函数声明，指的是操作，Yes返回true，No返回false。
int main() 
{
    int t,n;
    vector<int> a;//数列a
    vector<int> b;//数列b
    int k = 0;
    string dd[100];//string对象存储结果
    int temp_in;

    cin >> t;//输入组数t
   for(int k=0;k<t;k++)
   {
        cin >> n;//数列a的长度
        for (int i = 0; i < n; i++)
        {
            cin >> temp_in;
            a.push_back(temp_in);
        }
        for (int i = 0; i < n; i++)
        {
            cin >> temp_in;
            b.push_back(temp_in);
        }
        if (opp(a, b)==true)
            dd[k] = "YES";
        else
            dd[k] = "NO";
        a.erase(a.begin(),a.end());//矢量删除元素以及内存
        b.erase(b.begin(),b.end());
   }
    for (int i = 0; i < t; i++)
        cout << dd[i]<<endl;
    return 0;
}

bool opp(vector<int> a, vector<int> b) {
    stack<int> ss;//声明栈
    if (a.size() == 0 || b.size() == 0)
        return false;
    int tt;//存差值的变量
    bool tag = true;//哨兵标记，只记录第一次不同元素的差值
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == b[i])//元素相等
        {
            ss.push(a[i]);
        }
        else//元素不相等
        {
            if (tag)//第一次记录差值tt
            {
                tt = b[i] - a[i];
                tag = false;
            }
            if (b[i] == a[i] + tt)//判断后面元素的差值是否等于tt
            {
                ss.push(a[i]);
            }
        }
    }
    if (ss.size() == a.size())
        return true;
    else
        return false;
}

实验结果如下：

未完待续。。。
接上一个博客。

第二道 编程题

题目描述：在你面前从左到右摆放了n根长短不一的木棍，你每次可以折断一根木棍，并将折断后得到的两根木棍一左一右放在原来的位置上（即若原木棍有左邻居，则两根木棍必须放在左邻居的右边，若原来木棍有右邻居则摆放在右邻居的左边，所有木棍保持左右排列）。折断后的两根木棍必须为整数，且它们的长度和为原来木棍的长度，你希望最终木棍从做到右递增不减，那么你需要折断多少次木棍呢？
输入描述：

输入：

n:n根木棍；（1<=n<=3000）

$x_1$x1​、$x_2$x2​、$...$...、$x_n$xn​ （ 1<=L<=3000）

输出：

次数,比如7.

​
实例描述：

输入：
4

3 5 2 1

输出：
7

解题思路：
问题的核心：先找到木棍长度不符合要求的那一根木棍，折断一次的长度应该为多少是最合适的。作者使用矢量来存储这几根木棍，使用迭代器遍历木棍，如果符合递增要求，则迭代器加1；若找到不符合要求的木棍，比如实例中长度为5的木棍。则进行以下操作，判断折断的长度，我选择了左右两根邻居中最短的那一根。这里是长度为2，所以5折断为2和3，将2和3插入到原来的位置。这个时候迭代器重置为第一个元素位置继续遍历，直到遍历到矢量的最后一个元素。用count记录每一次折断。
代码如下：

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

using namespace std;

int break_number(vector<int> a);
void show(int n) { cout << n<<" "; };

int main()
{
	int n;
	int temp_in;
	vector<int> a;
	

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> temp_in;
		a.push_back(temp_in);
	}
	cout << break_number(a) << endl;
	return 0;
}

int break_number(vector<int> a)
{
	vector<int>::iterator p = a.begin();
	vector<int> b;
	int count = 0;
	int p_reduce = 0,p_plus;//记录迭代器的前一个元素和后一个元素
	while (p != (a.end() - 1))
	{
		int x1 = 0, x2 = 0;
		p_plus = *(p + 1);
		if (*p <= p_plus)
		{
			p_reduce = *p;
			p++;
		}
		else if (*p > p_plus)
		{
			x1 = p_plus<p_reduce?p_plus:p_reduce;
			x2 = *p - x1;
			count++;//折断一次
			cout << "折断"<<count<<"次"<<endl;
			b.insert(b.begin(), a.begin(),p);
			b.push_back(x1);
			b.push_back(x2);
			b.insert(b.end(), p + 1, a.end());
			for_each(b.begin(),b.end(),show);
			cout << endl;
			a.assign(b.begin(), b.end());
			b.erase(b.begin(),b.end());
			p = a.begin();
		}
	}
	return count;
}

结果为：

解法粗糙，还望指正。

第三道 编程题

题目描述：有n种无门槛优惠券，每种优惠券有一个面值$a_i$ai​。当一件商品的售价大于等于$a_i$ai​，你可以使用这种优惠卷直接折扣。折扣后的优惠卷不会回收，可以继续使用。现在你想买m件商品，每件商品的价格为$b_i$bi​，请问最少花费多少钱？

输入：
3 4
50 100 200
99 199 200 300
输出：
248

解题思路：使用二分查找到不大于b的优惠卷使用，累加和。其中每个商品只能使用一次优惠卷。

代码如下：

#include <iostream>
#define maxn 3010
#include <algorithm>
#define ll long long
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

int a[maxn], b[maxn];

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < m; ++i) {
		scanf("%d", &b[i]);
	}
	sort(a, a + n);
	ll sum = 0;
	for (int i = 0; i < m; ++i)
	{
		int p = upper_bound(a,a+n,b[i])-a;
		sum = sum + b[i] - a[p - 1];
	}
	printf("%lld\n",sum);
	return 0;
}

运行结果如下：

第四道 编程题

题目描述：
有n栋房子排成一行，假如第i栋房子的高度是正整数a[i]，i属于1到n；小明站在房子的顶部时，可以看到左右高度小于等于当前高度的房子，直到左右出现更高的房子。

输入：
t:t组数据
n：栋房子

输出：
站在每个房子上能看到的数目

实例：

输入：
3
4
1 4 3 3
5
8 2 2 4 6
6
5 8 1 3 2 9
输出：
0 3 1 1
4 1 1 2 3
0 4 0 2 0 5

解题思路：
在输入的数组中，给每个元素给定二个指针，一个向前遍历，一个向后遍历。直到遇到比此元素大的元素截止。用count计数。

代码如下：

#include<bits/stdc++.h>
#define LL long long
#define maxn 100010
#define INF 0x3f3f3f3f
using namespace std;

int opp(vector<int> a, int k, int n);

int main() {
    int t;
    vector<int> a, ans;
    stack<int> st;
    scanf_s("%d", &t);
    while (t--) 
    {
        int n=0;
        scanf_s("%d",&n);
        int temp_a;
        for (int i = 0; i < n; ++i) {
            scanf_s("%d", &temp_a);
            a.push_back(temp_a);
        }
        for (int i = 0; i < n; ++i)
        {
            ans.push_back( opp(a, i,n));
        }
        for (int i = 0; i < n; ++i)
            printf_s("%d ", ans[i]);
        printf("\n");
        a.erase(a.begin(),a.end());
        ans.erase(ans.begin(),ans.end());
    }
    return 0;
}

int opp(vector<int> a, int k,int n) {
    int count = 0;
    vector<int>::iterator p1 =a.begin();
    vector<int>::iterator p2 = a.begin();
    for (int i = 0; i < k; i++)
    {
        p1++; p2++;
    }
    for (int i = 0; i < k;i++)
    {
        if (*(--p1) <= a[k]) {
            count++;
        }
        else {
            break;
        }
    }
    for (int i = 0;i<n-k-1;i++)
    {
        if (*(++p2) <= a[k]&&p2!=a.end()) {
            count++;
        }
        else {
            break;
        }
    }
    return count;
}

实验结果：