6.5 KiB
1615. 最大网络秩
description：
n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。
代码：
fn main() {
let n:usize = 4;
let roads:Vec<Vec<i32>> = vec![vec![0,1], vec![0,3],vec![1,2], vec![1,3]];
let res = maximal_network_rank(n, &roads);
println!("res is: {}", res);
// for road in &roads{
// for &i in road {
// print!(" {} ", i == 2);
// }
// println!(" ");
// }
println!(" - - - ");
let roads:Vec<&[i32]> = vec![&[0,1], &[0,3], &[1,2], &[1,3]];
let res = maximal_network_rank2(n, &roads);
println!("res is: {}", res);
// for road in &roads{
// for &i in *road{
// print!(" {} ", i==2);
// }
// println!(" ");
// }
// 多维向量
let roads2:Vec<Vec<Vec<i32>>> = vec![vec![vec![0,1], vec![0,3],vec![1,2], vec![1,3]],vec![vec![0,1], vec![0,3],vec![1,2], vec![1,3]]];
for roads in &roads2{
for road in roads{
for &i in road {
print!(" {} ", i == 2);
}
println!(" ");
}
println!(" ");
}
// 多维数组
let roads3: &[&[&[i32]]] = &[&[&[0,1], &[0,3], &[1,2], &[1,3]], &[&[0,1], &[0,3], &[1,2], &[1,3]]];
for &roads in roads3{
for &road in roads{
for &i in road{
print!(" {} ", i==2);
}
}
println!(" ");
}
for roads in roads3{
for road in *roads{
for &i in *road{
print!(" {} ", i==2);
}
}
println!(" ");
}
// 多维数组
let roads4: Vec<&[&[i32]]> = vec![&[&[0,1], &[0,3], &[1,2], &[1,3]], &[&[0,1], &[0,3], &[1,2], &[1,3]]];
for roads in &roads4{
for road in *roads{
for &i in *road{
print!(" {} ", i==2);
}
}
println!(" ");
}
}
fn maximal_network_rank(n:usize, roads:&Vec<Vec<i32>>)->i32{
let mut connect:Vec<Vec<bool>> = vec![vec![false; n]; n];
let mut degree:Vec<i32> = vec![0; n];
for road in roads{
connect[road[0] as usize][road[1] as usize] = true;
connect[road[1] as usize][road[0] as usize] = true;
degree[road[0] as usize] = degree[road[0] as usize]+1;
degree[road[1] as usize] = degree[road[1] as usize]+1;
}
let mut max_rank = 0;
for i in 0..n {
for j in i+1..n{
let rank = degree[i] + degree[j] - (if connect[i][j] { 1 } else { 0 });
max_rank = max_rank.max(rank);
}
}
max_rank
}
fn maximal_network_rank2(n:usize, roads:&[&[i32]])->i32{
let mut connect:Vec<Vec<bool>> = vec![vec![false; n]; n];
let mut degree:Vec<i32> = vec![0; n];
for road in roads{
connect[road[0] as usize][road[1] as usize] = true;
connect[road[1] as usize][road[0] as usize] = true;
degree[road[0] as usize] += 1;
degree[road[1] as usize] += 1;
}
let mut max_rank = 0;
for i in 0..n {
for j in i+1..n{
let rank = degree[i] + degree[j] - if connect[i][j] { 1 } else { 0 };
max_rank = max_rank.max(rank);
}
}
max_rank
}
先这样理解，以后遇到再说把，有点乱。
图：
接收任何 i32 类型的切片，而不仅仅是 Vec<i32>写法。
关于for
遍历二维向量（不失去所有权的前提下，取出i32），多维也是如此。
多维：
i32 implements Add<&i32>, the trait that implements the logic for the + operator (and other traits implementing other mathematical operators like += and *, see std::ops module), but not PartialEq<&i32> (the trait used by comparison operators like >). Only PartialEq is implemented for i32. So you can add, add assign and multiply, etc. &i32 to a i32 value, but you can not compare &i32 with i32.
for road in &roads 中，road 的类型是 &&[i32]，是指向 &[i32] 类型的引用。这个引用是从 roads 的 Vec 中获取的。
而 for road in roads 中，road 的类型是 &[i32]，是 roads 中元素的引用，类型为 &[i32]。这里的 roads 是 Vec<&[i32]> 类型的引用，也就是指向 &[i32] 类型的引用的引用，即 &&[i32] 类型的引用。通过使用 & 对 roads 进行解引用，可以得到指向 Vec<&[i32]>> 类型的引用，即 &Vec<&[i32]>>，然后就可以对其进行迭代获取每个 &[i32] 类型的引用了。
在 Rust 中，数组或向量的元素可以通过索引访问，无论是使用 [] 运算符还是 get() 方法。当使用 [] 运算符时，Rust 会自动解引用数组或向量的引用，并将其作为指向第一个元素的指针来处理。因此，无论是 for road in &roads 还是 for road in roads，在使用 road[0] 访问数组或向量的第一个元素时，都将自动解引用指向该元素的指针，返回一个 i32 类型的值。这是 Rust 语言的自动解引用功能的一部分，它使得代码更加简洁和易读。