2021.7.21
今晚华为的面试题，帮同学做的，记录一下
说实话还挺难的，基本都算中等题，而且光看题就得看半天
链路可靠性
思路
建图，dfs
我这里是用的哈希表，加数组的形式，也差不多
import java.util.*;public class Main{ static class Node{ int target; int weight; public Node(int t, int w){ target = t; weight = w; } } static Map<Integer, ArrayList<Node>> map; public static void main(String[] args){ Scanner sc = new Scanner(System.in); map = new HashMap<>(); while(sc.hasNext()){ int start = sc.nextInt(); int target = sc.nextInt(); int weight = sc.nextInt(); Node node = new Node(target, weight); ArrayList<Node> list = map.getOrDefault(start, new ArrayList<>()); list.add(node); map.put(start, list); } int res = 0; Main main = new Main(); for(int key : map.keySet()){ int len = main.dfs(key, 0); res = Math.max(res, len); } System.out.println(res); } public int dfs(int start, int len){ if(!map.containsKey(start)) { return len; } int res = 0; ArrayList<Node> list = map.get(start); for(int i = 0; i < list.size(); i++){ Node node = list.get(i); int t = node.target; int w = node.weight; res = Math.max(res, dfs(t,len + w)); } return res; }} 同时运行的出租车数量
思路
就是遍历时间，看这个时间有没有车经过
注意路是环形的，两地经过的时间要处理一下
import java.util.*;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); int[][] person = new int[K][3]; int res = 0; for(int i = 0; i < K; i++){ person[i][0] = sc.nextInt(); person[i][1] = sc.nextInt(); person[i][2] = sc.nextInt(); } for(int i = 0; i <= 1000; i++){ int temp = 0; for(int j = 0; j < K; j++){ int pos1 = person[j][1]; int pos2 = person[j][2]; int diff = Math.abs(pos1 - pos2); int num = Math.min(diff, N - diff); if(person[j][0] <= i && i < person[j][0] + num * 5) temp++; } res = Math.max(res, temp); } System.out.println(res); }} 生产调度
思路
第二三次周赛时候的题吧，忘记了，第三道，当时有bug没发现
思路就是两个优先队列，一个放工序，一个放设备（记录用完的时间）
然后遍历时间，根据当前是否有设备，是否到达了完工时间来处理逻辑
import java.util.*;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); int[][] shebei = new int[K][2]; PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[1] == b[1] ? b[0] - a[0] : a[1] - b[1])); for(int i = 0; i < K; i++){ shebei[i][0] = sc.nextInt(); shebei[i][1] = sc.nextInt(); pq.offer(shebei[i]); } int res = 0; PriorityQueue<Integer> time = new PriorityQueue<>(); int num = 0; //遍历时间 for(int i = 0; i < 1000 * 1000; i++) { if(pq.isEmpty()) break; //如果到点了，机器停止 while(!time.isEmpty() && time.peek() == i){ time.poll(); } //如果机器没有空闲,剪枝 if(time.size() == N){ i = time.peek() - 1; } while(!pq.isEmpty() && time.size() < N){ int[] temp = pq.poll(); time.offer(i + temp[0]); res = Math.max(res, i + temp[0]); } } System.out.println(res); }}
算是做了一次笔试题吧，三道基本也都能写出来…
啥也不说了，还是去看八股了