字节跳动秋招第三次笔试思路分享
- 数组暴力模拟的，O（n^2）
- BFS，当前状态不在hashmap里面就递归搜索，在了的话看看是不是当前是不是最小，是的话需要更新最小
- 没看懂样例，我变菜了。。
- 始终判断当前长度。
当前长度=1，直接输出前半部分+最后的一个(一定存在)
当前长度=2，拿一位解密，一定可行。判断这两位数连起来能不能解密，不能就退出，能的话长度 -2 递归
From 春招一面挂去了友商的小伙伴...
#字节跳动##笔试题目#
2019-09-08 22:30 已编辑 阿里云_基础产品事业部_高级开发工程师
关注
全部评论
BuckWang
电子科技大学 交易师
同三题，第二题搞了好久，第三题一直没想到正解
周枫宇
广东技术师范大学 Java
大佬，求分享一波代码啊😂
lyswty
南京大学 测试开发
第三题就是个坑比，题意自己没讲清楚，比如如果碰到0破坏了方块那这一步还算不算是一步，连续两次遇到转向破坏了第二个转向，第二个转向还转不转 最后时间不够了，交了卷才写出了能AC的代码- - #include<iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<int> stage;
while (n--) {
string cur;
cin >> cur;
if (cur[0] == '<') stage.emplace_back(-2);
else if (cur[0] == '>') stage.emplace_back(-3);
else stage.emplace_back(stoi(cur));
}
while (q--) {
int start, end;
cin >> start >> end;
vector<int> cur_stage(stage.begin() + start - 1, stage.begin() + end);
int i = 0, score = 0, direct = 1;
bool flag = false;
while (i >= 0 && i < cur_stage.size()) {
if (cur_stage[i] > 0) {
flag = false;
score += cur_stage[i];
cur_stage[i]--;
}
else if (cur_stage[i] != 0){
if (!flag) {
if (cur_stage[i] == -2) direct = 0;
else direct = 1;
flag = true;
}
else cur_stage[i] = 0;
}
if (direct) i++;
else i--;
}
cout << score << endl;
}
system("pause");
return 0;
}
ฉันชอบคุณ
成都东软学院 Java
这个复杂度能过？？ 也太假了 、、、
大黑山程序猿
大连理工大学 后端
大佬能分享一下第二题bfs的代码吗？
BuckWang
电子科技大学 交易师
第二题代码 #include "bits/stdc++.h"
using namespace std;
int x,y,z,target;
struct state{
int x,y,z,step;
}f;
queue<state> q;
bool vis[200+10][200+10][200+10];
int bfs()
{
q.push(f);
vis[f.x][f.y][f.z]=1;
while(q.size())
{
f=q.front(); q.pop();
if(f.x==target||f.y==target||f.z==target) return f.step;
if(f.x<x&&vis[x][f.y][f.z]==0) //x倒满
{
q.push((state){x,f.y,f.z,f.step+1});
vis[x][f.y][f.z]=1;
}
if(f.x&&vis[0][f.y][f.z]==0) //x倒空
{
q.push((state){0,f.y,f.z,f.step+1});
vis[0][f.y][f.z]=1;
}
if(f.y<y&&vis[f.x][y][f.z]==0) //y倒满
{
q.push((state){f.x,y,f.z,f.step+1});
vis[f.x][y][f.z]=1;
}
if(f.y&&vis[f.x][0][f.z]==0) //y倒空
{
q.push((state){f.x,0,f.z,f.step+1});
vis[f.x][0][f.z]=1;
}
if(f.z<z&&vis[f.x][f.y][z]==0) //z倒满
{
q.push((state){f.x,f.y,z,f.step+1});
vis[f.x][f.y][z]=1;
}
if(f.z&&vis[f.x][f.y][0]==0) //z倒空
{
q.push((state){f.x,f.y,0,f.step+1});
vis[f.x][f.y][0]=1;
}
if(f.x>=y-f.y&&vis[f.x-(y-f.y)][y][f.z]==0)//x->y
{
q.push((state){f.x-(y-f.y),y,f.z,f.step+1});
vis[f.x-(y-f.y)][y][f.z]=1;
}
if(f.x<y-f.y&&vis[0][f.x+f.y][f.z]==0)//x->y
{
q.push((state){0,f.x+f.y,f.z,f.step+1});
vis[0][f.x+f.y][f.z]=1;
}
if(f.y>=x-f.x&&vis[x][f.y-(x-f.x)][f.z]==0)//y->x
{
q.push((state){x,f.y-(x-f.x),f.z,f.step+1});
vis[x][f.y-(x-f.x)][f.z]=1;
}
if(f.y<x-f.x&&vis[f.x+f.y][0][f.z]==0)//y->x
{
q.push((state){f.x+f.y,0,f.z,f.step+1});
vis[f.x+f.y][0][f.z]=1;
}
if(f.x>=z-f.z&&vis[f.x-(z-f.z)][f.y][z]==0)//x->z
{
q.push((state){f.x-(z-f.z),f.y,z,f.step+1});
vis[f.x-(z-f.z)][f.y][z]=1;
}
if(f.x<z-f.z&&vis[0][f.y][f.x+f.z]==0)//x->z
{
q.push((state){0,f.y,f.x+f.z,f.step+1});
vis[0][f.y][f.x+f.z]=1;
}
if(f.y>=z-f.z&&vis[f.x][f.y-(z-f.z)][z]==0)//y->z
{
q.push((state){f.x,f.y-(z-f.z),z,f.step+1});
vis[f.x][f.y-(z-f.z)][z]=1;
}
if(f.y<z-f.z&&vis[f.x][0][f.y+f.z]==0)//y->z
{
q.push((state){f.x,0,f.y+f.z,f.step+1});
vis[f.x][0][f.y+f.z]=1;
}
if(f.z>=x-f.x&&vis[x][f.y][f.z-(x-f.x)]==0)//z->x
{
q.push((state){x,f.y,f.z-(x-f.x),f.step+1});
vis[x][f.y][f.z-(x-f.x)]=1;
}
if(f.z<x-f.x&&vis[f.x+f.z][f.y][0]==0)//z->x
{
q.push((state){f.x+f.z,f.y,0,f.step+1});
vis[f.x+f.z][f.y][0]=1;
}
if(f.z>=y-f.y&&vis[f.x][y][f.z-(y-f.y)]==0)//z->y
{
q.push((state){f.x,y,z-(y-f.y),f.step+1});
vis[f.x][y][z-(y-f.y)]=1;
}
if(f.z<y-f.y&&vis[f.x][f.y+f.z][0]==0)//y->z
{
q.push((state){f.x,f.y+f.z,0,f.step+1});
vis[f.x][f.y+f.z][0]=1;
}
}
return -1;
}
int main()
{
scanf("%d%d%d%d",&x,&y,&z,&target);
int ans=bfs();
cout<<ans<<endl;
return 0;
}
相关推荐
投递旷视等公司10个岗位 > 点赞 评论 收藏
分享
