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

相关文章

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

ural 1026. Questions and Answers 查询

1026. Questions and Answers Time limit: 2.0 second Memory limit: 64 MB Background The database of the Pentagon contains a top-secret information. We don’t know what the information is — you

Mybatis中的like查询

<if test="templateName != null and templateName != ''">AND template_name LIKE CONCAT('%',#{templateName,jdbcType=VARCHAR},'%')</if>

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

京东物流查询|开发者调用API接口实现

快递聚合查询的优势 1、高效整合多种快递信息。2、实时动态更新。3、自动化管理流程。 聚合国内外1500家快递公司的物流信息查询服务,使用API接口查询京东物流的便捷步骤,首先选择专业的数据平台的快递API接口:物流快递查询API接口-单号查询API - 探数数据 以下示例是参考的示例代码: import requestsurl = "http://api.tanshuapi.com/a

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的