美团笔试(2024.4.9)
第一场实习笔试,A了3.3道,算法还是不太熟
第一题:
简单模拟即可
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in.nextInt(); int count = 0; int[][] array = new int[m][n]; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ array[i][j] = in.nextInt(); } } for(int i = 0; i < m - 1; i++){ for(int j = 0; j < n - 1; j++){ int a = array[i][j]; int b = array[i][j + 1]; int c = array[i + 1][j]; int d = array[i + 1][j + 1]; if(a == b && a == c && a == d && b == c && b == d && c == d){ count++; } } } System.out.println(count); } }
第二题:
贪心策略,按绝对值从小到大排序,优先需绝对值小的,直到和大于等于k
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); long k = scanner.nextLong(); int[] array = new int[n]; int count = 0; long sum = 0; for(int i = 1; i <= n; i++){ array[i - 1] = scanner.nextInt(); } for(int i = 0; i < n; i++){ array[i] = Math.abs(array[i]); } Arrays.sort(array); for(int i = 0; i < n; i++){ if(sum >= k){ break; } sum = sum + array[i]; count++; } if(sum > k){ System.out.println(count - 1); }else{ System.out.println(count); } } }
第三题:
DFS,用HashMap建树,每次DFS时返回该节点所代表子树红、黑节点的存在情况
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Scanner; public class Main { public static HashMap<Integer, List<Integer>> map = new HashMap<>(); public static HashMap<Integer, String> map1 = new HashMap<>(); public static int count = 0; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String n = scanner.nextLine(); String s = scanner.nextLine(); int n1 = Integer.valueOf(n); for(int i = 0; i < s.length(); i++){ map1.put(i + 1, s.substring(i, i + 1)); } for(int i = 0; i < n1 - 1; i++){ int a = scanner.nextInt(); int b = scanner.nextInt(); if(!map.containsKey(a)){ List<Integer> list = new ArrayList<>(); list.add(b); map.put(a, list); }else { List<Integer> list = map.get(a); list.add(b); map.put(a, list); } } boolean[] bb = DFS(1); System.out.println(count); } public static boolean[] DFS(int index){ boolean[] ans = new boolean[2]; if(!map.containsKey(index)){ String s = map1.get(index); if(s.equals("B")){ ans[0] = true; }else{ ans[1] = true; } return ans; } List<Integer> list = map.get(index); String s = map1.get(index); if(s.equals("B")){ ans[0] = true; }else{ ans[1] = true; } boolean left = ans[0]; boolean right = ans[1]; int flag = 0; for(Integer i: list){ boolean[] a = DFS(i); ans[0] = a[0] || ans[0]; ans[1] = a[1] || ans[1]; boolean left1 = left || a[0]; boolean right1 = right || a[1]; if (left1 == true && right1 == true){ flag = 1; } } if(flag == 1){ count++; } return ans; } }
第四题:没做
第五题:暴力DFS,30%
import java.util.HashSet; import java.util.Scanner; public class Main { public static HashSet<String> set = new HashSet<>(); public static int count = 0; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.nextLine(); for (int i = 0; i < s.length(); i++){ if(!set.contains(s.substring(i, i + 1))){ count = (count + 1) % 100000007; set.add(s.substring(i, i + 1)); } DFS(s, s.substring(i, i + 1), i); } System.out.println(count); } public static void DFS(String s, String s1, int index){ if(index >= s.length() - 1){ set.add(s1); return ; } for(int i = index + 1; i < s.length(); i++){ String ss2 = s.substring(i, i + 1); String ss3 = s1.substring(s1.length() - 1, s1.length()); if(!ss2.equals(ss3)){ String s2 = s1 + s.substring(i, i + 1); if(s2.length() > 0 && !set.contains(s2)){ count = (count + 1) % 100000007; } set.add(s2); DFS(s, s2, i); } } } }