[LeetCode] 118. Pascal's Triangle* 解題思路 (Easy)

這題需要組成一個三角形的數字。

LeetCode 題目連結

 

https://leetcode.com/problems/pascals-triangle/

 

題目

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Accept 作法

這題時間複雜度為 O(n2)。n 是 numRows。


Runtime: 0 ms
Memory: 37.3 MB

Java 程式碼

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result =new ArrayList<>();
        
        if(numRows ==0){
            return result;
        }
        
        result.add(new ArrayList<>());
        result.get(0).add(1);
        
        for(int i = 1;i< numRows;i++){
            ArrayList<Integer> list = new ArrayList<Integer>();
            
            List<Integer> lastList = result.get(i-1);
            
            list.add(1);
            
            for(int j = 1;j<i;j++){
               int num = lastList.get(j-1)+lastList.get(j);
               list.add(num);     
            }
            list.add(1);
            result.add(list);
        }
        return result;
    }
}

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題