2020年 暑期实习 字节跳动 后台开发与客户端开发笔试题(第二场 第一题)
程序员文章站
2024-03-26 12:03:11
...
2020年4月12日,19:00开始考试,笔试时间为两个小时,一共四道编程题。
第一道 编程题
题目描述:存在两个长度相等数列a和b,其中存储的是正整数,判断有没有一个操作能使a数列变化成b数列。
操作:在数列a中选取一个区间a[l] - a[r],对这个区间中的所有数字加上一个正整数k。
其中,1 <= l <= r <= n,k >= 0。
输入描述:
- 输入:
- : 表示组数据;
- : 表示数列的长度;
- …
- …
- 输出:
- 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;
}
实验结果如下:
未完待续。。。