保定网站优化公司,云南抖音推广,什么网站可以查询企业信息,重庆做网站建设公司前言
###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程#xff08;例如想要掌握基础用法#xff0c;该刷哪些题#xff1f;#xff09;我的解析也不会做的非常详细#xff0c;只会提供思路和一些关键点#xff0c;力扣上的大佬们的题解质量是非…前言
###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程例如想要掌握基础用法该刷哪些题我的解析也不会做的非常详细只会提供思路和一些关键点力扣上的大佬们的题解质量是非常非常高滴 习题
1.新增道路查询后的最短距离I
题目链接:3243. 新增道路查询后的最短距离 I - 力扣LeetCode
题面:
分析:bfs
贴上大佬代码:
class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {ListInteger[] 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, ListInteger[] g, int[] vis, int n) {QueueInteger 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 大佬代码:
class Solution {public ListString watchedVideosByFriends(ListListString watchedVideos, int[][] friends, int id, int level) {//bfs找到level好友DequeInteger q new ArrayDeque();q.addLast(id);int size q.size();//用于记录防止重复SetInteger set new HashSet();set.add(id);while(level0){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朋友观看的视频MapString,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);}}ListString 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(iMath.min(a.length(),b.length())){return a.length() - b.length();}}}}return map.get(a) - map.get(b);});return list;}
}后言
上面是力扣图论专题下一篇是其他的习题希望有所帮助一同进步共勉
