2020.9.6晚腾讯后台笔试题

//1
#include <iostream>
#include <vector>

using namespace std;

int main() {

    vector<int> arr1;
    vector<int> arr2;

    int n, x;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        arr1.push_back(x);
    }

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        arr2.push_back(x);
    }

    int i = 0;
    int j = 0;

    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] == arr2[j]) {
            cout << arr1[i] << " ";
            ++i;
            ++j;
        }
        else if (arr1[i] > arr2[j]) {
            ++i;
        }
        else {
            ++j;
        }
    }
    return 0;
}

//2
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <queue>

using namespace std;

int main() {

    int n, m;
    int x, num;
    int index = 0;
    cin >> n >> m;

    set<int> res;
    queue<int> vals;
    vector<set<int>> elems; //组对应的元素
    map<int, set<int>> ms; //元素所对应的组

    for (int i = 0; i < m; ++i) {
        cin >> x;
        set<int> ts;
        for (int j = 0; j < x; ++j) {
            cin >> num;
            ts.insert(num);
            ms[num].insert(index);
        }
        elems.push_back(ts);
        ++index;
    }

    vals.push(0);
    while (!vals.empty()) {
        int size = vals.size();
        for (int i = 0; i < size; ++i) {
            int cur = vals.front();
            vals.pop();
            for (auto item : ms[cur]) {
                for (auto item_ : elems[item]) {
                    if (res.find(item_) == res.end()) {
                        res.insert(item_);
                        vals.push(item_);
                    }
                }
            }
        }
    }

    cout << res.size();

    return 0;
}

//3
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

struct Node {
    string str;
    int count;
    Node(string &str) : str(str), count(1) {};
};


int main() {

    int n, k;
    int index = 0;
    string str;
    vector<Node> nodes;
    map<string, int> indexs;

    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        cin >> str;
        if (indexs.find(str) == indexs.end()) {
            indexs.insert({str, index++});
            nodes.push_back(Node(str));
        }
        else {
            nodes[indexs[str]].count++;
        }
    }

    sort(nodes.begin(), nodes.end(), [](const Node &n1, const Node &n2) {
        if (n1.count == n2.count) {
            return n1.str < n2.str;
        }
        return n1.count > n2.count;
    });

    for (int i = 0; i < k; ++i) {
        cout << nodes[i].str << " " << nodes[i].count << endl;
    }

    sort(nodes.begin(), nodes.end(), [](const Node &n1, const Node &n2) {
        if (n1.count == n2.count) {
            return n1.str < n2.str;
        }
        return n1.count < n2.count;
    });

    for (int i = 0; i < k; ++i) {
        cout << nodes[i].str << " " << nodes[i].count << endl;
    }

    return 0;
}

//4
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    int n;
    int x;
    int minIndex = -1;
    vector<int> array;
    vector<int> array_;
    cin >> n;
    minIndex = n / 2;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        array.push_back(x);
        array_.push_back(x);
    }

    sort(array_.begin(), array_.end());

    for (int i = 0; i < n; ++i) {
        if (array[i] < array_[minIndex]) {
            cout << array_[minIndex] << endl;
        }
        else {
            cout << array_[minIndex - 1] << endl;
        }
    }

    return 0;
}