楼主:
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
}
}