leetcode简单题26 N.118 杨辉三角 rust描述

 

//  动态规划
pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {let mut triangle: Vec<Vec<i32>> = vec![];for i in 0..num_rows {let mut row = vec![1; (i + 1) as usize];for j in 1..i as usize {row[j] = triangle[(i - 1) as usize][(j - 1)] + triangle[(i - 1) as usize][j];}triangle.push(row);}triangle
}
use std::collections::HashMap;
// 递归（带缓存）
struct Solution;
impl Solution {pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {let mut cache = HashMap::new();let mut triangle = vec![];for i in 0..num_rows {let mut row = vec![];for j in 0..=i {row.push(Self::get_value(i, j, &mut cache));}triangle.push(row);}triangle}fn get_value(i: i32, j: i32, cache: &mut HashMap<(i32, i32), i32>) -> i32 {if j == 0 || j == i {return 1;}if let Some(&val) = cache.get(&(i, j)) {return val;}let val = Self::get_value(i - 1, j - 1, cache) + Self::get_value(i - 1, j, cache);cache.insert((i, j), val);val}
}
// 迭代
pub fn generate2(num_rows: i32) -> Vec<Vec<i32>> {let mut triangle: Vec<Vec<i32>> = Vec::with_capacity(num_rows as usize);for i in 0..num_rows as usize {let mut row = vec![1; i + 1];for j in 1..i {row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];}triangle.push(row);}triangle
}
fn main() {}