网易互娱2020校招游戏研发笔试题
发布日期:2021-09-14 15:33:05
浏览次数:12
分类:技术文章
本文共 4402 字,大约阅读时间需要 14 分钟。
网易互娱游戏研发笔试题
第一题:判断一个数的二进制是否为回文串(AC)
方法一:存成数组之后比较#include#include #include #include using namespace std;int t,x,cnt;int num[111];int main(){ scanf("%d",&t); while(t--){ scanf("%d",&x); cnt=0; memset(num,0,sizeof(num)); while(x) { num[cnt]=x&1; x>>=1; cnt++; } int flag=1; for(int i=0;i
方法二:利用栈和队列
#includeusing namespace std; stack st;queue que;int main() { int _;cin>>_; while(_--) { int x;cin>>x; while(x) { st.push(x%2); que.push(x%2); x>>=1; } bool flag = 0; while(!st.empty()) { if(st.top() != que.front()) flag = 1; st.pop();que.pop(); } if(flag) cout<<"NO\n"; else cout<<"YES\n"; }}
第二题:判断二叉树每层的和是否为递增的0)
这道题没有通过,因为写的时候光顾着去建树了。 说没必要建树。其实建树也只是为了找根节点而已。 根节点可以利用所有的节点都有父亲节点这个特点,那么标记一下每个点有没有父亲节点,唯一一个没有父亲节点的点就是根节点。也可以利用入度为0的特性。把所有的输入index保存下来求和,然后求有入度点的和,相减就可以得到根节点的编号。同样,没有必要去层序遍历,如果遍历到某个点x的深度为d,那么sum[d] += val[x],这样的话只需要正常的DFS,就可以记录下每层的和,d一定不会超过节点数量。
#includeusing namespace std;const int N = 1005;bool du[N];int n;int sum[N],m;struct Node{ int val,l,r; void input(){ scanf("%d%d%d",&val,&l,&r); if(l >=0) du[l] = 1; if(r >=0) du[r] = 1; }}tree[N];void dfs(int now,int dep) { m = max(m,dep); sum[dep] += tree[now].val; if(tree[now].l >=0) dfs(tree[now].l,dep+1); if(tree[now].r >=0) dfs(tree[now].r,dep+1);}int main() { int _;scanf("%d",&_); while(_--) { scanf("%d",&n); memset(du,0,n+1); memset(sum,0,(n+1)<<2); m = 0; for(int i=0;i
第三题:喝咖啡(AC)
#include#include #include #include using namespace std;int t,k,m;int num[33];int ans=0;int main(){ scanf("%d",&t); while(t--) { scanf("%d %d",&k,&m); k++; for(int i=0;i =1) { ans++; temp-=k; } for(int i=1;i =num[i-1]+k) { ans++; temp-=k; } } temp=num[m-1]+k; while(temp<=30) { ans++; temp+=k; } printf("%d\n",ans); }}
第四题:在0-1矩阵中找到最大的十字架(部分通过)
在一个01矩阵中找一个最大的九宫格123
456 789
其中1-9都是等边长的正方形,且1、3、7、9全0,其余部分全1,输出左上和右下的坐标,如果有多个,输出最左上的一个
因为n,m<2000,t<10,而时限是1秒,所以说我们要尝试找出复杂度为n*m*t*log(min(n,m))
的算法 首先的是一个问题,如何判断九宫格合法,即判断1、3、7、9全0,其余部分全1 实际上我们可以一个区域一个区域的去判断,判断这个区域是不是全0或者是全1,如何这个问题就变成了O(1)的时间内求一个矩形区域和的问题,这个问题实际上就是前缀和的二维形式 sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+num[i][j];
但是这样去做的话,复杂度还是t*n*m*min(n,m)
的,还是不够
k*k
的区域全0 2、左上角的2k*2k
的区域除去那k*k
的区域外全1 实际上我们只需要对于一个点找一个以该点为顶点的最大全零正方形,然后以这个正方形的边长x判断另外八个区域就行了 如果我们找的边长小于x。则不满足条件2 如果我们找的边长大于x,则不满足条件1 对于这个边长x的寻找,我们就可以利用二分搜索的方法来确定了,现在整体的复杂度就变成了nmt*log(min(n,m)) 观察这个图形,我们会发现如果一个正方形是合法的,他中间的黑块(x_1,y_1,x_2,y_2)(,他的左上角的点(x_1-1,y_1-1)一定是白色,右下角的点(x_2+1,y_2+1)也一定是白色,那我们可以O(n2)枚举每个点,看看它能不能作为(x_1,y_1)如果可以,找到(x_2,y_2)。去判断一下九个块是不是满足题目给的条件
判断一个块是不是全0或者全1,我们可以预处理出来矩阵前缀和,求子矩阵和可以差分一下,那我们只需要判断一下子矩阵和是不是0或者是不是矩阵面积即可,具体看代码。 (我在枚举9块的那里写得太丑了)#includeusing namespace std;int n,m;char s[2005][2005];int sum[2005][2005];int a,b,c,d,ans=0;bool cal(int a,int b,int c,int d,bool flag) { int tot = sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1]; if(flag == 0) return tot==0; return tot == (c-a+1)*(c-a+1);}void solve(int bx,int by) { int nowx = bx+1,nowy = by+1; while(nowx<=n && nowy <= m && s[nowx][nowy] == '1') nowx++,nowy++; int ex = nowx-1,ey = nowy-1; int lenth = ex - bx + 1; if(!cal(bx,by,ex,ey,1)) return; int aa = bx-lenth,bb = by-lenth,cc = ex+lenth,dd = ey+lenth; ex-=lenth;ey-=lenth;bx-=lenth;by-=lenth; if(bx <1 || by < 1 || !cal(bx,by,ex,ey,0)) return; by+=lenth;ey+=lenth; if(!cal(bx,by,ex,ey,1)) return; by+=lenth;ey+=lenth; if(ey>m || !cal(bx,by,ex,ey,0)) return; bx+=lenth;ex+=lenth; if(!cal(bx,by,ex,ey,1)) return; bx+=lenth;ex+=lenth; if(ex>n || !cal(bx,by,ex,ey,0)) return; by-=lenth;ey-=lenth; if(!cal(bx,by,ex,ey,1)) return; by-=lenth;ey-=lenth; if(!cal(bx,by,ex,ey,0)) return; bx-=lenth;ex-=lenth; if(!cal(bx,by,ex,ey,1)) return; if(ans < lenth) { ans = lenth; a = aa;b = bb;c = cc;d = dd; } else if(ans == lenth) { if(aa
转载地址:https://blog.csdn.net/weixin_42490152/article/details/100982570 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月01日 01时49分57秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
一个深入学习Linux/C/C++的原创技术号
2019-04-27
Linux 用户空间和内核空间
2019-04-27
深入理解cache对写好代码至关重要
2019-04-27
你确定你会使用git commit?
2019-04-27
你会选择深圳还是佛山?
2019-04-27
华为开始对嵌入式开发者下手了!
2019-04-27
生命很短,我用tldr
2019-04-27
FUSE文件系统
2019-04-27
可怕,别人把我MCU固件给反汇编了!
2019-04-27
Modbus协议概念最详细介绍
2019-04-27
在家工作多年再回深圳找工作,会不会丢脸?
2019-04-27
Linux内存寻址方式
2019-04-27
Linux 内核如何描述一个进程?
2019-04-27
FreeRTOS及其应用,万字长文,基础入门
2019-04-27
物联网开发者被疯抢,华为做了什么?
2019-04-27
从中工毕业到年薪30万,我用了2年9个月
2019-04-27
recovery模式下支持ADB连接和串口操作
2019-04-27
买房这件小事
2019-04-27
STM32串口用中断还是用轮询
2019-04-27