美团笔试5道题

#软件开发2024笔面经# 1、n行m列矩阵，求满足1和0数量相等的2x2子矩阵的个数（遍历所有2x2矩阵，四个元素求和判断是否等于2，直接暴力过）

2、长度为n的字符串，删除尽量少的字符，使得字符串不包含长度为偶数的回文字符子串（其实就是删除字符串里连续的字符，只保留一个，最后统一删除的字符个数即可），如aaabc -> abc, abccabc -> abcabc
3、一个长度为n的数组a存储了1-n的所有数字且不重复，数组元素非红即白，只能交换红属性的数组元素，求把数组变为非降序的最小交换次数（其实就是红元素之间交换位置，把数组变为升序的最小交换次数），如果无法办到返回-1（即a[i]为白，且a[i] != i+1）

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表示询问。例如输入：
3
1 2
1 3
2
2 3
1 3
输出
1
500000004
（没思路，求评论区大神）