字节8.21客户端笔试题解
第一题:
贪心,摩天轮转动一次相当于可以多上4个人,题目要求转动尽可能少,那么自然想到尽可能的让互为朋友的4个人上去同一个摩天轮。
由于必须至少两个朋友一起上同一个摩天轮,如果余下了1个,那么就不能上4个,只能上3个,剩下2个人可以和其他2个人拼;如果余下了2个,那么也可以和其他2个人拼;如果剩3个,那么就拼不了了。
代码(这题代码忘记存了,实现的话就取一下模,然后记录剩下了多少个两人组就好了)
第二题:
问有哪些点到达不了终点,其实就是总点数减去能到达终点的点数。直接从终点出发进行BFS,按照题目模拟即可。
代码(C++):
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second const int maxn = 1e+5; vector<string> mp; int dir[4][2] = {1,0,0,1,-1,0,0,-1}; char op[4] = {'U','L','D','R'}; map<int,map<int,int> > vis; int main() { ios::sync_with_stdio(0); int n,m; cin>>n>>m; string s; for(int i = 0; i < n; i++) { cin>>s; mp.push_back(s); } int ex = -1,ey = -1; queue<pii> q; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { if(mp[i][j] == 'O') ex = i,ey = j; } q.push({ex,ey}); vis[ex][ey] = 1; int ans = n*m; while(!q.empty()) { auto t = q.front(); q.pop(); ans--; for(int i = 0; i < 4; i++) { int x = t.fi+dir[i][0],y = t.se+dir[i][1]; if(x>=0&&y>=0&&x<n&&y<m&&!vis[x][y]&&(mp[x][y]==op[i]||mp[x][y]=='.')) { vis[x][y] = 1; q.push({x,y}); } } } printf("%d\n",ans); return 0; }
第三题:
题目有点难懂,其实把一个花括号当成一个整体,那么这题就是一个简单的小正则匹配,记忆化搜索就好了。
代码(C++)(这里把花括号直接换成一个题目中没有的字符@,简化逻辑):
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second const int maxn = 105; string s,ns = ""; int n,m,ok = 0,must = 0; string p; bool vis[105][105]; //p1->s,p2->p void dfs(int p1,int p2,int must) { if(vis[p1][p2]) return; // cout<<p1<<" "<<p2<<endl; vis[p1][p2] = 1; if(p2 >= m && !must) { ok = 1; return; } if(ok) return; if(p1 >= n) return; if(p2 >= m) return; if(ns[p1] == '@') { dfs(p1+1,p2,must); dfs(p1,p2+1,must); } else if(ns[p1] == p[p2]) dfs(p1+1,p2+1,must-1); } int main() { ios::sync_with_stdio(0); int T; cin>>T; cin>>s; n = s.length(); int flg = 0,tt = 0; for(int i = 0; i < n; i++) { if(s[i] == '{') { flg = 1; ns += '@'; tt++; continue; } else if(s[i] == '}') { flg = 0; continue; } if(!flg) ns += s[i]; } // cout<<ns<<endl; must = ns.length()-tt; n = ns.length(); // cout<<ns<<endl; while(T--) { cin>>p; m = p.length(); memset(vis,0,sizeof(vis)); ok = 0; dfs(0,0,must); puts(ok?"True":"False"); } return 0; }
第四题:
思维题,不难发现只有把1移动到字符串的头部或者尾部的时候(头部/尾部一开始不为1),答案才会减少,移动到头部相当于少了1,尾部相当于少了10,那么自然优先移动到尾部。
代码(C++):
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second const int maxn = 1e+5; int main() { ios::sync_with_stdio(0); int T; cin>>T; while(T--) { int n,k; cin>>n>>k; string s; cin>>s; int ans = 0,fi = -1,la = -1; for(int i = 0; i < n-1; i++) ans += (s[i]-'0')*10+s[i+1]-'0'; for(int i = 0; i < n; i++) { if(fi == -1 && s[i] == '1') fi = i; if(s[i] == '1') la = i; } if(la != -1 && la != n-1 && n-1-la <= k) { k -= n-1-la; ans -= 10; } if(fi != -1 && fi != 0 && fi <= k) ans--; cout<<ans<<'\n'; } return 0; }#字节跳动##字节笔试##题解##字节23秋招笔试太难了吧##原来字节劝退的只是我,罢了罢了#