作者:
yam276 ('_')
2023-10-16 22:33:21※ 引述《leafff (leaf)》之銘言：
: 119. Pascal's Triangle II
: https://leetcode.com/problems/pascals-triangle-ii/
: 題目還有問能否讓空間複雜度為O(rowIndex)，
: 想問各位有沒有想法
我用DP亂解的：
impl Solution {
pub fn get_row(row_index: i32) -> Vec<i32> {
let mut triangle: Vec<Vec<i32>> = Vec::new();
for i in 0..=row_index as usize {
let mut row: Vec<i32> = Vec::new();
row.push(1);
for j in 1..i {
let value = triangle[i - 1][j - 1] + triangle[i - 1][j];
row.push(value);
}
if i > 0 {
row.push(1);
}
triangle.push(row);
}
triangle.last().cloned().unwrap_or(Vec::new())
}
}
別人的解之一：
一個for 直接用公式算出原本第二個for跑的東西
impl Solution {
pub fn get_row(row_index: i32) -> Vec<i32> {
let mut res = vec![1];
let mut prev: i64 = 1; // use i64 for the calculations
for k in 1..=row_index {
let next_val = prev * (row_index - k + 1) as i64 / k as i64;
res.push(next_val as i32);
prev = next_val;
}
res
}
}
別人的解之二：
空間O(row_index)解
只使用一個Vec
事先設定好大小
並從後往前算 避免覆蓋掉前一個數字
第二個for會從頭算到現在這一階
impl Solution {
pub fn get_row(row_index: i32) -> Vec<i32> {
let mut row = vec![1; row_index as usize + 1];
for i in 0..=(row_index as usize) {
for j in (1..i).rev() {
row[j] = row[j - 1] + row[j];
}
}
row
}
}