华为 4.17 笔试AK
暑期实习投到现在大大小小笔试做了好多,基本都只过一题多点,昨天刚刚被xhs虐完,今天做华子的笔试,AK了,头一回AK。算是这段时间找实习处处碰壁唯一能稍微舒缓一下情绪的事情了。
希望华子能给机会
第一题 数据量不大,狠狠暴力。我这做法并不优。不过数据量小
// 4.17 1 import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); HashMap<String,Integer> m = new HashMap<>(); scan.nextLine(); String s = scan.nextLine(); String str = s; String t = rem(str); while(!str.equals(t)){ str = t; t = rem(t); if(t.equals("0")) { str = t; break; } } System.out.print(str); } static String rem(String s){ String[] cards = s.split(" "); int n = cards.length; StringBuilder ans = new StringBuilder(); int i = 0; while(i<n){ String t = cards[i]; int ti = i; int count = 0; while(i<n&&t.equals(cards[i])){ count++; i++; } if(count==3){ continue; }else if(count == 4){ ans.append(t); ans.append(' '); }else{ for (int j = ti; j < i; j++) { ans.append(t); ans.append(' '); } } } if(ans.length() == 0)return "0"; ans.deleteCharAt(ans.length()-1); return ans.toString(); } }
第二题 建树+bfs写的。因为是字符串,建树挺麻烦的,应该还有更好的方法,例如并查集应该能做。
//4.17 2 import java.util.*; public class Main { static Set<String> fa = new HashSet<>(); static HashMap<String, Set<String>> lm = new HashMap<>(); static HashMap<String, int[]> nm = new HashMap<>(); public static void main(String[] args) { Scanner scan = new Scanner(System.in); int M = scan.nextInt(); int N = scan.nextInt(); scan.nextLine(); String[] problems = new String[N]; for (int i = 0; i < N; i++) { problems[i] = scan.nextLine(); } for(String line:problems){ String[] items = line.split(" "); String father = items[1]; String child = items[0]; int lev = Integer.parseInt(items[2]); int num = Integer.parseInt(items[3]); if(father.equals("*")){ fa.add(child); if(!lm.containsKey(child)) lm.put(child,new HashSet<>()); if(!nm.containsKey(child)) nm.put(child,new int[]{0,0}); }else { if(!lm.containsKey(father))lm.put(father,new HashSet<>()); if(!nm.containsKey(father)) nm.put(father,new int[]{0,0}); if(!lm.containsKey(child))lm.put(child,new HashSet<>()); if(!nm.containsKey(child)) nm.put(child,new int[]{0,0}); lm.get(father).add(child); } nm.get(child)[lev]+=num; } int ans = 0; for (String f:fa) { int x = dfs(f); if(x>M)ans++; } System.out.println(ans); } static int dfs(String root){ Set<String> x = lm.get(root); int[] my = nm.get(root); int cost = 5*my[0]+2*my[1]; for(String y:x){ cost += dfs(y); } return cost; } }
第三题 dijkstra,求完再加个索引一块排序。 不过奇怪的是,给的数据n = 1e4,矩阵都1e8了,java竟然只跑180ms,不知道时间是怎么算的
import java.util.*; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[][] g = new int[n][n]; int[] cap = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g[i][j] = scan.nextInt(); } } for (int i = 0; i < n; i++) { cap[i] = scan.nextInt(); } int s = scan.nextInt(); int ms = scan.nextInt(); int[][] res = dijkstra(g,s); Arrays.sort(res,(a,b)->a[0]==b[0]?a[1]-b[1]:a[0]-b[0]); StringBuilder ans = new StringBuilder(); int sum = 0; for (int i = 1; i < n; i++) { sum+=cap[res[i][1]]; ans.append(res[i][1]); ans.append(' '); if(sum>=ms)break; } ans.deleteCharAt(ans.length()-1); System.out.println(ans); } static int[][] dijkstra(int[][]g,int s){ int n = g.length; int[] dist = new int[n]; Arrays.fill(dist,Integer.MAX_VALUE); dist[s] = 0; boolean[] vis = new boolean[n]; for (int i = 0; i < n; i++) { int t = -1; for (int j = 0; j < n; j++) { if(!vis[j]&&(t==-1||(dist[t]>dist[j]))){ t = j; } } vis[t] = true; for (int j = 0; j < n; j++) { if(g[t][j]<0) continue; if(dist[t]+g[t][j]<dist[j]){ dist[j] = dist[t]+g[t][j]; } } } int[][]res = new int[n][2]; for (int i = 0; i < n; i++) { res[i][0] = dist[i]; res[i][1] = i; } return res; } }