美团 24 年春招笔试(含前三道个人题解)-03.23

共计 2659 个字符，预计需要花费 7 分钟才能阅读完成。

第一题

1、n 行 m 列矩阵，求满足 1 和 0 数量相等的 2x2 子矩阵的个数。

输入示例

2 3
110
010

输出示例

1

说明

两个 2*2 的子矩形，只有一个是合法的。

思路

 枚举 + 模拟。子矩阵固定 2*2，只需枚举 i[0,n-2]和 j[0,m-2]即可。

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        String[] matrix = new String[n];
        for(int i=0;i<n;i++){
            if(scan.hasNext()){
                matrix[i] = scan.next();
            }
        }
        int res = 0;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<m-1;j++){
                if(checkSubMatrix(i,j,matrix)){
                    res ++;
                }
            }
        }
        System.out.println(res);

    }

    private static boolean checkSubMatrix(int i, int j, String[] matrix){
        int sum = 0;
        sum += matrix[i].charAt(j) - '0';
        sum += matrix[i].charAt(j+1) - '0';
        sum += matrix[i+1].charAt(j) - '0';
        sum += matrix[i+1].charAt(j+1) - '0';
        return sum == 2;
    }
}

第二题

2、长度为 n 的字符串，删除尽量少的字符，使得字符串不包含长度为偶数的回文字符子串。

输入示例

5
aaabc

输出示例

2

说明

删除变为 abc即可，删除了 2 个字符。

思路

 要求字符串不包含长度为偶数的回文子串说明字符串中不存在连续相等的字符。因此只需遍历一遍，删除相邻相同字符串并统计个数即可。

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String string = scanner.next();

        int ans = 0;
        for (int i = 1; i < n; i++) {
            char c = string.charAt(i);
            // 不能连续相同
            if (c == string.charAt(i - 1)) {
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

第三题

3、一个长度为 n 的数组 a 存储了 1-n 的所有数字且不重复，数组元素非红即白，只能交换红属性的数组元素，求把数组变为非降序的最小交换次数。

如果无法完成排序，请输出 -1。否则输出一个整数，代表操作的最小次数。

输入示例

4
1 3 2 4
WRRW

输出示例

1

说明

第一次操作，交换 2 和 3，数组变成[1,2,3,4]

思路

 长度为 n 的数组存储 1~n 的数字并且不重复，目的是求将该数组变为非降序（即升序）的最小交换次数。因为无论怎么换，我们最终的目的都是将其变为升序的，因此nums[i] = i + 1。我们只需要保证下标为 i 的元素是 i+1 即可，使用哈希表记录每一个数字的出现位置，不断往后交换。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        char[] colors = scanner.next().toCharArray();
        // mp[nums[i]]=i -> 数字nums[i]对应的下标位置
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(nums[i], i);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            // nums[i] == i + 1 下标0~n-1对应1~n
            if (nums[i] == i + 1) {
                continue;
            }
            // 如果当前下标位置的颜色为红色并且当前下标对应的数字的颜色也是红色，那么就可以将它们进行调换
            if (colors[i] == 'R' && colors[map.get(i + 1)] == 'R') {
                ans++;
                int temp = nums[i];
                nums[i] = nums[map.get(i + 1)];
                nums[map.get(i + 1)] = temp;
                map.put(temp, map.get(i + 1));
            } else {
                ans = Integer.MAX_VALUE;
                break;
            }
        }
        if (ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }

}

第四题

4、定义字符串权值为字符串长度*字符串包含的字符种类，例如“aabc”的权值为 4*3=12。现在给定一个字符串 s 和权值 k，求可以切割的最大连续子串数量，且满足每个子串的权重>=k。字符串给出形式：例如 s =“a(2)b(2)a(3)”等价于“aabbaaa”

应该是贪心或动态规划

第五题

5、n 个节点的树，起点为 s 节点，终点为 t 节点，每次随机选择一条之前没有走过的路，求到达 t 的概率。针对每次询问求出能到达 t 的概率对 10^9+7 取模后的结果。如果最后答案为分数 a/b，其中 a 与 b 互质，那么输出 x，使得 bx 与 a 同余，模为 10^9+7，且 0≤x ＜ 10^9+7（可以证明 x 唯一）。第一行输入 n 表示树节点个数，后跟 n-1 行，每行两个整数 1≤u,v≤n 表示树上的边，接下来一行 1≤q≤2x10^5 表示询问次数，后跟 q 行，每行两个整数 1≤s,t≤n 表示询问。

没见人写出来。

 代码并未进行大量的测试用例测试，仅供参考。