力扣-图论-9【算法学习day.59】

news/2024/12/16 0:42:53/

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.新增道路查询后的最短距离I

题目链接:3243. 新增道路查询后的最短距离 I - 力扣（LeetCode）

题面:

分析:bfs

贴上大佬代码:

java">class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {List<Integer>[] g = new ArrayList[n - 1]; // 邻接表Arrays.setAll(g, i -> new ArrayList<>()); // 初始化邻接表for (int i = 0; i < n - 1; i++) { // 构建初始图g[i].add(i + 1);}int[] ans = new int[queries.length]; // 结果数组int[] vis = new int[n - 1]; // 访问标记数组for (int i = 0; i < queries.length; i++) { // 处理每个查询g[queries[i][0]].add(queries[i][1]); // 添加边ans[i] = bfs(i + 1, g, vis, n); // 计算最短距离}return ans; // 返回结果}private int bfs(int i, List<Integer>[] g, int[] vis, int n) {Queue<Integer> q = new LinkedList<>(); // 队列q.offer(0); // 起点int step = 1; // 步数while (!q.isEmpty()) { // BFSint size = q.size();for (int j = 0; j < size; j++) {int x = q.poll();for (int y : g[x]) {if (y == n - 1) { // 到达终点return step;}if (vis[y] != i) { // 未访问vis[y] = i;q.offer(y);}}}step++;}return -1; // 无法到达}
}

2.获取你好友已观看的视频

题目链接:1311. 获取你好友已观看的视频 - 力扣（LeetCode）

大佬代码:

java">class Solution {public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {//bfs找到level好友Deque<Integer> q = new ArrayDeque<>();q.addLast(id);int size = q.size();//用于记录防止重复Set<Integer> set = new HashSet<>();set.add(id);while(level>0){int i = q.pollFirst();for(int a : friends[i]){if(!set.contains(a)){set.add(a);q.addLast(a);}}size--;if(size == 0){level--;size = q.size();}}//哈希表-记录level朋友观看的视频Map<String,Integer> map = new HashMap<>();while(!q.isEmpty()){int i = q.pollFirst();for(String s : watchedVideos.get(i)){if(map.containsKey(s))map.put(s,map.get(s)+1);else map.put(s,1);}}List<String> list = new ArrayList<>(map.keySet());//排序list.sort((a,b)->{if(map.get(a) == map.get(b)){int i = 0;while(true){if(a.charAt(i) != b.charAt(i))return a.charAt(i) - b.charAt(i);else{i++;if(i>=Math.min(a.length(),b.length())){return a.length() - b.length();}}}}return map.get(a) - map.get(b);});return list;}
}