美团笔试 美团笔试题 0323
笔试时间：2024年03月23日
历史笔试传送门：2023秋招笔试合集
第一题
题目：小美的01矩阵
小美拿到了一个n行m列的矩阵，她想知道该矩阵有多少个 2*2 的子矩形满足 1 和 0 的数量相等？
输入描述
第一行输入两个正整数n,m用空格隔开。
接下来的n行，每行输入一个长度为m的 01 串，用来表示矩阵。
2<=n,m<=100
输出描述
一个整数，代表 1 和 0 的数量相等的 2*2 的子矩形数量。
样例输入
2 3
110
010
样例输出
1
说明
两个 2*2 的子矩形，只有一个是合法的。
参考题解
模拟题。由于子矩阵固定大小是22，因此不需要前缀和，直接模拟即可。只需要保证每一个22的子矩阵的和是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) {
char c;
cin >> c;
matrix[i][j] = c - '0';
}
}
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][j + 1] + matrix[i + 1][j] + matrix[i + 1][j + 1] == 2) {
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) {
String line = scanner.next();
for (int j = 0; j < m; ++j) {
matrix[i][j] = line.charAt(j) - '0';
}
}
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][j + 1] + matrix[i + 1][j] + matrix[i + 1][j + 1] == 2) {
ans++;
}
}
}
System.out.println(ans);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
n,m = map(int, input().split())
matrix = []
for _ in range(n):
matrix.append([int(c) for c in input()])
ans = 0
for i in range(n-1):
for j in range(m-1):
if matrix[i][j]+matrix[i][j+1]+matrix[i+1][j]+matrix[i+1][j+1] == 2:
ans += 1
print(ans)
第二题
题目：小美的回文子串
小美有一个长为 n的字符串s，她希望删除尽可能少的字符，使得字符串不含长度为偶数的回文子串。她想知道她最少要删除几个字符，请你帮帮她吧。
输入描述
输入包含两行。
第一行一个正整数n(1<=n<=10^5)，表示字符串s 的长度。
第二行一个长为n字符串s。
输出描述
输出包含一行一个整数，表示最少删除数量。
补充说明
子串：一个字符串从头或尾删除若干个（也可以不删）得到的结果字符串。
回文：一个字符串正着读和倒着读一样，则该字符串回文。
样例输入一
5
aaabc
样例输出一
2
样例输入二
1
e
样例输出二
0
参考题解
偶数的回文子串等价于：不能有连续的字符相等。只要相邻的相等就要删除。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
string str;
cin >> str;
int ans = 0;
for (int i = 1; i < n; ++i) {
// 不能连续相同
if (str[i] == str[i - 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();
String str = scanner.next();
int ans = 0;
for (int i = 1; i < n; ++i) {
// 不能连续相同
if (str.charAt(i) == str.charAt(i - 1)) {
ans++;
}
}
System.out.println(ans);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
n = int(input())
string = input()
ans = 0
for i,c in enumerate(string):
# 不能连续相同
if i>0 and c==string[i-1]: ans += 1
print(ans)
第三题
题目：小美的元素交换
小美拿到了一个排列，其中初始所有元素都是红色，但有一些元素被染成了白色。小美每次操作可以选择交换任意两个红色元素的位置。她希望操作尽可能少的次数使得数组变成非降序，你能帮帮她吗？
排列是指：一个长度为n的数组，其中 1 到n每个元素恰好出现了一次。
输入描述
第一行输入一个正整数n，代表数组的长度。
第二行输入n个正整数ai，代表数组的元素。
第三行输入一个长度为n的字符串，代表数组元素的染色情况。第i个字符为'R'代表第i个元素被染成红色，为'W'代表初始的白色。
1<=n<=10^5
1<=ai<=n
输出描述
如果无法完成排序，请输出 -1。否则输出一个整数，代表操作的最小次数。
样例输入
4
1 3 2 4
WRRW
样例输出
1
说明：第一次操作，交换 2 和 3，数组变成[1,2,3,4]
参考题解
哈希表。最后的结果要求是[1,2,3,....n]，那么只需要保证下标为i的元素是i+1即可，使用哈希表记录每一个数字的出现位置，不断往后交换即可。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n);
vector<char> colors(n);
unordered_map<int, int> dic;
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
for (int i = 0; i < n; ++i) {
cin >> colors[i];
dic[nums[i]] = i;
}
int ans = 0;
for (int i = 0; i < n; ++i) {
// i->i+1
if (nums[i] == i + 1) continue;
if (colors[i] == 'R' && colors[dic[i + 1]] == 'R') {
ans++;
swap(nums[i], nums[dic[i + 1]]);
dic[nums[i]] = dic[i + 1];
} else {
ans = INT_MAX;
break;
}
}
if (ans == INT_MAX) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
char[] colors = new char[n];
Map<Integer, Integer> dic = new HashMap<>();
for (int i = 0; i < n; ++i) {
nums[i] = scanner.nextInt();
}
String colorInput = scanner.next(); // Read the whole line of colors as a String
for (int i = 0; i < n; ++i) {
colors[i] = colorInput.charAt(i);
dic.put(nums[i], i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
// i->i+1
if (nums[i] == i + 1) continue;
if (colors[i] == 'R' && colors[dic.get(i + 1)] == 'R') {
ans++;
int temp = nums[i];
nums[i] = nums[dic.get(i + 1)];
nums[dic.get(i + 1)] = temp;
dic.put(nums[i], dic.get(i + 1));
} else {
ans = Integer.MAX_VALUE;
break;
}
}
if (ans == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(ans);
}
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
from math import inf n = int(input())
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解，包含python、C++、Java多种语言版本，持续更新中。
投递美团等公司10个岗位