美团 8.12 后端&数开&软件 笔试
只做出了三道半，最后一道参考这个大佬的思路https://www.nowcoder.com/discuss/519845427500285952
第一题：小美的排列询问
直接用map
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Map<Integer,Integer> map = new HashMap<>();
for(int i = 1; i <= n; i++) {
int t = sc.nextInt();
map.put(t, i);
}
int x = sc.nextInt();
int y = sc.nextInt();
if(Math.abs(map.get(x)-map.get(y))==1){
System.out.println("Yes");
}else {
System.out.println("No");
}
}
第二题：小美走公路
前缀和，注意数据范围，开long
最开始，用了两个for循环一个做输入，一个生成前缀和，结果只过了一半数据，猜测可能超时。后面优化只用一个循环同时完成输入和前缀和生成。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] sum = new long[n+1];
//前缀和
for(int i = 1; i <= n; i++) {
sum[i] = sc.nextLong();
sum[i] += sum[i-1];
}
int x = sc.nextInt();
int y = sc.nextInt();
//取绝对值
long res1 = Math.abs(sum[y-1]-sum[x-1]);
long res2 = sum[n] -res1;
long res = Math.min(res1,res2);
System.out.println(res);
}
第三题：小美的蛋糕切割
最开始这道题想复杂了，以为要二分，后来发现可以用二维前缀和解决，注意数据范围，要开long
定义：p[i][j] 记录 a 中子矩阵 [0, 0, i-1, j-1] 的元素和
static int[][] a;
static long[][] p;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
a = new int[n][m];
p = new long[n + 1][m + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
}
}
// 构造二维前缀和 m行 n列
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i - 1][j - 1];
}
}
long res = Integer.MAX_VALUE;
for(int i= 1;i <= n;i++){ //横切 0,0 i,m
res= Math.min(res,Math.abs(p[i][m]- (p[n][m]-p[i][m])));
}
for(int j= 1;j <= m;j++){ //竖切 0,0, n,j
res= Math.min(res,Math.abs(p[n][j]- (p[n][m]-p[n][j])));
}
System.out.println(res);
}
第四题：小美将字符串平铺成矩阵
暴力穷举因数，然后DFS搜索联通区域
static int n, m, k;
//二维映射到一维 :n*m 二维坐标为(i,j)则一维坐标为i*m+j
static char[] s;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
//DFS搜索
public static void dfs(int x, int y, boolean[][] st) {
int t = x * m + y;
st[x][y] = true;
for (int i = 0; i < 4; i++) {
int a = x + dx[i];
int b = y + dy[i];
int z = a * m + b;
if (a < 0 || a >= n || b < 0 || b >= m || st[a][b] || s[z] != s[t]){
continue;
}
dfs(a, b, st);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
k = sc.nextInt();
s = sc.next().toCharArray();
int res = k;
for (int i = 1; i <= k; i++) {
if (k % i != 0) { // 必须要可以整除
continue;
}
n = i;
m = k / i;
boolean[][] st = new boolean[n][m];
int cnt = 0;
for (int j = 0; j < n; j++) {
for (int l = 0; l < m; l++) {
if (!st[j][l]) {
cnt++;
dfs(j, l, st);
}
}
}
res = Math.min(res, cnt);
}
System.out.println(res);
}
第五题：小美将字符串平铺成矩阵
树形DP，太难想了，参考这个大佬的思路https://www.nowcoder.com/discuss/519845427500285952
每个节点可以染色或者不染色。设dp[u][1]表示将u节点染色 dp[u][0]表示不将u节点染色 染色的话，则必须只选择一个可以染色的孩子。dp[u][1]=dp[u][0]-max(dp[v][0],dp[v][1])+dp[v][0]+2 不染色的话，则孩子染色和不染色都可以，取最大值即可。dp[u][0]+=max(dp[v][1],dp[v][0])
static int n, ans;
static long[] a;
static int[][] dp;
static List<Integer>[] e;
// 判断两数乘积是不是 完全平方数
public static boolean x2(long x, long y) {
long d = (long) Math.sqrt(x * y);
return d * d == x * y;
}
public static void dfs(int u, int fa) {
for (int v : e[u]) {
if (v == fa) {
continue;
}
dfs(v, u);
dp[u][0] += Math.max(dp[v][1], dp[v][0]);
}
for (int v : e[u]) {
if (v == fa || !x2(a[u], a[v])) {
continue;
}
dp[u][1] = Math.max(dp[u][1], dp[u][0] - Math.max(dp[v][0], dp[v][1]) + 2 + dp[v][0]);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
a = new long[n + 1];
for (int i = 1; i <= n; i++){
a[i] = sc.nextLong();
}
e = new List[n + 1];
for (int i = 1; i <= n; i++){
e[i] = new ArrayList<>();
}
//邻接矩阵 构造树
for (int i = 1; i < n; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
e[u].add(v);
e[v].add(u);
}
dp = new int[n + 1][2];
dfs(1, 0);
ans = Math.max(dp[1][0], dp[1][1]);
System.out.println(ans);
}
