当前位置: 首页 > 面试经验 >

美团8.12笔试 后端开发

优质
小牛编辑
82浏览
2023-08-16

美团8.12笔试 后端开发

第一题:排列判断是否相邻

有一个排列,一共有n个数,还有两个数x和y,请你判断x和y在排列中是否相邻,是则输出”Yes”,不是则输出”No”

1 ≤ n ≤ 1e5

输入n,x,y

注意判断x的前后有没有y即可;

第二题:环形公路最短距离

现有一条环形公路,总共有n个站点,a[i]代表第i个站点与第i+1个站点之间的距离,特殊的,a[n]表示第n个站点与第一个站点之间的距离。出发地为x,目的地为y,请你求出x到y的最短距离

1 ≤ n ≤ 1e5

1 ≤ a[i] ≤ 1e9

注意a[i]要用long int,判断正着走与反着走哪个小输出哪个

第三题:切蛋糕

现有一个n*m的蛋糕矩阵a,a[i][j]代表一小块蛋糕的美味度,现在小美要和一个好朋友分享蛋糕,因此需要把这个蛋糕矩阵切成两半,并且要求分成两半后的两块蛋糕的美味度尽可能相等,即求出分成两半后的两块蛋糕的abs(s1 - s2)的最小值,s1代表第一块蛋糕的美味度,s2代表第二块蛋糕的美味度。要求:必须保证每一小块蛋糕的完整性(即不能斜着切,如果把整个大蛋糕正着放)

1 ≤ n , m≤ 1e3

1 ≤ a[i][j] ≤ 1e5

因为只能横切或者竖切,那每次输入数组的时候保存下来每一行 以及 每一列的美味度之和,再遍历每次切的abs最小值判断即可。

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int main(){
    int n, m, temp;
    cin>>n>>m;
    vector<int> row(n,0);
    vector<int> col(m,0);
    int sum_all = 0;
    for(int i = 0; i < n; i++){
        int sum = 0;
        for(int j = 0; j < m; j++){
            cin>>temp;
            sum += temp;
            col[j] += temp;
            sum_all += temp;
        }
        row[i] = sum;
    }
    int half_row = 0, half_col = 0;
    int min_row = INT_MAX, min_col = INT_MAX;
    for(int i=0; i<n; i++){
        half_row +=row[i];
        int minus_row = abs(sum_all - 2*half_row);
        min_row = min(min_row,minus_row);
    }
    for(int i=0; i<m; i++){
        half_col += col[i];
        int minus_col = abs(sum_all - 2*half_col);
        min_col = min(min_col,minus_col);
    }
    int res = min(min_col,min_row);
    cout<<res<<endl;
    return 0;
}

第四题:字符串平铺成矩阵

一个长为n的字符串s,将其重组为一个二维矩阵,二维数组长宽x,y,那么x*y = n。

矩阵的权重定义为矩阵连通块的数量。定义上下左右四个方向相邻相同字符是连通的,希望矩阵的权重最小,求最小权重值。

比如 abcbbcbcc,可建立矩阵3*3 abc,bbc,bcc,此时权重为3。

可以遍历出所有x,y的组合,并对每一组x,y分别进行dfs,来计算矩阵的权重

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
void dfs(const string& s, int width, int height, int row, int col, vector<vector<bool>>& visited) {
    if (row < 0 || row >= height || col < 0 || col >= width || visited[row][col]) {
        return;
    }
    visited[row][col] = true;
    char currentChar = s[row * width + col];

    if (row > 0 && s[(row - 1) * width + col] == currentChar) {
        dfs(s, width, height, row - 1, col, visited);
    }
    if (row < height - 1 && s[(row + 1) * width + col] == currentChar) {
        dfs(s, width, height, row + 1, col, visited);
    }
    if (col > 0 && s[row * width + col - 1] == currentChar) {
        dfs(s, width, height, row, col - 1, visited);
    }
    if (col < width - 1 && s[row * width + col + 1] == currentChar) {
        dfs(s, width, height, row, col + 1, visited);
    }
}

int computeWeight(const string& s, int width, int height) {
    int weight = 0;
    vector<vector<bool>> visited(height, vector<bool>(width, false));

    for (int i = 0; i < height; ++i) {
        for (int j = 0; j < width; ++j) {
            if (!visited[i][j]) {
                dfs(s, width, height, i, j, visited);
                weight++;
            }
        }
    }
    return weight;
}

int minWeight(string s, int n) {
        int minWeight = INT_MAX;
        // 遍历不同的宽高组合
        for (int width = 1; width <= n; ++width) {
            for (int height = 1; height <= n; ++height) {
                if (width * height == n) {
                    int weight = computeWeight(s, width, height);
                    minWeight = min(minWeight, weight);
                }
            }
        }
        return minWeight;
    }

int main() {
    int n;
    string s;
    cin>>n;
    cin>>s;
    int result = minWeight(s, n);
    cout << "Minimum weight: " << result << endl;
    return 0;
}

第五题 染色问题

一个树,每个节点一个值,初始每个节点都是白色,每次操作可以选择一组相邻节点,如果两个节点都是白色并且乘积为完全平方数,可以把这两个节点同时染红,问最多能染红多少个节点

输入第一行n个节点,第二行每个节点权值,后面n-1行每行两个数代表这两个节点中间有边相连

思路:树形dp

#美团信息集散地##美团嵌入式#
 类似资料: