字节跳动夏令营笔试题记录。 题目链接
三个单选,两个填空,有基础知识题、概率题(概率题做的太差,基本不会)
四个编程。
第一题:给一个正整数数组,每两个数之间的距离定义是: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最大的那个。
#大佬的精简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是陆地,计算有多少块陆地(上下左右或斜对角相邻就算联通)。
#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%acm3%a##,输出acmaaaacmaaa。
#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题。