写点什么

2022-09-27:给定一个棵树, 树上每个节点都有自己的值,记录在数组 nums 里, 比如 nums[4] = 10,表示 4 号点的值是 10, 给定树上的每一条边,记录在二维数组 edges 里, 比如 ed

  • 2022 年 9 月 27 日
    北京
  • 本文字数:2704 字

    阅读完需:约 9 分钟

2022-09-27:给定一个棵树, 树上每个节点都有自己的值,记录在数组nums里, 比如nums[4] = 10,表示4号点的值是10, 给定树上的每一条边,记录在二维数组edges里, 比如ed

2022-09-27:给定一个棵树,树上每个节点都有自己的值,记录在数组 nums 里,比如 nums[4] = 10,表示 4 号点的值是 10,给定树上的每一条边,记录在二维数组 edges 里,比如 edges[8] = {4, 9}表示 4 和 9 之间有一条无向边,可以保证输入一定是一棵树,只不过边是无向边,那么我们知道,断掉任意两条边,都可以把整棵树分成 3 个部分。假设是三个部分为 a、b、c,a 部分的值是:a 部分所有点的值异或起来,b 部分的值是:b 部分所有点的值异或起来,c 部分的值是:c 部分所有点的值异或起来,请问怎么分割,能让最终的:三个部分中最大的异或值 - 三个部分中最小的异或值,最小。返回这个最小的差值。输入:nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]。输出:9。


答案 2022-09-27:


dfn 序号。这道题来自力扣 2322。力扣上测试了好几种语言的代码,go 语言运行效率是最高,其次是 java;rust 表现不佳,原因是代码中有复制切片的行为。内存占用 go 是最低的,rust 偏高,原因是代码中有复制切片的行为。时间复杂度:O(n^2)。空间复杂度:O(n)。


代码用 rust 编写。代码如下:


use std::iter::repeat;fn main() {    let mut nums = vec![1, 5, 5, 4, 11];    let mut edges = vec![vec![0, 1], vec![1, 2], vec![1, 3], vec![3, 4]];    let ans = minimum_score(&mut nums, &mut edges);    println!("ans = {}", ans);}const MAX_VALUE: i32 = 1 << 31 - 1;static mut cnt: i32 = 0;
fn minimum_score(nums: &mut Vec<i32>, edges: &mut Vec<Vec<i32>>) -> i32 { let n = nums.len() as i32; // 先建立图 // ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); let mut graph: Vec<Vec<i32>> = vec![]; // 4个点,0、1、2、3 // 0 : {} // 1 : {} // 2 : {} // 3 : {} for _i in 0..n { graph.push(vec![]); } for edge in edges.iter() { // a,b // graph.get(a).add(b); // graph.get(b).add(a); graph[edge[0] as usize].push(edge[1]); graph[edge[1] as usize].push(edge[0]); } // 无向边组成的无环图 // 为了方便,就认为0是头 // dfn[i] = ? let mut dfn: Vec<i32> = repeat(0).take(n as usize).collect(); // xor[i] 以i为头的整棵树,整体异或的结果是多少? let mut xor: Vec<i32> = repeat(0).take(n as usize).collect(); // size[i] 以i为头的整棵树,一共几个点? let mut size: Vec<i32> = repeat(0).take(n as usize).collect();
unsafe { cnt = 1; } dfs(nums, &mut graph, 0, &mut dfn, &mut xor, &mut size); let mut ans = MAX_VALUE; let m = edges.len() as i32; let mut cut1: i32; let mut cut2: i32; let mut pre: i32; let mut pos: i32; let mut part1: i32; let mut part2: i32; let mut part3: i32; let mut max: i32; let mut min: i32; for i in 0..m { // i,要删掉的第一条边,i号边 // edges[i][0] edges[i][1] dfn 谁大,谁就是删掉之后的树的头!cut1 // a b cut1 // { a, b} // 0 1 let a = edges[i as usize][0]; let b = edges[i as usize][1]; cut1 = if dfn[a as usize] < dfn[b as usize] { b } else { a }; for j in (i + 1)..m { // j, 要删掉的第二条边,j号边 // { c, d} // 0 1 let c = edges[j as usize][0]; let d = edges[j as usize][1]; cut2 = if dfn[c as usize] < dfn[d as usize] { d } else { c }; // cut1,cut2 pre = if dfn[cut1 as usize] < dfn[cut2 as usize] { cut1 } else { cut2 }; pos = if pre == cut1 { cut2 } else { cut1 }; // 早 pre 晚 pos part1 = xor[pos as usize]; // pos为头的树,是pre为头的树的子树! if dfn[pos as usize] < dfn[pre as usize] + size[pre as usize] { part2 = xor[pre as usize] ^ xor[pos as usize]; part3 = xor[0] ^ xor[pre as usize]; } else { // pos为头的树,不是pre为头的树的子树! part2 = xor[pre as usize]; part3 = xor[0] ^ part1 ^ part2; } max = get_max(get_max(part1, part2), part3); min = get_min(get_min(part1, part2), part3); ans = get_min(ans, max - min); } } return ans;}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T { if a > b { a } else { b }}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T { if a < b { a } else { b }}// 所有节点的值,存在nums数组里// 整个图结构,存在graph里// 当前来到的是cur号点// 请把cur为头,整棵树,所有节点的dfn、size、xor填好!// 返回!fn dfs( nums: &mut Vec<i32>, graph: &mut Vec<Vec<i32>>, cur: i32, dfn: &mut Vec<i32>, xor: &mut Vec<i32>, size: &mut Vec<i32>,) { // 当前节点了!, dfn[cur as usize] = unsafe { cnt }; unsafe { cnt += 1; } // 只是来到了cur的头部! xor[cur as usize] = nums[cur as usize]; size[cur as usize] = 1; // 遍历所有的孩子! for next in graph.clone()[cur as usize].iter() { //有clone,会影响性能 // 只有dfn是0的孩子,才是cur在树中的下级!!!! if dfn[*next as usize] == 0 { // cur某个孩子是next
dfs(nums, graph, *next, dfn, xor, size); // next整棵树的异或和, xor[cur as usize] ^= xor[*next as usize]; // next整棵树的size size[cur as usize] += size[*next as usize]; } }}
复制代码


执行结果如下:






左神java代码

发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2021.02.15 加入

还未添加个人简介

评论

发布
暂无评论
2022-09-27:给定一个棵树, 树上每个节点都有自己的值,记录在数组nums里, 比如nums[4] = 10,表示4号点的值是10, 给定树上的每一条边,记录在二维数组edges里, 比如ed_算法_福大大架构师每日一题_InfoQ写作社区