滴滴出行2017秋招笔试真题-编程题汇总 - 题解第一题：第二题：餐馆第三题：第四题：末尾0的个数第五题：进制转换

80 阅读 0 评论 53 点赞

我是靠谱客的博主平淡小蘑菇，这篇文章主要介绍滴滴出行2017秋招笔试真题-编程题汇总 - 题解第一题：第二题：餐馆第三题：第四题：末尾0的个数第五题：进制转换，现在分享给大家，希望可以做个参考。

滴滴的题考经典算法比较多啊，两道经典动态规划，一道经典搜索题，一道编程之美原题(听别人说是编程之美上的，自己并不清楚)，两道水题.

题目链接：[点这儿].

第一题：

题目：连续最大和

求数组的连续最大和，太经典了，有dp的做法，也有非dp的线性做法，我用的dp.

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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(n^2)$ 的算法，但是这个题的数据用这样的算法是过不了的，必须优化到 $O(nlogn)$ 。

我们可以想到在 $O(n^2)$ 做法中有个循环是找桌子，顺序查找的，这个时候桌子的容量已经排好序了，那么很容易就可以从这两个条件看出来可以二分查找来优化，于是我用了stl中的multiset.lower_bound来实现这个二分.

后来在评论区看到有人用优先队列做的，其实是一样的，优先队列的查找最大值也是 $O(logn)$ 的，这种做法只不过是 $O(logn * n)$ 也就是说和我的做法只是循环内外层调换了下，有兴趣的可以试试.

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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!=1times 2timescdotstimes ktimescdotstimes n$ 。首先分析下什么时候末尾才会出现0，当 $k$ 中有5这个因子的时候与偶数相乘就会出现0，因此，这个题转化为 $n!$ 中有多少个5因子；

$n! = 1 \times 2 \times \dots \times (5 * 1) \times \dots \times 9 \times (5 * 2) \times \dots 24 \times (5 * 5 * 1) \times \dots (5 * 5 * 5) \times \dots$ $n!=1times 2timescdotstimes (5*1)timescdotstimes9times (5*2)timescdots 24times (5*5*1)timescdots(5*5*5)timescdots$
可以发现有一个5的因子的数是每隔5个就有，有两个5的因子的数是每隔25个就有，……，那么很直接的做法就是下面代码的做法了(每隔5个数有1个5，然后再是每隔25个数再有1个5，累加起来就好了).

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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).

解析：

水题，直接模拟，我的代码应该是最简洁的吧.

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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背包问题，直接写就好了，如果这个题没有这句话”当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 “，那么这就是个多重背包问题了.

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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秋招笔试真题-编程题汇总内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：笔试面试题
浏览次数：80 次浏览
发布日期：2024-10-14 02:25:02
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_10_f3_12__23_gx.html

滴滴出行2017秋招笔试真题-编程题汇总 - 题解第一题：第二题：餐馆第三题：第四题：末尾0的个数第五题：进制转换

第一题：

题目：连续最大和

代码：

第二题：餐馆

题目：

解析：

代码：

第三题：

题目：地下迷宫

解析：

代码：

第四题：末尾0的个数

题目：

解析：

代码：

第五题：进制转换

题目：

解析：

第六题：数字和为sum的方法数

题目：

解析：

代码：

最后

评论列表共有 0 条评论

发表评论取消回复

滴滴出行2017秋招笔试真题-编程题汇总 - 题解第一题：第二题：餐馆第三题：第四题：末尾0的个数第五题：进制转换

第一题：

题目：连续最大和

代码：

第二题：餐馆

题目：

解析：

代码：

第三题：

题目：地下迷宫

解析：

代码：

第四题：末尾0的个数

题目：

解析：

代码：

第五题：进制转换

题目：

解析：

第六题：数字和为sum的方法数

题目：

解析：

代码：

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复