概述
滴滴的题考经典算法比较多啊，两道经典动态规划，一道经典搜索题，一道编程之美原题(听别人说是编程之美上的，自己并不清楚)，两道水题.
题目链接：[点这儿].
第一题：
题目：连续最大和
求数组的连续最大和，太经典了，有
dp的做法，也有非dp的线性做法，我用的dp.
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n;
while (cin >> n) {
vector<int> arr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
vector<LL> dp(n, 0);
LL ans = arr[0];
dp[0] = arr[0];
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1] < 0 ? arr[i] : dp[i - 1] + arr[i];
ans = max(dp[i], ans);
}
cout << ans << endl;
}
return 0;
}
第二题：餐馆
题目：
某餐馆有
n张桌子，每张桌子有一个参数：a可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大
解析：
贪心，很容易想到，消费高并且人数少的客人们是要优先考虑的(店家都喜欢做土豪的生意嘛).其次要把这些客人安排到大小恰到合适的桌子，这样可以接纳更多的客人(避免浪费，店家也最喜欢做这种事).
这样就可以直接写出一个复杂度为 O(n2) 的算法，但是这个题的数据用这样的算法是过不了的，必须优化到 O(nlogn) 。
我们可以想到在 O(n2) 做法中有个循环是找桌子，顺序查找的，这个时候桌子的容量已经排好序了，那么很容易就可以从这两个条件看出来可以二分查找来优化，于是我用了
stl中的multiset.lower_bound来实现这个二分.后来在评论区看到有人用优先队列做的，其实是一样的，优先队列的查找最大值也是 O(logn) 的，这种做法只不过是 O(logn∗n) 也就是说和我的做法只是循环内外层调换了下，有兴趣的可以试试.
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
bool cmp(const pair<int, int> &A, const pair<int, int> &B)
{
if (A.second != B.second)
return A.second > B.second;
return A.first < B.first;
}
int main()
{
int n, m;
while (cin >> n >> m) {
multiset<int> a;
vector<pair<int, int> > arr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a.insert(x);
}
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
arr.emplace_back(x, y);
}
sort(arr.begin(), arr.end(), cmp);
LL ans = 0;
for (int i = 0; i < m && a.size() > 0; i++) {
auto it = a.lower_bound(arr[i].first);
if (it != a.end()) {
ans += arr[i].second;
a.erase(it);
}
}
cout << ans << endl;
}
return 0;
}
第三题：
题目：地下迷宫
小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值
P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。
解析：
bfs，已经写过太多这种题了，不想写这个题解析了，可以看看我博客的其他文章，里面有这类题的解析.
代码：
#include <bits/stdc++.h>
using namespace std;
int dirx[] = {-1, 0, 1, 0};
int diry[] = {0, 1, 0, -1};
int value[] = {3, 1, 0, 1};
struct Node {
int x, y;
int p, pre;
Node(int x, int y, int p, int pre = -1) : x(x), y(y), p(p), pre(pre) {}
bool operator < (const Node &other) const {
return p > other.p;
}
};
int main()
{
int n, m, p;
while (cin >> n >> m >> p) {
vector<vector<int> > mp(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x;
cin >> x;
mp[i][j] = x;
}
}
deque<Node> que;
vector<vector<bool> > used(n, vector<bool>(m, false));
que.push_back(Node(0, 0, p));
int head = 0;
used[0][0] = true;
bool f = false;
int ans = 0;
while (!que.empty()) {
if (que.begin() + head == que.end())
break;
auto now = que[head++];
if (now.x == 0 && now.y == m - 1) {
f = true;
ans = head - 1;
break;
}
for (int i = 0; i < 4; i++) {
int tx = now.x + dirx[i], ty = now.y + diry[i];
int tp = now.p - value[i];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && mp[tx][ty] == 1 && !used[tx][ty] && tp >= 0)
que.push_back(Node(tx, ty, tp, head - 1)), used[tx][ty] = true;
}
}
if (!f) {
cout << "Can not escape!" << endl;
} else {
stack<int> st;
while (que[ans].pre != -1)
st.push(que[ans].pre), ans = que[ans].pre;
while (!st.empty())
cout << "[" << que[st.top()].x << "," << que[st.top()].y << "],", st.pop();
cout << "[" << 0 << "," << m - 1 << "]" << endl;
}
}
return 0;
}
第四题：末尾0的个数
题目：
输入一个正整数
n,求n!(即阶乘)末尾有多少个0？ 比如:n = 10; n! = 3628800,所以答案为2.
解析：
n!=1×2×⋯×k×⋯×n 。首先分析下什么时候末尾才会出现0，当 k 中有5这个因子的时候与偶数相乘就会出现0，因此，这个题转化为
n! 中有多少个5因子；
n!=1×2×⋯×(5∗1)×⋯×9×(5∗2)×⋯24×(5∗5∗1)×⋯(5∗5∗5)×⋯
可以发现有一个5的因子的数是每隔5个就有，有两个5的因子的数是每隔25个就有，……，那么很直接的做法就是下面代码的做法了(每隔5个数有1个5，然后再是每隔25个数再有1个5，累加起来就好了).
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
while (cin >> n) {
int ans = 0;
for (; n; ans += n /= 5);
cout << ans << endl;
}
return 0;
}
第五题：进制转换
题目：
给定一个十进制数
M，以及需要转换的进制数N。将十进制数M转化为N进制数,M(32位整数)、N(2 ≤ N ≤ 16).
解析：
水题，直接模拟，我的代码应该是最简洁的吧.
#include <bits/stdc++.h>
using namespace std;
const char MP[] = "0123456789ABCDEF";
int main()
{
int M, N;
while (cin >> M >> N) {
stack<int> st;
bool f = false;
for (M = M < 0 ? f = true, -M : M; M; st.push(M % N), M /= N);
for (f ? cout << "-", 0 : 0; !st.empty(); cout << MP[st.top()], st.pop());
cout << endl;
}
return 0;
}
第六题：数字和为sum的方法数
题目：
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
解析：
最经典的01背包问题，直接写就好了，如果这个题没有这句话”当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 “，那么这就是个多重背包问题了.
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n, sum;
while (cin >> n >> sum) {
vector<int> arr(n);
for (int i = 0; i < n; i++)
cin >> arr[i];
vector<LL> dp(sum + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int j = sum; j >= arr[i]; j--)
dp[j] += dp[j - arr[i]];
cout << dp[sum] << endl;
}
return 0;
}
最后
以上就是平淡小蘑菇为你收集整理的滴滴出行2017秋招笔试真题-编程题汇总 - 题解第一题：第二题：餐馆第三题：第四题：末尾0的个数第五题：进制转换的全部内容，希望文章能够帮你解决滴滴出行2017秋招笔试真题-编程题汇总 - 题解第一题：第二题：餐馆第三题：第四题：末尾0的个数第五题：进制转换所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复