2024-04-25 17:00 香港大学推荐算法

关注

美团笔试美团笔试题 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：[此代码未进行大量数据的测试，仅供参考]