美团8.12 后端笔试代码

美团8.12 后端笔试代码

第一题：

给一个x和y，问它们在数组中是否相邻

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> vec(n);
    for(auto &c : vec){
        cin >> c;
    }
    int x, y; cin >> x >> y;
    bool f = false;
    for(int i = 0; i < n-1;i++){
        if(vec[i] == x && vec[i+1] == y || vec[i] == y && vec[i+1] == x){
            f = true;
            break;
        }
    }
    if(f){
            cout << "Yes\n";
        }else{
            cout << "No\n";
        }
}

第二题：

给一个x和y（下标从1到n），以及一个环形数组，数组a[i] 表示第i个点到第i+1个点的距离，求x到y的最短距离

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = int64_t;

int main() {
    int n;
    cin >> n;
    vector<ll> vec(n);
    for (auto& c : vec) {
        cin >> c;
    }
    ll x, y;
    cin >> x >> y;
    x--, y--;
    ll ans = 1e9;
    if (x > y) {
        ll mx1 = 0, mx2 = 0;
        for (int i = y; i < x; i++) {
            mx1 += vec[i];
        }
        for (int i = x; i < n; i++) {
            mx2 += vec[i];
        }
        for (int i = 0; i < y; i++) {
            mx2 += vec[i];
        }
        ans = min(mx1, mx2);
    } else {//x < y
        ll mx1 = 0, mx2 = 0;
        for (int i = x; i < y; i++) {
            mx1 += vec[i];
        }
        for (int i = y; i < n; i++) {
            mx2 += vec[i];
        }
        for (int i = 0; i < x; i++) {
            mx2 += vec[i];
        }
        ans = min(mx1, mx2);
    }

    cout <<ans;
}
// 64 位输出请用 printf("%lld")

第三题

给你一个二维数组，你需要横线切一刀或者竖向切一刀，将其分为两块（记作a,b），

求两数组的和之间的最小的差值（即abs(sumA - sumB）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = int64_t;

ll n, m, s1 = 0, s2 = 0, sum = 0;
const int N = 1e3+10;

ll a[N][N];

int main() {
    //一刀,二维前缀和问题
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
            sum += a[i][j];
        }
    }
    for(int i = 1; i < n; i++){
        a[i][0] += a[i-1][0]; 
    }
    for(int j = 1; j < m; j++){
        a[0][j] += a[0][j-1]; 
    }
    for(int i = 1; i < n; i++){
        for(int j = 1; j < m; j++){
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        }
    }
    ll ans = 1e18;
    for(int i = 0; i < n; i++){
        //ll preSum = a[i][m-2] + a[i-1][m-1] - a[i-1][m-2];
        ans = min(ans, abs(a[i][m-1] - (sum - a[i][m-1])));
    }
    for(int j = 0; j < m; j++){
        //ll preSum = a[n-1][j-1] + a[i-1][j] - 
        ans = min(ans, abs(a[n-1][j] - (sum - a[n-1][j])));
    }


    cout << ans << endl;
}
// 64 位输出请用 printf("%lld")

第四题

给你一个长度为n的字符串，然后你可以将其分为x*y = n的二维数组，当四个方向字符相同时为联通块，求最小的连通块个数

不懂啊，为啥我才60%，盯了40分钟也没看出来，希望有大佬可以给我说一下

好吧已经有大佬点醒我了，我只计算了nm中n<=m的情况

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

using ll = int64_t;

const int N = 1e3+10;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

int nn, mm, ans = 1e9, every = 0;

void dfs(int x, int y, vector<vector<char>> &g, vector<vector<int>> &vis){
    vis[x][y] = 1;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || nx >= nn || ny < 0 || ny >= mm) continue;
        if(vis[nx][ny] == 1 || g[x][y] != g[nx][ny]) continue;
        vis[nx][ny] = 1;
        dfs(nx, ny, g, vis);
    }
}

void calc(vector<vector<char>> &g, vector<vector<int>> &vis){
    for(int i = 0; i < nn; i++){
        for(int j = 0; j < mm; j++){
            if(vis[i][j] == 0) {
                vis[i][j] = 1;
                dfs(i, j, g, vis);
                every ++; 
            }
        }
    }
}

int main() {
    int n; cin >> n;
    string s; cin >> s;
    vector<int> yinzi;
    for(int i = 1; i * i <= n; i++){
        if(n % i == 0) yinzi.push_back(i);
    }
    for(int c : yinzi){
        nn = n / c, mm = c;
        vector<vector<char>> g(nn, vector<char>(mm));
        vector<vector<int>> vis(nn, vector<int>(mm, 0));
        for(int i = 0; i < nn; i++){
            for(int j = 0; j < mm; j++){
                g[i][j] = s[i * mm + j];
                // cout << g[i][j];
            }
            // cout << endl;
        }
        //cout << endl;
        every = 0;
        //memset(vis, 0, sizeof(vis));
        calc(g, vis);
        ans = min(every, ans);
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")

第五题

给你一颗树，一开始节点颜色都是黑色，每个节点都有一个权值，当两个相邻节点的乘积为完全平方数时，你可以将他们同时染成红色，求这颗树中，你最多能得到多少红色节点

print(0) //6.67%