帕斯卡三角

  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. }