猿辅导笔试编程题思路(算法岗位)

代码写的不好别喷啊。。。思路就是这么个思路。。
第一题代码别看了,写的不是很优美,就不贴出来了。。

第一题(100):
根据括号递归,里层括号的输出是外层的输入

第二题(100):
一个记忆化搜索,dp[i][j][k]代表从i,j出发用k次机会最远的距离

if(mat[x][y] < mat[nx][ny]) dp[x][y][kk] = max(dp[x][y][kk], dfs(nx, ny, kk) + 1);
if(mat[x][y] >= mat[nx][ny] && kk > 0) dp[x][y][kk] = max(dp[x][y][kk], dfs(nx, ny, kk - 1) + 1);
在dfs函数最开始的时候判断一下,如果dp[x][y][k]不等于初始值的时候直接返回就可以了
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#define MAXN 505
#define MAXK 11
using namespace std;
int dp[MAXN][MAXN][MAXK];
int mat[MAXN][MAXN];
int n, m, k, ans;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int dfs(int x, int y, int kk)
{  if(dp[x][y][kk] != -1) return dp[x][y][kk];  dp[x][y][kk] = 1;  for(int i = 0; i < 4; i++)  {  int nx = x + dx[i];  int ny = y + dy[i];  if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  if(mat[x][y] < mat[nx][ny]) dp[x][y][kk] = max(dp[x][y][kk], dfs(nx, ny, kk) + 1);  if(mat[x][y] >= mat[nx][ny] && kk > 0) dp[x][y][kk] = max(dp[x][y][kk], dfs(nx, ny, kk - 1) + 1);  }  return dp[x][y][kk];
}
int main()
{  while(scanf("%d%d%d", &n, &m, &k) != EOF)  {  ans = 0;  for(int i = 0; i < n; i++)  {  for(int j = 0; j < m; j++)  {  scanf("%d", &mat[i][j]);  }  }  memset(dp, -1, sizeof(dp));  for(int i = 0; i < n; i++)  {  for(int j = 0; j < m; j++)  {  dp[i][j][k] = dfs(i, j, k);  ans = max(ans, dp[i][j][k]);  }  }  printf("%d\n", ans);  }  return 0;
}


第三题(70):
dp,二维dp,第二维表示当前i状态下是否在手里,转移方程:
dp[i][1] = dp[i - 1][0];
dp[i][0] = ( ( (dp[i - 1][1] * (LL)(k - 1)) % MOD )+ ( (dp[i - 1][0] * (LL)(k - 2)) % MOD) ) % MOD;
感觉过100,可能需要矩阵快速幂优化一下。。但时间不够了
====================================================
想了一下第三题过100%的解法,
[ai]
[bi]
ai是当前第i回合在我手里的状态,bi是当前回合在其他人手里的状态
则有ai=bi-1  bi=(k-1)*ai-1+(k-2)*bi-1
[ai] = [0       1][ai-1]
[bi] = [k-1 k-2][bi-1]
那么就可以对这个矩阵求一个快速幂模就可以了。。

#猿辅导##笔试题目##题解#
全部评论
大佬可以发代码吗?
点赞 回复 分享
发布于 2019-08-03 21:01
可以观摩你的代码嘛,感谢
点赞 回复 分享
发布于 2019-09-14 21:45
笔试的题型分布是什么样的?
点赞 回复 分享
发布于 2019-08-22 17:21
请问第二题里如果初始化dp全都是-1, if(dp[x][y][kk] != -1) return dp[x][y][kk]; 这个条件如何达成,即dfs搜索到最开始的位置
点赞 回复 分享
发布于 2019-08-21 17:23
大佬我24号笔试,可以分享我你的代码嘛,感谢
点赞 回复 分享
发布于 2019-08-17 15:24
大佬我24号笔试,可以分享我你的代码嘛,感激涕零😁😁😁😁😁
点赞 回复 分享
发布于 2019-08-16 16:49
牛逼,大师球
点赞 回复 分享
发布于 2019-08-08 15:09
(LL) 是什么?
点赞 回复 分享
发布于 2019-08-06 13:28
想看第三题的代码,求分享,感觉为啥不是按顺序传递呢?做笔试的时候调了好久都没调出来
点赞 回复 分享
发布于 2019-08-06 10:27
能分享一下最后一题的代码吗?
点赞 回复 分享
发布于 2019-08-04 15:32
大佬求最后一题代码
点赞 回复 分享
发布于 2019-08-03 23:44
求第一题代码
点赞 回复 分享
发布于 2019-08-03 23:34
**666
点赞 回复 分享
发布于 2019-08-03 22:36
巨佬
点赞 回复 分享
发布于 2019-08-03 22:05
大佬你是怎么训练这个思维的啊,我根本就想不到,就不知道怎么下手
点赞 回复 分享
发布于 2019-08-03 21:52
可以看看题意吗😂 没参加但是想做做看
点赞 回复 分享
发布于 2019-08-03 21:39
强烈想要第一题的代码,可以发一下吗?🤣🤣🤣😂😂😂
点赞 回复 分享
发布于 2019-08-03 21:23
可以看一下第二题的dp代码吗
点赞 回复 分享
发布于 2019-08-03 21:14
大佬
点赞 回复 分享
发布于 2019-08-03 21:12
活捉一枚大佬
点赞 回复 分享
发布于 2019-08-03 21:01

相关推荐

不愿透露姓名的神秘牛友
07-03 17:37
点赞 评论 收藏
分享
废物一个0offer:认真的吗二本本科找人工智能岗位
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
9
53
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务