公司网站建设注册,免费建设一个网站,多用户商城系统的服务态度,魏县网络营销推广方法2024.1.26 题目来源我的题解方法一 使用dfs对每一组查询都求最近公共祖先#xff08;会超时#xff0c;通不过#xff09;方法二 不需要构建图#xff0c;直接在原始数组上进行求最大公共祖先的操作。 题目来源
力扣每日一题#xff1b;题序#xff1a;2846
我的题解
… 2024.1.26 题目来源我的题解方法一 使用dfs对每一组查询都求最近公共祖先会超时通不过方法二 不需要构建图直接在原始数组上进行求最大公共祖先的操作。 题目来源
力扣每日一题题序2846
我的题解
方法一 使用dfs对每一组查询都求最近公共祖先会超时通不过 使用dfs对每一组查询都去找最近公共祖先并在这个过程中统计边的权重最后通过TreeMap计算出边权重集合中元素重复的最大次数贪心策略可知结果为查询路径上总共的边-最大次数。 时间复杂度O( n 2 n^2 n2) 空间复杂度O( m × n m\times n m×n) ListInteger list;public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {MapInteger,Integer[] graphcreateGraph(n,edges);int qnqueries.length;int[] resnew int[qn];for(int i0;iqn;i){int fromqueries[i][0];int toqueries[i][1];if(fromto)continue;listnew ArrayList();boolean[] visitednew boolean[n];dfs(graph,from,to,visited,new ArrayList());res[i]needChange(list);}return res;}public int needChange(ListInteger l){TreeMapInteger, Long frequencyMap new TreeMap(l.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting())));TreeMapInteger, Long frequencySortMapnew TreeMap(Comparator.comparing(frequencyMap::get));frequencySortMap.putAll(frequencyMap);return l.size()-Integer.parseInt(frequencySortMap.get(frequencySortMap.lastKey()).toString());}public MapInteger,Integer[] createGraph(int n,int[][] edges){MapInteger,Integer[] graphnew HashMap[n];for(int i0;in;i)graph[i]new HashMap();for(int[] e:edges){int from e[0];int toe[1];int vale[2];graph[from].put(to,val);graph[to].put(from,val);}return graph;}public void dfs(MapInteger,Integer[] graph,int from,int to,boolean[] visited,ListInteger path){if(fromto){listnew ArrayList(path);return ;}visited[from]true;for(int next:graph[from].keySet()){if(!visited[next]){path.add(graph[from].get(next));dfs(graph,next,to,visited,path);path.remove(path.size()-1);}}visited[from]false;}方法二 不需要构建图直接在原始数组上进行求最大公共祖先的操作。
参考官方题解 以节点 0 为根节点使用数组 count[i]记录节点 i到根节点 0 的路径上边权重的数量即 count[i][j] 表示节点 i到根节点 0 的路径上权重为 j的边数量。对于查询 queries[i][ a i a_i ai, b i b_i bi]记节点 l c a i lca_i lcai为节点 a i a_i ai与 b i b_i bi的最近公共祖先那么从节点 a i a_i ai到节点 b i b_i bi的路径上权重为 j 的边数量 t j t_j tj的计算如下 t j count [ a i ] [ j ] count [ b i ] [ j ] − 2 × count [ lca i ] [ j ] t_j \textit{count}[a_i][j] \textit{count}[b_i][j] - 2 \times \textit{count}[\textit{lca}_i][j] tjcount[ai][j]count[bi][j]−2×count[lcai][j] 为了让节点 a i a_i ai到节点 b i b_i bi路径上每条边的权重都相等贪心地将路径上所有的边都更改为边数量最多的权重即可即从节点 a i a_i ai到节点 b i b_i bi路径上每条边的权重都相等所需的最小操作次数 r e s i res_i resi的计算如下 res i ∑ j 1 W t j − max 1 ≤ j ≤ W t j \textit{res}_i \sum_{j1}^{W}t_j - \max_{1 \le j \le W}t_j resi∑j1Wtj−max1≤j≤Wtj 其中 W26W 26W26 表示权重的最大值。 时间复杂度O((mn)×Wm×logn)其中 n 是节点数目m 是查询数目W 是权重的可能取值数目。 空间复杂度O(n×Wm) class Solution {static final int W 26;public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {int m queries.length;MapInteger, Integer[] neighbors new Map[n];for (int i 0; i n; i) {neighbors[i] new HashMapInteger, Integer();}for (int[] edge : edges) {neighbors[edge[0]].put(edge[1], edge[2]);neighbors[edge[1]].put(edge[0], edge[2]);}Listint[][] queryArr new List[n];for (int i 0; i n; i) {queryArr[i] new ArrayListint[]();}for (int i 0; i m; i) {queryArr[queries[i][0]].add(new int[]{queries[i][1], i});queryArr[queries[i][1]].add(new int[]{queries[i][0], i});}int[][] count new int[n][W 1];boolean[] visited new boolean[n];int[] uf new int[n];int[] lca new int[m];tarjan(0, -1, neighbors, queryArr, count, visited, uf, lca);int[] res new int[m];for (int i 0; i m; i) {int totalCount 0, maxCount 0;for (int j 1; j W; j) {int t count[queries[i][0]][j] count[queries[i][1]][j] - 2 * count[lca[i]][j];maxCount Math.max(maxCount, t);totalCount t;}res[i] totalCount - maxCount;}return res;}public void tarjan(int node, int parent, MapInteger, Integer[] neighbors, Listint[][] queryArr, int[][] count, boolean[] visited, int[] uf, int[] lca) {if (parent ! -1) {System.arraycopy(count[parent], 0, count[node], 0, W 1);count[node][neighbors[node].get(parent)];}uf[node] node;for (int child : neighbors[node].keySet()) {if (child parent) {continue;}tarjan(child, node, neighbors, queryArr, count, visited, uf, lca);uf[child] node;}for (int[] pair : queryArr[node]) {int node1 pair[0], index pair[1];if (node ! node1 !visited[node1]) {continue;}lca[index] find(uf, node1);}visited[node] true;}public int find(int[] uf, int i) {if (uf[i] i) {return i;}uf[i] find(uf, uf[i]);return uf[i];}
}困难题果然不是我会做的做做搬运工得了
有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
