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

2024.1.26

- - 题目来源
  - 我的题解
  - - 方法一使用dfs对每一组查询都求最近公共祖先（会超时，通不过）
    - 方法二不需要构建图，直接在原始数组上进行求最大公共祖先的操作。

题目来源

力扣每日一题；题序：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$ ]，记节点 $lca_i$ 为节点 $a_i$ 与 $b_i$ 的最近公共祖先，那么从节点 $a_i$ 到节点 $b_i$ 的路径上，权重为 j 的边数量 $t_j$ 的计算如下：

$t_j = \textit{count}[a_i][j] + \textit{count}[b_i][j] - 2 \times \textit{count}[\textit{lca}_i][j]$
为了让节点 $a_i$ 到节点 $b_i$ 路径上每条边的权重都相等，贪心地将路径上所有的边都更改为边数量最多的权重即可，即从节点 $a_i$ 到节点 $b_i$ 路径上每条边的权重都相等所需的最小操作次数 $res_i$ 的计算如下： $\textit{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];
    }
}