本文共 2282 字，大约阅读时间需要 7 分钟。

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

Example:

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

题意：给定一个非负整数 numRows ，生成杨辉三角的前 numRows 行。

解法 递推

开始写的C++代码如下：

class Solution {
   public:    vector
   
    
     > generate(int numRows) {
           vector
     
      
       > ans;        if (numRows == 0) return ans;        ans.push_back(vector
       
        {
   1});        if (numRows == 1) return ans;        ans.push_back(vector
        
         { 1, 1}); if (numRows == 2) return ans; for (int i = 2; i < numRows; ++i) { ans.push_back(vector
         
          { 1}); int size = ans[i - 1].size(); for (int j = 0; j < size - 1; ++j) ans[i].push_back(ans[i - 1][j] + ans[i - 1][j + 1]); ans[i].push_back(1); } return ans; }};
         
        
       
      
     
    
   

运行效率如下：

执行用时：4 ms, 在所有 C++ 提交中击败了38.91% 的用户内存消耗：6.9 MB, 在所有 C++ 提交中击败了5.03% 的用户

20201206 Update 今日打卡更新Java代码：

class Solution {
        public List
    
     
      > generate(int numRows) {
            List
      
       
        > ans = new ArrayList<>();        int[][] arr = new int[numRows][numRows];        for (int i = 0; i < numRows; ++i) {
                List
        
          subList = new ArrayList<>();            for (int j = 0; j <= i; ++j) {
                    if (j == 0 || j == i) arr[i][j] = 1;                else arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];                subList.add(arr[i][j]);            }            ans.add(subList);        }        return ans;    } }
        
       
      
     
    

运行效率见下：

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户内存消耗：36.5 MB, 在所有 Java 提交中击败了34.00% 的用户

这样写得太繁琐了，简化如下：

class Solution {
   public:    vector
   
    
     > generate(int numRows) {
           vector
     
      
       > ans(numRows);         for (int i = 0; i < numRows; ++i) {
               for (int j = 0; j < i + 1; ++j) {
    //第i行的数字个数为i+1                if (j == 0 || j == i) ans[i].push_back(1); //第i行的第0,i个数为1                else ans[i].push_back(ans[i - 1][j - 1] + ans[i - 1][j]);            }        }        return ans;    }};
      
     
    
   

提交后效率如下：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗：6.6 MB, 在所有 C++ 提交中击败了40.46% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/109192803 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！