腾讯音乐娱乐2021校招笔试真题

1、三国鼎立

【题目描述】
在n∗m的棋盘格状土地上盘踞着三个国家的若干股势力，上下左右相邻的属于同一个国家的土地被认为是同一股势力。现在想知道，土地上总共有多少股势力？
输入描述：
第一行两个正整数，土地宽n，长m；
接下来一个n∗m个矩阵，今包含'1'、'2'、'3'，表示土地上的国家分布。
输出描述：
一个正整数，势力股数。
备注：
1≤n、w≤100。
输入样例：
4 4
1122
1222
3111
3333
输出样例：
4
说明：
11
1
是1国的一块势力
22
222
是2国一块势力
3
3333
是3国一块势力
111
是1国的另一块势力
总共4块势力

【解题思路】
经典连通块搜索问题，枚举每个点出发往各个方向搜索相连通的位置。

【参考代码】
#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>> &a, int x, int y, int val) {
    if (a[x][y] != val)
        return;
    a[x][y] = 0;
    if (x + 1 < a.size())
        dfs(a, x + 1, y, val);
    if (y + 1 < a[0].size())
        dfs(a, x, y + 1, val);
    if (x - 1 >= 0)
        dfs(a, x - 1, y, val);
    if (y - 1 >= 0)
        dfs(a, x, y - 1, val);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        string line;
        cin >> line;
        for (int j = 0; j < m; ++j)
            a[i][j] = line[j] - '0';
    }

    int res = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 0)
                continue;
            ++res;
            dfs(a, i, j, a[i][j]);
        }

    cout << res << endl;
    return 0;
}

2、狡猾的雇主

【题目描述】
一位雇主想要招聘一个工人，有n个人前来应聘，这位雇主让每个人写下期望的薪资，然后再进行选择。
因为这个雇主十分狡猾，ta会选择期望薪资最低的人，但是这个人可能不是唯一的，为了避免纠纷，ta会选择在没有和其他人提出的期望薪资相同的情况下期望薪资最低的人录用。
求这个最低薪资，如果没有合适的人，则输出-1
输入描述：
第一行一个整数n
第二行n个整数表示n个人提出的期望薪资
保证所有输入的数为正整数且不超过104
输出描述：
一行一个整数表示答案
输入样例1：
3
3 2 1
输出样例1：
1
输入样例2：
6
1 1 4 5 1 4
输出样例2：
5
输入样例3：
3
4 4 4
输出样例3：
-1

【解题思路】
用set判断这个元素是否有多个，省去一点时间，然后有多个的移出有序队列中，最终有序队列poll一个出来就是所需要的了。

【参考代码】
importjava.util.HashSet;
importjava.util.PriorityQueue;
importjava.util.Scanner;
importjava.util.Set;

publicclassMain {
    publicstaticvoidmain(String[] args) {
        Scanner s =newScanner(System.in);
        intx = s.nextInt();
        Set<Integer> set =newHashSet();
        PriorityQueue<Integer> p =newPri