滴滴出行2017秋招笔试真题-编程题汇总
时长:120分钟 总分:100分
145浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 6 |
1.
连续最大和
一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3
输入描述：
输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。输入样例：
3
-1 2 1 输出描述：
所有连续子数组中和最大的值。输出样例
3
2.
餐馆
某餐馆有n张桌子，每张桌子有一个参数：a 可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大
输入描述：
输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 接下来m行，每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。输入样例：
3 5 2 4 2 1 3 3 5 3 7 5 9 1 10 输出描述：
输出一个整数,表示最大的总预计消费金额输出样例
20
3.
地下迷宫
小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。
输入描述：
输入包括n+1行:
第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100)
接下来的n行:
每行m个0或者1,以空格分隔输入样例： 4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 输出描述： 如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示如果不能逃离迷宫,则输出"Can not escape!"。 测试数据保证答案唯一输出样例 [0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]
第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100)
接下来的n行:
每行m个0或者1,以空格分隔输入样例： 4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 输出描述： 如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示如果不能逃离迷宫,则输出"Can not escape!"。 测试数据保证答案唯一输出样例 [0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]
4.
末尾0的个数
输入一个正整数n,求n!(即阶乘)末尾有多少个0？ 比如: n = 10 n! = 3628800,所以答案为2
输入描述：
输入为一行，n(1 &le n &le 1000)输入样例：
10 输出描述：
输出一个整数,即题目所求输出样例
2
5.
进制转换
给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数
输入描述：
输入为一行，M(32位整数)、N(2 &le N &le 16)，以空格隔开。输入样例：
7 2 输出描述：
为每个测试实例输出转换后的数，每个输出占一行。如果N大于9，则对应的数字规则参考16进制（比如，10用A表示，等等）输出样例
111
6.
数字和为sum的方法数
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 输入描述： 输入为两行:
第一行为两个正整数n(1 &le n &le 1000)，sum(1 &le sum &le 1000)
第二行为n个正整数A[i](32位整数)，以空格隔开。输入样例： 5 15 5 5 10 2 3 输出描述： 输出所求的方案数输出样例 4
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 输入描述： 输入为两行:
第一行为两个正整数n(1 &le n &le 1000)，sum(1 &le sum &le 1000)
第二行为n个正整数A[i](32位整数)，以空格隔开。输入样例： 5 15 5 5 10 2 3 输出描述： 输出所求的方案数输出样例 4
