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;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

方法二 不需要构建图，直接在原始数组上进行求最大公共祖先的操作。

参考：官方题解

以节点 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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

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

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