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

2024-02-06 11:52

本文主要是介绍2024.1.26力扣每日一题——边权重均等查询,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2024.1.26

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

题目来源

力扣每日一题;题序:2846

我的题解

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

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

时间复杂度:O( n 2 n^2 n2)
空间复杂度:O( m × n m\times n m×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 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] tj=count[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_{j=1}^{W}t_j - \max_{1 \le j \le W}t_j resi=j=1Wtjmax1jWtj
其中 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];}
}

困难题果然不是我会做的,做做搬运工得了在这里插入图片描述

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

这篇关于2024.1.26力扣每日一题——边权重均等查询的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/684230

相关文章

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》:本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

mysql表操作与查询功能详解

《mysql表操作与查询功能详解》本文系统讲解MySQL表操作与查询,涵盖创建、修改、复制表语法,基本查询结构及WHERE、GROUPBY等子句,本文结合实例代码给大家介绍的非常详细,感兴趣的朋友跟随... 目录01.表的操作1.1表操作概览1.2创建表1.3修改表1.4复制表02.基本查询操作2.1 SE

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复

mysql查询使用_rowid虚拟列的示例

《mysql查询使用_rowid虚拟列的示例》MySQL中,_rowid是InnoDB虚拟列,用于无主键表的行ID查询,若存在主键或唯一列,则指向其,否则使用隐藏ID(不稳定),推荐使用ROW_NUM... 目录1. 基本查询(适用于没有主键的表)2. 检查表是否支持 _rowid3. 注意事项4. 最佳实

苹果macOS 26 Tahoe主题功能大升级:可定制图标/高亮文本/文件夹颜色

《苹果macOS26Tahoe主题功能大升级:可定制图标/高亮文本/文件夹颜色》在整体系统设计方面,macOS26采用了全新的玻璃质感视觉风格,应用于Dock栏、应用图标以及桌面小部件等多个界面... 科技媒体 MACRumors 昨日(6 月 13 日)发布博文,报道称在 macOS 26 Tahoe 中

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA