2024.1.26力扣每日一题——边权重均等查询

题目来源

力扣每日一题；题序：2846

我的题解

方法一 使用dfs对每一组查询都求最近公共祖先（会超时，通不过）

使用dfs对每一组查询都去找最近公共祖先，并在这个过程中统计边的权重，最后通过TreeMap计算出边权重集合中元素重复的最大次数，贪心策略可知，结果为：查询路径上总共的边-最大次数。

时间复杂度：O($n^2$)
空间复杂度：O($m\times n$)

 List<Integer> list;public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {Map<Integer,Integer>[] graph=createGraph(n,edges);int qn=queries.length;int[] res=new int[qn];for(int i=0;i<qn;i++){int from=queries[i][0];int to=queries[i][1];if(from==to)continue;list=new ArrayList<>();boolean[] visited=new boolean[n];dfs(graph,from,to,visited,new ArrayList<>());res[i]=needChange(list);}return res;}public int needChange(List<Integer> l){TreeMap<Integer, Long> frequencyMap = new TreeMap<>(l.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting())));TreeMap<Integer, Long> frequencySortMap=new TreeMap<>(Comparator.comparing(frequencyMap::get));frequencySortMap.putAll(frequencyMap);return l.size()-Integer.parseInt(frequencySortMap.get(frequencySortMap.lastKey()).toString());}public Map<Integer,Integer>[] createGraph(int n,int[][] edges){Map<Integer,Integer>[] graph=new HashMap[n];for(int i=0;i<n;i++)graph[i]=new HashMap<>();for(int[] e:edges){int from =e[0];int to=e[1];int val=e[2];graph[from].put(to,val);graph[to].put(from,val);}return graph;}public void dfs(Map<Integer,Integer>[] graph,int from,int to,boolean[] visited,List<Integer> path){if(from==to){list=new 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$,$b_i$]，记节点 $lc{a}_i$为节点 $a_i$与 $b_i$的最近公共祖先，那么从节点 $a_i$到节点 $b_i$的路径上，权重为 j 的边数量 $t_j$的计算如下：

$t_j=\text{count}[a_i][j]+\text{count}[b_i][j]-2\times \text{count}[{\text{lca}}_i][j]$
为了让节点 $a_i$到节点$b_i$路径上每条边的权重都相等，贪心地将路径上所有的边都更改为边数量最多的权重即可，即从节点$a_i$到节点$b_i$路径上每条边的权重都相等所需的最小操作次数 $re{s}_i$的计算如下：${\text{res}}_i={\sum }_{j=1}^W{t}_j-{\max }_{1\le j\le W}{t}_j$
其中 W=26W = 26W=26 表示权重的最大值。

时间复杂度：O((m+n)×W+m×logn)，其中 n 是节点数目，m 是查询数目，W 是权重的可能取值数目。
空间复杂度：O(n×W+m)

class Solution {static final int W = 26;public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {int m = queries.length;Map<Integer, Integer>[] neighbors = new Map[n];for (int i = 0; i < n; i++) {neighbors[i] = new HashMap<Integer, Integer>();}for (int[] edge : edges) {neighbors[edge[0]].put(edge[1], edge[2]);neighbors[edge[1]].put(edge[0], edge[2]);}List<int[]>[] queryArr = new List[n];for (int i = 0; i < n; i++) {queryArr[i] = new ArrayList<int[]>();}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, Map<Integer, Integer>[] neighbors, List<int[]>[] 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];}
}

困难题果然不是我会做的，做做搬运工得了

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~