leetcode/
pascals_triangle.rs

1//! # 118. 杨辉三角
2//!
3//! 难度 简单
4//!
5//! 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
6//!
7//! 在杨辉三角中，每个数是它左上方和右上方的数的和。
8//!
9//! ## 示例:
10//!
11//! ```text
12//! 输入: 5
13//! 输出:
14//! [
15//!      [1],
16//!     [1,1],
17//!    [1,2,1],
18//!   [1,3,3,1],
19//!  [1,4,6,4,1]
20//! ]
21//! ```
22//! See [leetcode](https://leetcode-cn.com/problems/pascals-triangle/)
23
24pub struct Solution;
25impl Solution {
26    pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
27        assert!(num_rows >= 0);
28
29        gen_pascal_triangle()
30            .take(num_rows as usize)
31            .collect()
32    }
33}
34
35fn gen_pascal_triangle() -> impl Iterator<Item = Vec<i32>> {
36    std::iter::successors(Some(vec![1]), |row| {
37        vec![1].into_iter()
38            .chain(row.windows(2).map(|v| v.iter().sum()))
39            .chain(vec![1].into_iter())
40            .collect::<Vec<i32>>()
41            .into()
42    })
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[test]
50    fn test() {
51        let cases = vec![
52            (0, vec![]),
53            (1, vec![vec![1]]),
54            (2, vec![
55                    vec![1],
56                    vec![1,1],
57            ]),
58            (5, vec![
59                    vec![1],
60                    vec![1,1],
61                    vec![1,2,1],
62                    vec![1,3,3,1],
63                    vec![1,4,6,4,1]]),
64        ];
65
66        for (num_rows, expect) in cases {
67            assert_eq!(expect, Solution::generate(num_rows));
68        }
69    }
70
71    #[test]
72    fn test_gen_pascal_triangle() {
73        let mut gen = gen_pascal_triangle();
74        assert_eq!(vec![1], gen.next().unwrap());
75        assert_eq!(vec![1,1], gen.next().unwrap());
76        assert_eq!(vec![1,2,1], gen.next().unwrap());
77        assert_eq!(vec![1,3,3,1], gen.next().unwrap());
78        assert_eq!(vec![1,4,6,4,1], gen.next().unwrap());
79    }
80}
leetcode/pascals_triangle.rs

leetcode/
pascals_triangle.rs
