【挚文集团2025届秋招】Java开发工程师（陌陌业务）-服务端综合-笔试

【挚文集团2025届秋招】Java开发工程师（陌陌业务）-服务端综合-笔试

时间：2024-09-06 19:00

选择

编程

1

代码：

// Description: 【挚文集团2025届秋招】Java开发工程师（陌陌业务）-服务端综合-笔试-编程第一题
// Accept: 100%
// Date: 2024/09/06

#include <iostream>
#include <vector>

using namespace std;

class Node {
public:
    char value;
    vector<Node *> children = vector<Node *>();

    explicit Node(char _value) : value(_value) {}

    ~Node() {
        for (Node *node: children) {
            delete node;
        }
    }

    void addChild(Node *child) {
        if (child && find(children.begin(), children.end(), child) == children.end()) {
            children.emplace_back(child);
        }
    }

    [[nodiscard]] pair<int, vector<Node *>> longestPath() const {
        if (children.empty()) {
            return {1, {const_cast<Node *>(this)}}; // 如果没有子节点，路径长度为 0，路径只有当前节点
        }

        int maxPathLength = 0;
        vector<Node *> longestPathNodes;

        for (const auto &child: children) {
            auto [childPathLength, childPathNodes] = child->longestPath();
            if (childPathLength > maxPathLength) {
                maxPathLength = childPathLength;
                longestPathNodes = move(childPathNodes);
            }
        }

        longestPathNodes.insert(longestPathNodes.begin(), const_cast<Node *>(this)); // 将当前节点添加到路径前面
        return {maxPathLength + 1, longestPathNodes};
    }
};

class Solution {
private:
    vector<Node *> nodes = vector<Node *>(26);
    vector<int> roots = vector<int>(26);
public:
    string LongestBehaviorPath(vector<string> &paths) {
        for (const string &path: paths) {
            for (int i = 0; i < path.size(); i += 3) {
                Node *node = getNodes(path[i]);
                if (i == 0) {
                    if (roots[path[i] - 'A'] == 0) {
                        roots[path[i] - 'A'] = 1;
                    }
                    continue;
                }
                Node *parent = getNodes(path[i - 3]);
                parent->addChild(node);
                roots[path[i] - 'A'] = -1;
            }
        }
        string longestPath;
        for (int i = 0; i < roots.size(); ++i) {
            if (roots[i] != 1) {
                continue;
            }

            auto res = nodes[i]->longestPath().second;
            string longest_path;
            for (int j = 0; j < res.size() - 1; ++j) {
                longest_path += string(1, res[j]->value) + "->";
            }
            longest_path += string(1, res[res.size() - 1]->value);
            if (longest_path.size() > longestPath.size()) {
                longestPath = longest_path;
            }
        }

        return longestPath;
    }

    Node *getNodes(char v) {
        if (nodes[v - 'A'] == nullptr) {
            nodes[v - 'A'] = new Node(v);
        }
        return nodes[v - 'A'];
    }
};

2

代码：

// Description: 【挚文集团2025届秋招】Java开发工程师（陌陌业务）-服务端综合-笔试-编程第二题
// Accept: 100%
// Date: 2024/09/06

#include <iostream>
#include <vector>

using namespace std;

class Solution {

public:
    int mergeSort(vector<long>& record, vector<long>& tmp, int l, int r) {
        if (l >= r) {
            return 0;
        }

        int mid = (l + r) / 2;
        int inv_count = mergeSort(record, tmp, l, mid) + mergeSort(record, tmp, mid + 1, r);
        int i = l, j = mid + 1, pos = l;
        while (i <= mid && j <= r) {
            if (record[i] <= record[j]) {
                tmp[pos] = record[i];
                ++i;
                inv_count += (j - (mid + 1));
            }
            else {
                tmp[pos] = record[j];
                ++j;
            }
            ++pos;
        }
        for (int k = i; k <= mid; ++k) {
            tmp[pos++] = record[k];
            inv_count += (j - (mid + 1));
        }
        for (int k = j; k <= r; ++k) {
            tmp[pos++] = record[k];
        }
        copy(tmp.begin() + l, tmp.begin() + r + 1, record.begin() + l);
        return inv_count;
    }
    int InversionCount(vector<long> &timeSequence) {
        int n = timeSequence.size();
        vector<long> tmp(n);
        return mergeSort(timeSequence, tmp, 0, n - 1);
    }
};