2019字节跳动夏令营在线笔试题

2022-11-14 14:21:10 浏览数 (1)

字节跳动夏令营笔试题记录。 题目链接

题目

三个单选,两个填空,有基础知识题、概率题(概率题做的太差,基本不会)

四个编程。

第一题:给一个正整数数组,每两个数之间的距离定义是:a[i] a[j]-(j-i),即a[i] a[j] i-j。其中i和j是两个数的下标,并且j>i。问任意两个数之间的距离最大是多少。 同样是用的暴力,有大佬只取前多少个数计算就过了。。。还是测试数据太水。 思路:如果用暴力的话,当第j位是两个数中的一个时,从第0位到第j-1位挨着试一遍,取最大的就行,这样是n方复杂度。 但是从第0位到第j-1位的过程可以优化,因为0到j-1位中,一定是a[i] i最大的那个数被选中,所以在j进行循环时,就一直记录a[i] i最大的那个。

代码语言:javascript复制
#大佬的精简python
def cal(scores):
	pre=-float('inf')
	res=-float('inf')
	for idx, score in enumerate(scores):
		res=max(res,pre score-idx)
		pre=max(pre,score idx)
	return res

第二题:给一个二维的01地图,1是陆地,计算有多少块陆地(上下左右或斜对角相邻就算联通)。

代码语言:javascript复制
#include <iostream>
#include <vector>

using namespace std;

int row[8]={-1,-1,-1,0,0,1,1,1};
int col[8]={-1,0,1,-1,1,-1,0,1};

void cal(vector<vector<char>> &mapp,int i,int j,int nn,int mm){
    mapp[i][j]='0';
    for(int ii=0;ii<8;ii  ){
        int xx=i row[ii];
        int yy=j col[ii];
        if(xx>=0&&yy>=0&&xx<nn&&yy<mm){
            if(mapp[xx][yy]=='1'){
                cal(mapp,xx,yy,nn,mm);
            }
        }

    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin>>n>>m;

    const int nn=n,mm=m;
    vector<vector<char>> mapp(nn,vector<char>(mm,'0'));

    int tmp=0;
    for(int i=0;i<nn;i  ){
        for(int j=0;j<mm;j  ){
            cin>>tmp;
            mapp[i][j]='0' tmp;
        }
    }

    int sum=0;
    for(int i=0;i<nn;i  ){
        for(int j=0;j<mm;j  ){
            if(mapp[i][j]=='1'){
                sum  ;
                cal(mapp,i,j,nn,mm);
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}

第三题:给定字符串:3$acm#,输出acmacmacm。 输入2�m3%a##,输出acmaaaacmaaa。

代码语言:javascript复制
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    stack<char> sc;
    string str;
    cin>>str;
    for(int i=0;i<str.size();i  ){
        if(str[i]>='0'&&str[i]<='9'){
            sc.push(str[i]);
        }else if(str[i]=='%'){
            sc.push(str[i]);
        }else if(str[i]=='#'){
            string tmp="";
            string now="";
            char t;
            while(sc.top()!='%'){
                t=sc.top(); sc.pop();
                tmp =t;
            }
            reverse(tmp.begin(),tmp.end());
            sc.pop();
            int num=sc.top()-'0'; sc.pop();
            for(int k=0;k<num;k  ){
                now =tmp;
            }
            for(int l=0;l<now.size();l  ){
                sc.push(now[l]);
            }
        }else{
            sc.push(str[i]);
        }

    }
    string res;
        while(!sc.empty()){
            res.push_back(sc.top()); sc.pop();
        }
        reverse(res.begin(),res.end());
        cout<<res<<endl;
    return 0;
}

第四题:没时间做,大佬说是2018 worldfinal的c题。

acm

0 人点赞