9.22 拼多多服务端开发笔试4题（CPP版本）

1.图书馆找书（100%）前缀+二分

#include <bits/stdc++.h>

using namespace std;

int main () {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        a[i] += a[i - 1];
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int b;
        cin >> b;
        //二分法来了
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (a[mid] < b) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        cout << l + 1 << endl;
    }
    return 0;
}

2.走不同颜色的路有多少条（100%）简单DFS

#include <bits/stdc++.h>

using namespace std;

set<int> st;
int nums = 0;

void dfs(int i, int j, int& n, int& m, vector<vector<int>>& tb) {
    if (st.find(tb[i][j]) != st.end()) return;
    else st.insert(tb[i][j]);
    if (i == n - 1 && j == m - 1) nums++;
    if (i < n - 1) dfs(i + 1, j, n, m, tb);
    if (j < m - 1) dfs(i, j + 1, n, m, tb);
    st.erase(tb[i][j]);
}

int main () {
    int T;
    cin >> T;
    for (int p = 0; p < T; p++) {
        int n, m, k;
        cin >> n >> m >> k;
        st.clear();
        nums = 0;
        vector<vector<int>> tab(n, vector<int> (m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> tab[i][j];
            }
        }
        dfs(0, 0, n, m, tab);
        cout << nums << endl;
    }
    return 0;
}

3.前面有多少矮的（100%）笨办法做的，听说可以用栈

#include <bits/stdc++.h>

using namespace std; 

int main () {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    vector<int> sortIdx(n, -1);
    for (int i = n - 1; i >= 0; i--) {
        int lowNum = h[i];
        for (int t = 0; t < n; t++) {
            if (lowNum == 0 && sortIdx[t] == -1) {
                sortIdx[t] = i;
                break;
            }
            if (sortIdx[t] == -1) lowNum--;
        }
    }
    for (int i = 0; i < n; i++) {
        h[sortIdx[i]] = i + 1;
    }
    for (int i = 0; i < n; i++) cout << h[i] << " ";
    cout << endl;
    return 0;
}

4.N步M个棋子，求移动后坐标（超时20%）听说可以移动棋盘法

#include <bits/stdc++.h>

using namespace std;

int main () {
    int T;
    cin >> T;
    for (int p = 0; p < T; p++) {
        int N, M, X, Y;
        cin >> N >> M >> X >> Y;
        vector<int> steps(N);
        int totalX = 0;
        int totalY = 0;
        int minX = 0;
        int minY = 0;
        int maxX = 0;
        int maxY = 0;
        for (int k = 0; k < N; k++) cin >> steps[k];
        for (int k = 0; k < N; k++) {
            if (steps[k] == 1) {
                totalX--;
                if (totalX < minX) minX = totalX;
            } else if (steps[k] == 2) {
                totalY--;
                if (totalY < minY) minY = totalY;
            } else if (steps[k] == 3) {
                totalX++;
                if (totalX > maxX) maxX = totalX;
            } else if (steps[k] == 4) {
                totalY++;
                if (totalY > maxY) maxY = totalY;
            }
        }
        for (int i = 0; i < M; i++) {
            int x, y;
            cin >> x >> y;
            int fixL = 0, fixR = 0, fixT = 0, fixB = 0;
            if ((x + minX >= 1) && (x + maxX <= X) && (y + minY >= 1) && (y + maxY <= Y)) {
                x += totalX;
                y += totalY;
            } else {
                for (int k = 0; k < N; k++) {
                    if (steps[k] == 1) {
                        if (x > 1) x--;
                    } else if (steps[k] == 2) {
                        if (y > 1) y--;
                    } else if (steps[k] == 3) {
                        if (x < X) x++;
                    } else if (steps[k] == 4) {
                        if (y < Y) y++;
                    }
                }
            }
            cout << x << " " << y<< endl;
        }
    }
    return 0;
}

挣扎半天没救的解法

#include <bits/stdc++.h>

using namespace std;

int main () {
    int T;
    cin >> T;
    for (int p = 0; p < T; p++) {
        int N, M, X, Y;
        cin >> N >> M >> X >> Y;
        vector<int> steps(N);
        int totalX = 0;
        int totalY = 0;
        int minX = 0;
        int minY = 0;
        int maxX = 0;
        int maxY = 0;
        for (int k = 0; k < N; k++) cin >> steps[k];
        for (int k = 0; k < N; k++) {
            if (steps[k] == 1) {
                totalX--;
                if (totalX < minX) minX = totalX;
            } else if (steps[k] == 2) {
                totalY--;
                if (totalY < minY) minY = totalY;
            } else if (steps[k] == 3) {
                totalX++;
                if (totalX > maxX) maxX = totalX;
            } else if (steps[k] == 4) {
                totalY++;
                if (totalY > maxY) maxY = totalY;
            }
        }
        for (int i = 0; i < M; i++) {
            int x, y;
            cin >> x >> y;
            int fixL = 0, fixR = 0, fixT = 0, fixB = 0;
            if (x + minX < 1) fixL = 1 - x - minX;
            if (x + maxX > X) fixR = X - x - maxX;
            if (y + minY < 1) fixT = 1 - y - minY;
            if (y + maxY > Y) fixB = Y - y - minY;

            x += totalX + fixL + fixR;
            x = max(0, min(X, x));
            y += totalY + fixT + fixB;
            y = max(0, min(Y, y));
            cout << x << " " << y<< endl;
        }
    }
    return 0;
}

#拼多多##笔经#

全部评论

推荐最新楼层

南七技校

楼主

蔚来_IC_底层软件开发工程师

不想做了，面完大疆再看看微软就行了

点赞回复分享

发布于 2021-09-22 17:10

菜鸟邦邦

北京化工大学 C++

int main() { int n; cin >> n; vector<pair<int, int>> nums; for (int i = 1; i <= n; i++) { int num; cin >> num; nums.emplace_back(num, i); } sort(nums.begin(), nums.end(), [](auto& a, auto& b) { return a.first == b.first ? a.second > b.second:a.first < b.first; }); vector<int> res(n); for (int i = 0; i < n; i++) { res[nums[i].second - 1] = i + 1; } cout << res[0]; for (int i = 1; i < n; i++) { cout << " " << res[i]; } cout << endl; return 0; }

点赞回复分享

发布于 2021-09-22 17:10

菜鸟邦邦

北京化工大学 C++

第三题这样有什么问题吗？测试用例能过，提交不行

点赞回复分享

发布于 2021-09-22 17:11

MFresh

深圳大学后端

public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = Integer.parseInt(in.nextLine().trim()); String[] str = in.nextLine().trim().split(" "); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.parseInt(str[i]); } int[] res = new int[n]; boolean[] marked = new boolean[n]; int cnt = 0; while (cnt < n) { // 从后往前找，遇到 0 就标记为最矮的，否则就减 1 (代表前面为 0 的已经被标记，剔除) for (int i = arr.length - 1; i >= 0; i--) { if (marked[i]) continue; if (arr[i] == 0) { res[i] = ++cnt; marked[i] = true; break; } else { arr[i] -= 1; } } } for (int i = 0; i < res.length; i++) { System.out.print(res[i] + " "); } }

点赞回复分享

发布于 2021-09-22 17:50

孟寻

中山大学 C++

第三题老哥思路是什么有点看不懂

点赞回复分享

发布于 2021-09-22 18:44