用欧拉计划学Rust编程(第67题)
第67题 最大路径和II
问题描述：
解题步骤
第18题的算法用递归实现，数据量小，没有问题，在这道题中得更换算法。
如果知道一个节点的左、右节点的最大路径，可以很容易地计算出当前节点的最大路径，从底层开始，逐层计算每个节点到底部节点的最大路径上一层的最大路径，所以从每一层中最大路径只与下一层的左、右节点有关。
1）读文件，保存到数组中
这里采用连续存放的策略，节省内存空间。UNIX和Windows中的换行符有一点点区别，replace()时要注意。
let data = std::fs::read_to_string("triangle.txt").expect("读文件失败");
let data2 = data.trim().replace("\r\n", " ").replace("\n", " ");
let w: Vec<usize> = data2
.split(" ")
.map(|x| x.parse::<usize>().unwrap())
.collect();
2）计算某一个节点的行号
强行规定顶层的行号为1，逐层增1，这样规定有一个好处，就是每层的行号就是每层元素的个数。
fn row(n: usize) -> usize {
let mut s = 0;
for r in 1.. {
s += r;
if s > n {
return r;
}
}
return 0;
}
3）自下而上逐层计算
fn compute_path_weight(w: &Vec<usize>) -> Vec<usize> {
let mut path: Vec<usize> = vec![0; w.len()];
let max_row: usize = row(w.len() - 1);
for i in (0..w.len()).rev() { // 从底层向上计算
let r = row(i);
if r == max_row { // leaf
path[i] = w[i];
} else {
let left = w[i] + path[i + r];
let right = w[i] + path[i + r + 1];
path[i] = if left > right { left } else { right };
}
}
return path;
}
4）第0个节点的值就是答案
let path = compute_path_weight(&w);
println!("{}", path[0]);
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-10-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读