LeetCode #119 Pascal’s Triangle II 巴斯卡三角形 II

回傳巴斯卡三角形指定的列

英文原文如下

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

中文翻譯

給予一個整數 rowIndex,回傳第 rowIndex 列 (從0開始)的巴斯卡三角形。

在巴斯卡三角形中,每一個數字都是上面的兩個數字的加總,顯示如下(上面那張圖,不在貼一次了)。

範例及題目限制

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

進一步: 你可以優化你的算法使其只使用 O(rowIndex) 的額外空間嗎?


解題思路

這一題,我們可以先參考系列的第一題 – LeetCode #118 Pascal’s Triangle 解題思路及翻譯

它們之間唯一的差異就是一個要整個三角形,而這一題只要特定的列就好

C# 解決方案

方案1

public class Solution {
    public IList<int> GetRow(int rowIndex) {
        List<int> res = new List<int>();
        
        res.Add(1);  // the first line
        
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j >= 1; j--) {
                res[j] += res[j - 1];
            }
            res.Add(1);
        }
        
        return res;
    }
}

Java 解決方案

方案1

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        
        res.add(1);  // the first line
        
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j >= 1; j--) {
                res.set(j,res.get(j) + res.get(j - 1));
            }
            res.add(1);
        }
        
        return res;
    }
}

結論

🧡如果這篇文章有幫上你的一點點忙,那是我的榮幸

🧡收藏文章或幫我點個廣告,那都是對我的支持

✅如有任何疑問,歡迎透過留言或messenger讓我知道 !

題目連結 : Pascal’s Triangle II – LeetCode

相關題目 :

一些隨機的LeetCode文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *