帕斯卡三角

1. /// ## Paslcal's triangle problem

3. /// pascal_triangle(num_rows) returns the first num_rows of Pascal's triangle.
4. /// About Pascal's triangle: https://en.wikipedia.org/wiki/Pascal%27s_triangle
5. ///
6. /// Arguments:
7. ///     * `num_rows` - number of rows of triangle
8. /// Complexity
9. ///     - time complexity: O(n^2),
10. ///     - space complexity: O(n^2),
11. pub fn pascal_triangle(num_rows: i32) -> Vec<Vec<i32>> {
12. let mut ans: Vec<Vec<i32>> = vec![];

14. for i in 1..num_rows + 1 {
15. let mut vec: Vec<i32> = vec![1];

17. let mut res: i32 = 1;
18. for k in 1..i {
19. res *= i - k;
20. res /= k;
21. vec.push(res);
22. }
23. ans.push(vec);
24. }

26. ans
27. }

29. #[cfg(test)]
30. mod tests {
31. use super::pascal_triangle;

33. #[test]
34. fn test() {
35. assert_eq!(pascal_triangle(3), vec![vec![1], vec![1, 1], vec![1, 2, 1]]);
36. assert_eq!(
37. pascal_triangle(4),
38. vec![vec![1], vec![1, 1], vec![1, 2, 1], vec![1, 3, 3, 1]]
39. );
40. assert_eq!(
41. pascal_triangle(5),
42. vec![
43. vec![1],
44. vec![1, 1],
45. vec![1, 2, 1],
46. vec![1, 3, 3, 1],
47. vec![1, 4, 6, 4, 1]
48. ]
49. );
50. }
51. }