美团笔试美团笔试题 0413

笔试时间：2024年04月13日

历史笔试传送门：2023秋招笔试合集

第一题

题目：小美的好矩阵

小美定义一个矩阵是“好矩阵”，当且仅当该矩阵所有元素都相同。

现在小美拿到了一个矩阵，她想知道该矩阵有多少2*2的子矩阵是好矩阵？

输入描述

第一行输入两个正整数n和m，代表矩阵的行数和列数。

接下来n行，每行输入m个正整aij，代表小美拿到的矩阵。

1<=n,m<=100

1<=aij<=10^9

输出描述

2*2好子矩阵的数量。

样例输入

3 3

1 2 1

1 1 1

1 1 3

样例输出

1

说明

只有左下角一个好子矩阵。

参考题解

遍历所有的2*2的子矩阵，判断是否满足元素都相等，计数即可。

C++：[此代码未进行大量数据的测试，仅供参考]

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m - 1; ++j) {
            if (matrix[i][j] == matrix[i + 1][j] && matrix[i][j] == matrix[i][j + 1] && matrix[i][j] == matrix[i + 1][j + 1]) {
                ++ans;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                if (matrix[i][j] == matrix[i + 1][j] && matrix[i][j] == matrix[i][j + 1] && matrix[i][j] == matrix[i + 1][j + 1]) {
                    ans += 1;
                }
            }
        }

        System.out.println(ans);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n,m = map(int, input().split())
matrix = []
for i in range(n):
    matrix.append(list(map(int, input().split())))

ans = 0
for i in range(n-1):
    for j in range(m-1):
        if matrix[i][j] == matrix[i+1][j] == matrix[i][j+1] == matrix[i+1][j+1]:
            ans += 1

print(ans)

第二题

题目：小美的元素加减

小美拿到了一个数组，她可以进行最多k次操作，每次操作任选一个元素加1或者减1。

小美希望最终0的数量尽可能多。你能帮帮她吗？

输入描述

第一行输入2个正整n,k，代表数组大小和小美的操作次数。

第二行输n个整ai，代表小美拿到的数组。

1<=n<=10^5

1<=k<=10^14

-10^9<=ai<=10^9

输出描述

一个整数，代表最终0的数量的最大值。

样例输入

4 5

-2 3 -2 9

样例输出

2

说明

对第二个元素操作3次减1，对第三个元素操作2次加1，这样数组变成[-2,0,0,9]。

请注意，方案并不是唯一的。但可以证明，0的数量不会超过2个。

参考题解

将所有的的、元素变为正数，从小的开始去减，直到k不够为止

C++：[此代码未进行大量数据的测试，仅供参考]

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

int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> nums(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
        nums[i] = std::abs(nums[i]);
    }

    std::sort(nums.begin(), nums.end());
    int res = 0;

    for (int i = 0; i < n; ++i) {
        if (k > nums[i]) {
            k -= nums[i];
            ++res;
        } else {
            break;
        }
    }

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

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = Math.abs(scanner.nextInt());
        }

        Arrays.sort(nums);
        int res = 0;

        for (int num : nums) {
            if (k > num) {
                k -= num;
                res++;
            } else {
                break;
            }
        }

        System.out.println(res);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n,k = map(int, input().split())
nums = list(map(int, input().split()))

# 把nums中的负数全部变为正数
for i in range(n):
    nums[i] = abs(nums[i])

nums.sort()
res = 0
for i,num in enumerate(nums):
    if k > num:
        k -= num
        res += 1
    else:
        break

print(res)