2020 字节跳动Byte Camp夏令营 在线笔试
笔试共150min，有单选，多选，填空和编程题。时间安排不当，导致填空题没做。这里只回忆编程题
编程题共四题，前三题通过了，最后一个通过20%，回想一下感觉自己知道最后一问最后一题是在哪出问题了，后面细说。
第一题
给定两维数组，数组中为0或1,1为障碍。给定初始坐标(x,y)，给目的地坐标(X,Y)，每一步可以上下左右移动，求出初始到结束的最短路径。
分析：这个问题是最短路问题，但可以四个方向移动，不太适合用dp，所以这里采用bfs。这里踩了点坑，就是给定的坐标x表示col的下标，y表示row。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int n;
int M, N;
int x,y;
int X,Y;
int A[105][105];
int visited[105][105];
#define PII pair<int,int>
#define fi first
#define se second
int minDist()
{
memset(visited,0,sizeof(visited));
queue<PII> Q;
Q.push({x,y});
visited[x][y]= 1;
if(A[x][y]==1) return -1;
int lv=1;
while(!Q.empty())
{
for(int i=Q.size(); i>0; i--)
{
PII t = Q.front(); Q.pop();
//cout<<t.fi<<" "<<t.se<<";";
if(t.fi == X && t.se==Y) return lv;
if(t.fi>0 && A[t.fi-1][t.se]==0 && visited[t.fi-1][t.se]==0)
{
Q.push({t.fi-1,t.se});
visited[t.fi-1][t.se]=1;
}
if(t.se>0 && A[t.fi][t.se-1]==0 && visited[t.fi][t.se-1]==0)
{
Q.push({t.fi,t.se-1});
visited[t.fi][t.se-1]=1;
}
if(t.fi+1<N && A[t.fi+1][t.se]==0 && visited[t.fi+1][t.se]==0)
{
Q.push({t.fi+1,t.se});
visited[t.fi+1][t.se]=1;
}
if(t.se+1<M && A[t.fi][t.se+1]==0 && visited[t.fi][t.se+1]==0)
{
Q.push({t.fi,t.se+1});
visited[t.fi][t.se+1]=1;
}
}
//cout<<endl;
lv++;
}
return -1;
}
int work()
{
cin>>n;
while(n--)
{
cin>>M>>N;
cin>>y>>x;
cin>>Y>>X;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++)
cin>>A[i][j];
cout<<minDist()<<endl;
}
return 0;
}
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
int main()
{
#ifdef LOCAL
fr("d:/tmp/input");
fw("d:/tmp/output");
#endif
ios::sync_with_stdio (false);
cin.tie (nullptr);
work();
return 0;
}第二题
类似于leetcode上的石子问题。给定n，每次从中减去1到m任意数，不能不减。然后看谁先全部取完。计算先手坑定能赢的次数。对于这种问题，我常用dp来做。遍历先手的所有选项，若有后手必定输的情况，则先手一定赢，否则一定输。但这里n,m都很大，需要用到数学上的一点归纳。这里看后手,采用策略：先手拿x,则后手拿m+1-x,这样一轮下来必定n到 n-(m+1)，若n%(m+1)==0, 则后手必赢。否则，先手取x，使得(n-x)%(m+1)==0, 这时先手采用同样的策略必定能赢。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define PII pair<int,int>
#define fi first
#define se second
int t;
int m;
int n;
bool win()
{
int x = n/m;
if(x%2==0) return true;
else return false;
}
int work()
{
cin>>t;
int ans=0;
while(t--)
{
cin>>n>>m;
if(win()) ans++;
}
cout<<ans<<endl;
return 0;
}
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
int main()
{
#ifdef LOCAL
fr("d:/tmp/input");
fw("d:/tmp/output");
#endif
ios::sync_with_stdio (false);
cin.tie (nullptr);
work();
return 0;
}
第三题
这个问题中，需要将带评论的json字符串去掉评论返回。基本思路是找到“//”的话，跳过直至行尾;找到“/”的话，找下一个"/",并将这里中间的跳过。一个小坑是，对于getline读入的字符串，是不带有回车符的，需要读的时候手动加一下。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define PII pair<int,int>
#define fi first
#define se second
string s;
string line;
string simplify()
{
string ans;
int i=0;
while(i<s.size())
{
if(s[i]=='/')
{
if(i+1<s.size() && s[i+1]=='/')
{
i+=2;
while(i<s.size() && s[i]!='\n') i++;
ans+=s[i++];
}
else if(i+1<s.size() && s[i+1]=='*')
{
i+=2;
while(i+1<s.size() && (s[i]!='*' || s[i+1]!='/')) i++;
//cout<<"-->"<<s[i]<<s[i+1]<<"<---- "<<endl;
i+=2;
}
else
ans+=s[i++];
}
else
ans+=s[i++];
}
return ans;
}
void work()
{
while( getline(cin,line) )
{
s+=line+'\n';
}
cout<<s<<endl;
cout<<simplify();
}
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
int main()
{
#ifdef LOCAL
fr("d:/tmp/input");
fw("d:/tmp/output");
#endif
ios::sync_with_stdio (false);
cin.tie (nullptr);
work();
return 0;
}
第四题
这个问题中给定一个n节点的树，gcd(x,y)表示树的x节点到y节点的一条路径上所有节点的最大公约数，dist(表示路径的长度（节点数）。求gcd(x,y)>1的所有路径中最大的dist(x,y)。n最大20w,范围也是1到20w.
从n个范围来看，最多只能采用nlog(n)的算法了。我最后的想法是，先算所有节点的质因数，然后对给定质因数p, dfs遍历，遍历时保证节点能被p整除。这样对给定p的情况，转化为树中最常路径了，这个问题有点像leetcode的二叉树的直径。我想我可能是下面少加了个1才搞错了。。当然这也只是我的个人事后猜测，也许不是这样，现在也无从验证了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define PII pair<int,int>
#define fi first
#define se second
int n;
int A[200005];
int visited[200005];
unordered_map<int, vector<int>> G;
int ans = 0;
unordered_set<int> primes;
void addP(int x)
{
int i=2;
while(x>1)
{
if(x%i==0)
{
primes.insert(i);
while(x>1 && x%i==0)
x/=i;
}
i++;
}
}
// find max path length
int dfs(int ni, int p)
{
visited[ni] = 1;
if(A[ni]%p!=0) return 0;
priority_queue<int, vector<int>, greater<int>> maxLen;
int maxL=0;
for(int nj : G[ni])
{
if(visited[nj]==0)
{
int t = dfs(nj, p);
maxL = max(t, maxL);
if( maxLen.size()<2 ) maxLen.push(t);
else if( t>maxLen.top() )
{
maxLen.pop();
maxLen.push(t);
}
}
}
ans = max(ans, 1+maxL);
if(maxLen.size()>=2)
{
int t1 = maxLen.top(); maxLen.pop();
int t2 = maxLen.top(); maxLen.pop();
ans = max(ans, 1+t1+t2); //这里比赛时少加了个1
}
return 1+maxL;
}
int maxDist()
{
for(int i=0; i<n; i++)
addP(A[i]);
for(int p : primes)
{
for(int i=0 ;i<n ; i++) visited[i] = 0;
for(int i=0; i<n; i++)
if(visited[i]==0 ) // 比赛时没加isOk
dfs(i, p);
}
return ans;
}
void work()
{
cin>>n;
int a,b;
memset(visited,0,sizeof(visited));
for(int i=0; i<n; i++) cin>>A[i];
for(int i=0; i<n-1; i++)
{
cin>>a>>b;
G[a-1].push_back(b-1);
G[b-1].push_back(a-1);
}
cout<<maxDist()<<endl;
}
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
int main()
{
#ifdef LOCAL
fr("d:/tmp/input");
fw("d:/tmp/output");
#endif
ios::sync_with_stdio (false);
cin.tie (nullptr);
work();
return 0;
}总结
问题其实还不是太难，还是自己太菜了。。。继续加油！
查看7道真题和解析