华为OD刷题C卷 - 每日刷题34（内存冷热标记，电脑病毒感染）

本文主要是介绍华为OD刷题C卷 - 每日刷题34（内存冷热标记，电脑病毒感染），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、（内存冷热标记）：

这段代码是解决“内存冷热标记”的问题。它提供了一个Java类Main，其中包含main方法和markHot方法，用于根据内存页的访问频次进行冷热标记。

main方法首先读取访存序列的记录条数N，然后读取访存序列和热内存的频次阈值T。接着，调用markHot方法进行冷热内存页的标记。

markHot方法使用一个HashMap来统计每个内存页框号的访问频次。然后，移除所有访问频次小于阈值T的页框号。使用Java 8的流（Stream）和Lambda表达式对剩余的页框号按照访问频次降序、页框号升序进行排序，并打印出每个热内存页框号及其访问频次。

2、（电脑病毒感染）：

这段代码是解决“电脑病毒感染”的问题。它提供了一个Java类Main，其中包含main方法，用于计算感染整个网络内所有电脑所需的最短时间。

main方法首先读取电脑的总数N和网络连接的数量M。然后，读取每条网络连接的详细信息，包括连接的起点、终点和感染时间，构建一个邻接表表示网络。接着，读取源点（病毒起始的电脑编号）。

使用Dijkstra算法的思想，通过优先队列（PriorityQueue）和已访问标记数组（visited）来找到从源点到网络内所有电脑的最短感染时间。最后，遍历最短感染时间数组dist，找到最大值，即为感染所有电脑所需的最短时间。如果存在无法感染的电脑，则返回-1。

package OD363;import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;/*** @description 内存冷热标记* @level 4*//*** 题目描述* <p>* 现代计算机系统中通常存在多级的存储设备，针对海量 workload 的优化的一种思路是将热点内存页优先放到快速存储层级，这就需要对内存页进行冷热标记。* 一种典型的方案是基于内存页的访问频次进行标记，如果统计窗口内访问次数大于等于设定阈值，则认为是热内存页，否则是冷内存页。* 对于统计窗口内跟踪到的访存序列和阈值，现在需要实现基于频次的冷热标记。内存页使用页框号作为标识。* <p>* 输入描述* 第一行输入为 N，表示访存序列的记录条数，0 < N ≤ 10000。* <p>* 第二行为访存序列，空格分隔的 N 个内存页框号，页面号范围 0 ~ 65535，同一个页框号可能重复出现，出现的次数即为对应框号的频次。* <p>* 第三行为热内存的频次阈值 T，正整数范围 1 ≤ T ≤ 10000。* <p>* 输出描述* 第一行输出标记为热内存的内存页个数，如果没有被标记的热内存页，则输出 0 。* <p>* 如果第一行 > 0，则接下来按照访问频次降序输出内存页框号，一行一个，频次一样的页框号，页框号小的排前面。*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//序列条数int n = Integer.parseInt(sc.nextLine());//在下一行有nextLine()时可以有效防止换行符//访问序列int[] list = new int[n];for (int i = 0; i < n; i++) {list[i] = sc.nextInt();}//阈值int t = sc.nextInt();if (n == 0) {System.out.println(0);} else {markHot(list, t);}}//标记过热内存的个数public static void markHot(int[] list, int t) {//存放次数Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < list.length; i++) {map.put(list[i], map.getOrDefault(list[i], 0) + 1);}//把小于阈值的给移出map.keySet().removeIf(s -> map.get(s) < t);//输出大于阈值的个数即当前map的大小System.out.println(map.size());//排序：先按频次降序，频次相同按页码升序map.entrySet().stream().sorted((a, b) ->a.getValue() == b.getValue() ? a.getKey() - b.getKey() : b.getValue() - a.getValue()).forEach(s -> System.out.println(s.getKey()));超过阈值的个数//int count = 0;存放超过阈值的页面 <页框号,频次>//Map<Integer, Integer> hot = new TreeMap<>();遍历map//for (int key : map.keySet()) {//    if (map.get(key) >= t) {//        count++;//        hot.put(key, map.get(key));//    }//}如果没有超过阈值的，返回0//if (count == 0) {//    System.out.println(0);//} else {//    System.out.println(count);//    //超过阈值的:先按频次降序，频次一样的按页框号升序//    hot.keySet().stream().sorted((a, b) -> {//        //频次不同，则按频次降序//        if (hot.get(a) != hot.get(b)) {//            return hot.get(b) - hot.get(a);//        }else {//            //频次相同，按页框号升序//            return a - b;//        }//    }).forEach(s -> System.out.println(s));//}}
}

package OD364;import java.util.*;/*** @description 电脑病毒感染* @level 6* @score 200* @url https://hydro.ac/d/HWOD2023/p/OD364*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//不是并查集！//有n台电脑int n = sc.nextInt();//电脑i，电脑i能到达的下一台电脑以及耗时HashMap<Integer, ArrayList<int[]>> graph = new HashMap<>();//m条相连信息int m = sc.nextInt();for (int i = 0; i < m; i++) {int from = sc.nextInt();int to = sc.nextInt();int time = sc.nextInt();graph.putIfAbsent(from, new ArrayList<>());graph.get(from).add(new int[]{to, time});}//源点int src = sc.nextInt();//记录源点感染到其他电脑的最短耗时 下标从1开始int[] dist = new int[n + 1];//初始时，源点默认与其他点不相连，耗时为无穷大Arrays.fill(dist, Integer.MAX_VALUE);//源点到自己的耗时为0dist[src] = 0;//优先队列，已经被探索到的点中耗时越小的越优先PriorityQueue<Integer> needCheck = new PriorityQueue<>(Comparator.comparingInt(a -> dist[a]));//记录点是否在队列中boolean[] visited = new boolean[n + 1];//初始时探索的点只有源点needCheck.add(src);visited[src] = true;while (needCheck.size() > 0) {//取出当前探索的点需要耗时最少的int cur = needCheck.poll();//取出了就要修改状态visited[cur] = false;//如果cur有能到达的其他点if (graph.containsKey(cur)) {//遍历cur能到达的所有其他点for (int[] next : graph.get(cur)) {//可到达的点int v = next[0];//花费时间int t = next[1];//从源点到v的时间是dist[v] 通过cur到达v的时间是dist[cur]+t//第一次遍历时则是newDist = dist[src] + t(与源点直接相连花费的时间)int newDist = dist[cur] + t;if (newDist < dist[v]) {dist[v] = newDist;//如果v不在已探索的路径中，则添加if (!visited[v]) {visited[v] = true;needCheck.add(v);}}}}}//dist[]是源点到其他各点的最短耗时，时间是共用的，最大值就是感染到所有电脑花费的时间int ans = 0;for (int i = 1; i <= n; i++) {ans = Math.max(ans, dist[i]);}//不能直接用stream.max() 因为dist[0]一直是无穷大//int max = Arrays.stream(dist).max().orElse(0);//如果有无法感染的电脑，则源点到该电脑的dist是无穷大System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);}
}