leetcode # 118:Pascal's Triangle 楊輝三角

gggggggbong 發布于2019-08-16 18:23 / 2608人閱讀

摘要：楊輝三角給定一個非負整數，生成楊輝三角的前行。在楊輝三角中，每個數是它左上方和右上方的數的和。另外可以在內層循環加判斷在不等于時才加上，這樣可省略代碼段，但是這個會在每次進入第一次循環后判斷一次。本著減少資源消耗的原則，應當提到外面。

118:Pascal"s Triangle 楊輝三角

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

給定一個非負整數 numRows，生成楊輝三角的前 numRows 行。

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]
]

解題思路：

? 第一行第二行都是1，每行第一個和最后一個都為1，假設其他位置的數x索引坐標是(m,n)，則x就是數是它索引正上方的數和索引正上方的左邊的數之和。即(m-1,n),(m-1,n-1)兩數和。

java：

class Solution {
    public List> generate(int numRows) {
        List> triangle = new ArrayList>();

        if(numRows == 0) return triangle;
        List one = new ArrayList();
        one.add(1);
        triangle.add(one);
        if(numRows == 1) return triangle;
        for (int i=1;i row = new ArrayList();
            row.add(1);
            for (int j=1;j prev = triangle.get(i-1);
                row.add(prev.get(j-1)+prev.get(j));
            }
            row.add(1);
            triangle.add(row);
        }
        return triangle;
    }
}

python：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows==0:return []
        triangle=[[1]]
        if numRows==1: return triangle
        for i in range(1,numRows):
            tmp=[1]
            for j in range(1,i):
                tmp.append(triangle[i-1][j-1]+triangle[i-1][j])
            tmp.append(1)
            triangle.append(tmp)
        return triangle

總結：

很簡單的一道題，可以復習一下java嵌套數組數據結構。另外可以在內層循環加判斷 if(i!=0) row.add(1);triangle.add(row); 在i不等于0時才加上1，這樣可省略

List one = new ArrayList();
        one.add(1);
        triangle.add(one);
        if(numRows == 1) return triangle;

代碼段，但是這個 if(i!=0)會在每次進入第一次循環后判斷一次。本著減少資源消耗的原則，應當提到外面。

云服務器 GPU云服務器 Triangle pascal_triangle Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/74995.html

leetcode # 118:Pascal&#039;s Triangle 楊輝三角

摘要：楊輝三角給定一個非負整數，生成楊輝三角的前行。在楊輝三角中，每個數是它左上方和右上方的數的和。另外可以在內層循環加判斷在不等于時才加上，這樣可省略代碼段，但是這個會在每次進入第一次循環后判斷一次。本著減少資源消耗的原則，應當提到外面。 118:Pascals Triangle 楊輝三角 Given a non-negative integer numRows, generate the...

CKJOKER 2019-07-31 10:37 評論0 收藏0
Leetcode 118&119 Pascal&#039;s Triangle

摘要：首先要對特殊情況進行處理小于等于的情況。然后循環，每一次產生一個，個有個元素，每個的第一個和第個元素都是對于中間的那些元素，則找出前一個的對應位置的兩個元素加和即可得到。這一道題只要求返回形式的一行的元素即可。 118 Pascals Triangle 題目詳情 Given numRows, generate the first numRows of Pascals triangle....

laznrbfe 2019-08-15 13:40 評論0 收藏0
[LeetCode] 118. Pascal&#039;s Triangle

Problem Given a non-negative integer numRows, generate the first numRows of Pascals triangle. In Pascals triangle, each number is the sum of the two numbers directly above it. Example: Input: 5Output:...

sunnyxd 2019-08-16 13:34 評論0 收藏0
LeetCode 118：楊輝三角 II Pascal&#039;s Triangle II

摘要：公眾號愛寫作者愛寫給定一個非負索引，其中，返回楊輝三角的第行。在楊輝三角中，每個數是它左上方和右上方的數的和。示例輸入輸出進階你可以優化你的算法到空間復雜度嗎解題思路和之前寫的那篇號楊輝三角基本類似。公眾號：愛寫bug（ID：icodebugs）作者：愛寫bug 給定一個非負索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。 Given a non-negative index...

KaltZK 2019-08-16 18:29 評論0 收藏0
LeetCode 118：楊輝三角 II Pascal&#039;s Triangle II

摘要：公眾號愛寫作者愛寫給定一個非負索引，其中，返回楊輝三角的第行。在楊輝三角中，每個數是它左上方和右上方的數的和。示例輸入輸出進階你可以優化你的算法到空間復雜度嗎解題思路和之前寫的那篇號楊輝三角基本類似。公眾號：愛寫bug（ID：icodebugs）作者：愛寫bug 給定一個非負索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。 Given a non-negative index...

xiaodao 2019-07-31 11:25 評論0 收藏0