120. 三角形最小路径和

每天一道Rust-LeetCode(2019-08-14)

坚持每天一道题,刷题学习Rust.

题目描述

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

自底向上
先求最下面一行的最小路径,就是他自身.
然后依次求出倒数第二行的所有元素的最短路径.
依次类推,最终得出自顶向下的最短路径.
时间复杂度为O(N) N为所有元素的个数
空间复杂度为O(n) n为三角形总行数

解题过程

struct Solution {}
impl Solution {
    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
        let mut row = triangle.len();
        let mut path = triangle[row - 1].clone();
        while path.len() > 1 {
            row -= 1;
            let rv = triangle.get(row - 1).unwrap();
            for i in 0..row {
                let m = path[i].min(path[i + 1]); //保证不会越界的
                path[i] = m + rv[i];
            }
            path.pop(); //扔掉最后一个
        }
        return path[0];
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_mininum_total() {
        assert_eq!(
            11,
            Solution::minimum_total(vec![vec![2], vec![3, 4], vec![6, 5, 7], vec![4, 1, 8, 3],])
        )
    }
}

一点感悟

使用rust确实能让思路更清晰,使得通过率更高.

其他

欢迎关注我的github,本项目文章所有代码都可以找到.