leetcode/
pascals_triangle_ii.rs

1//! # 119. 杨辉三角 II
2//!
3//! 难度 简单
4//!
5//! 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
6//!
7//!
8//!
9//! 在杨辉三角中，每个数是它左上方和右上方的数的和。
10//!
11//! ## 示例:
12//!
13//! ```text
14//! 输入: 3
15//! 输出: [1,3,3,1]
16//! ```
17//! ## 进阶：
18//!
19//! 你可以优化你的算法到 *O(k)* 空间复杂度吗？
20//!
21//! See [leetcode](https://leetcode-cn.com/problems/pascals-triangle-ii/)
22
23pub struct Solution;
24impl Solution {
25    pub fn get_row(row_index: i32) -> Vec<i32> {
26        assert!(row_index >= 0);
27
28        gen_pascal_triangle()
29            .skip(row_index as usize)
30            .next()
31            .unwrap()
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![1]),
53            (1, vec![1,1]),
54            (2, vec![1,2,1]),
55            (3, vec![1,3,3,1]),
56            (4, vec![1,4,6,4,1]),
57        ];
58
59        for (num_rows, expect) in cases {
60            assert_eq!(expect, Solution::get_row(num_rows));
61        }
62    }
63}
leetcode/pascals_triangle_ii.rs

leetcode/
pascals_triangle_ii.rs
