Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

※ 引述《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
    }
}


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1697466803.A.E81.html
※ 編輯: yam276 (123.193.249.242 臺灣), 10/16/2023 22:35:45
→ wwndbk: 大師
→ yam276: 不是==
→ ZooseWu: for從後面跑回來可以少紀錄很多變數 都沒想到