关键词:
美团点评2017秋招笔试编程题
1, 大富翁游戏,玩家根据骰子的点数决定走的步数,即骰子点数为1时可以走一步,点数为2时可以走两步,点数为n时可以走n步。求玩家走到第n步(n<=骰子最大点数且是方法的唯一入参)时,总共有多少种投骰子的方法。
题解:
写出前面的几个, 1 -> 1; 2 -> 2 ; 3 -> 4; 4 -> 8; 5 -> 16; 6 -> 32; 可以得到是 二的 n-1 次幂。
#include <cstdio> int main(){ int n, ans; while(scanf("%d", &n) != EOF){ if(n <= 0){ printf("%d ", 0); continue; } ans = 1; for(int i=1; i<n; ++i){ ans *= 2; } printf("%d ", ans); } return 0; }
2, 给你六种面额 1、5、10、20、50、100 元的纸币,假设每种币值的数量都足够多,编写程序求组成N元(N为0~10000的非负整数)的不同组合的个数。
题解:
多一个 bill 选项, 则可以从 该bill 值的 0,1,2 ... j/bill , 这么多种集合。dp[i][j] = dp[i][j] + dp[i-1][j - k*bill[i] ];
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int MAXN = 10000 + 10; const int BILL[6] = {1, 5, 10, 20, 50, 100}; int n, dp[6][MAXN]; void init(){ memset(dp, 0, sizeof(dp)); for(int i=0; i<MAXN; ++i){ dp[0][i] = 1; } for(int i=1; i<6; ++i){ for(int j=1; j<MAXN; ++j){ for(int k=0; k*BILL[i] <= j; ++k){ dp[i][j] += dp[i-1][j - k*BILL[i]]; } } } } int main(){ freopen("in.txt", "r", stdin); init(); while(scanf("%d", &n) != EOF){ printf("%d ", dp[5][n] ); } return 0; }
3, 给定一组非负整数组成的数组h,代表一组柱状图的高度,其中每个柱子的宽度都为1。 在这组柱状图中找到能组成的最大矩形的面积(如图所示)。 入参h为一个整型数组,代表每个柱子的高度,返回面积的值。
题解:
经典的最大矩形问题。使用 left and right array, 分别记录每一个pt可以扩展的最大距离。
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int MAXN = 10000 + 10; int n, tmp, ans, num[MAXN], lft[MAXN], rgt[MAXN]; int main(){ while(scanf("%d", &n) != EOF){ for(int i=1; i<=n; ++i){ scanf("%d", &num[i]); } num[0] = num[n+1] = 0; for(int i=1; i<=n; ++i){ tmp = i - 1; while(num[i] <= num[tmp]){ tmp = lft[tmp] - 1; } lft[i] = tmp + 1; } for(int i=n; i>=1; --i){ tmp = i + 1; while(num[i] <= num[tmp]){ tmp = rgt[tmp] + 1; } rgt[i] = tmp - 1; } ans = 0; for(int i=1; i<=n; ++i){ ans = max(ans, num[i]*(rgt[i] - lft[i] + 1)); } printf("%d ", ans ); } return 0; }
4, 给出两个字符串(可能包含空格),找出其中最长的公共连续子串,输出其长度。
题解:
使用 动态规划。
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int MAXN = 100 + 10; char ch1[MAXN], ch2[MAXN]; int dp[MAXN][MAXN]; int get_line(char *line, int max_size){ int c, len = 0; while( (c = getchar()) != EOF && len < max_size ){ line[len++] = c; if(c == ‘ ‘){ break; } } line[len] = ‘ ‘; return (len - 1); } int main(){ int ans = 0; int len1 = get_line(ch1, MAXN); int len2 = get_line(ch2, MAXN); memset(dp, 0, sizeof(dp)); for(int i=0; i<len1; ++i){ for(int j=0; j<len2; ++j){ if(ch1[i] == ch2[j]){ dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1); ans = max(ans, dp[i+1][j+1]); } } } printf("%d ", ans); return 0; }
美团点评2017秋招笔试编程题——大富翁游戏
大富翁游戏,玩家根据骰子的点数决定走的步数,即骰子点数为1时可以走一步,点数为2时可以走两步,点数为n时可以走n步。求玩家走到第n步(n<=骰子最大点数且是方法的唯一入参)时,总共有多少种投骰子的方法。 输... 查看详情
2017年腾讯秋招软件开发笔试编程题回忆版
2017年腾讯秋招软件开发笔试编程题回忆版(所有题目大致描述如下,并非完整的题目回忆,但意思大致一样)1、又一个魔法城市,城市里面有n个魔法城堡,序号为0,1,2。。。n-1;魔法城堡之间都有路径相连;魔法城堡两两之... 查看详情
字节秋季笔试四道编程题(2021-09-12)(代码片段)
...经全部整理好放在【TechGuide】了,私信公众号回复【美团】或者【百度】即可获得最实时的笔试题解啦!通知:最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了,私信公众号回复... 查看详情
美团点评2017校招笔试真题-算法工程师a
美团点评2017校招笔试真题-算法工程师A1.下面哪种STL容器的实现和其它三个不一样A.setB.dequeC.multimapD.map正确答案:B STL的容器可以分为以下几个大类:1、顺序(序列)容器,有vector,list,deque,string,stack(适配器类),queue(适配器类... 查看详情
运维工程师笔试真题:美团点评2017春招真题
1、数据库索引可以明显提高哪一操作的效率?正确答案:AASELECTBINSERTINTO…VALUES…CUPDATEDDELETE2、数据库:以下哪种锁定方式能提供最佳的并行访问性能?正确答案:DA列锁定B表锁定C块锁定D行锁定3、从DELETE语句中省略WHERE子句,将产... 查看详情
codem美团点评编程竞赛资格赛题
最近看到牛课网美团一个编程竞赛,想着做做看,结果一写就是两天。。真是写不动了啊。话不多说,下面开始我的题解。题目大致还是比较考察思维和代码能力(因为自己代码能力较弱,才会觉得比较考察代码能力吧==!),... 查看详情
两道经典算法题-吉比特2017秋招笔试
阅读目录求素数最大差值回到顶部求素数输入M、N,1<M<N<1000000,求区间[M,N]内的所有素数的个数。素数定义:除了1以外,只能被1和自己整除的自然数称为素数输入描述:两个整数M,N输出描述:区间内素数的个数示例1输入210... 查看详情
2017年9月秋招记录--持续更新
...试,一面跪)六、360(笔试跪)七、大疆(笔试跪)八、美团(笔试等通知)九、百度校招提前批(二面通过,等三面)十、高德地图(等一面)十一、拼多多(三次笔试跪)十二、亚马逊中国(待笔试)十三、51信用卡十四、... 查看详情
链家秋招内推编程笔试题目
参加8.19的链家内推笔试,总体来说题目难度不大,20个选择题还有三道编程题。选择题,里面有两道关于IP地址计算的题目,有点忘了,不知道最后的计算有没有问题,所以还需要复习学习完的知识,因为不知道什么时候就会遇... 查看详情
美团2019秋招后台开发编程题题解(代码片段)
图的遍历题目描述给定一张包含N个点、N-1条边的无向连通图,节点从1到N编号,每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点,那么总路程至少是多少?输入第一行包含一个整数N,1≤N≤105。接下来N-1行,每行... 查看详情
网易2017秋招编程题集合-牛客网
网易2017秋招编程题集合-牛客网 链接:https://www.nowcoder.com/questionTerminal/0147cbd790724bc9ae0b779aaf7c5b50来源:牛客网如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如:{1,2,1},{15,78,78,15... 查看详情
网易秋招校招编程题(代码片段)
网易内推面试凉了,再战正式批笔试,选择和简答略难,编程题很良心,基本就是模拟、找规律,略加思考就能解出来的题目,本弱鸡只有在良心网易笔试才能AK。1、翻转翻转 这题一开始没思路,ac了后两题后再回... 查看详情
网易2017秋招编程题——回文序列解题报告
Problem:https://www.nowcoder.com/question/next?pid=2811407&qid=46573&tid=6015849如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如:{1,2,1},{15,78,78,15},{112}是回文序列,{1,2,2},{15,78,87,51},{112,2,11}不是回文序列。... 查看详情
最新美团点评java团队面试题:大厂高级测试面试题
正文做了3~5年编程开发,你已经积累了不少项目经验,扩宽了技术广度,也许已发力成为团队管理者。到了这个阶段,大家却常有这种感受:感觉自己卡在瓶颈进步缓慢,技术水平很难像早期一样实现大幅... 查看详情
网易2017春招笔试真题编程题集合——分饼干
参考:http://blog.csdn.net/wwe4023/article/details/70171648的内容//importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);Stringline=in.nextLine();intn=Integer. 查看详情
codem美团点评编程大赛初赛a轮
...锻炼下就行了。身体训练时间限制:1秒空间限制:32768K美团外卖的配送员用变速跑的方式进行身体训练。他们训练的方式是:n个人排成一列跑步,前后两人之间相隔u米,每个人正常速度均为v米/秒。当某个配送员排在最后的时... 查看详情
美团点评2017校招研发offer面经
2017届的校招早早就结束了,抽出时间做个记录。职位:后台开发工程师岗位职责:如果你热爱编程,这里给你平台用代码改变世界;如果你乐于挑战,这里有用户和商家五花八门的需求和苛刻的系统运行环境在等待着你;在... 查看详情
网易2017秋招编程题集合_以下代码全部来自牛客网
如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如:{1,2,1},{15,78,78,15},{112}是回文序列, {1,2,2},{15,78,87,51},{112,2,11}不是回文序列。现在给出一个数字序列,允许使用一种转换操作:选择任意两个... 查看详情