欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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。
输入描述:

  • 输入:
  • tt: 表示tt组数据;
  • n1n_1: 表示数列的长度;
  • x1x_1 x2x_2 x3x_3xnx_n
  • y1y_1 y2y_2 y3y_3yny_n
  • ......
  • 输出:
  • 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;
}

实验结果如下:
2020年 暑期实习 字节跳动 后台开发与客户端开发笔试题(第二场 第一题)

未完待续。。。

相关标签: 面试笔试