leetcode 118. Pascal's Triangle 杨辉三角形

Bertha 。 2022-06-08 04:17 146阅读 0赞

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,  
Return

\[  
\[1\],  
\[1,1\],  
\[1,2,1\],  
\[1,3,3,1\],  
\[1,4,6,4,1\]  
\]

这个就是中国最伟大的杨辉三角形的问题。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /*
     * 中国最伟大的杨辉三角形
     * */
    public class Solution 
    {
        public List<List<Integer>> generate(int numRows) 
        {
            List<List<Integer>> res=new ArrayList<>();
            if(numRows==0)
                return res;
            else if(numRows==1)
            {
                List<Integer> one=new ArrayList<>();
                one.add(1);
                res.add(one);
                return res;
            }else
            {
                List<Integer> one=new ArrayList<>();
                one.add(1);
                one.add(0);
                res.add(one);
                for(int i=1;i<numRows;i++)
                {
                    List<Integer> tt=res.get(i-1);
                    List<Integer> rr=new ArrayList<>();
                    rr.add(tt.get(0));
                    for(int j=1;j<tt.size();j++)
                        rr.add(tt.get(j) + tt.get(j-1));
    
                    rr.add(0);
                    res.add(rr);
                }
                for(int i=0;i<res.size();i++)
                    res.get(i).remove(res.get(i).size()-1);
                return res;
            }
        }
    }

下面是C++的做法，这个是中国最经典的杨辉三角形的问题

代码如下：

#include <iostream>
    #include <string>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<vector<int>> generate(int n) 
        {
            vector<vector<int>> res;
            if (n == 0)
                return res;
            else if (n == 1)
            {
                vector<int> one{ 1 };
                res.push_back(one);
                return res;
            }
            else
            {
                vector<int> one{ 1 ,0};
                res.push_back(one);
                for (int i = 1; i < n; i++)
                {
                    vector<int> one{res[i-1][0]};
                    for (int j = 1; j < res[i - 1].size();j++)
                        one.push_back(res[i - 1][j]+ res[i - 1][j-1]);
                    one.push_back(0);
                    res.push_back(one);
                }
                for (int i = 0; i < res.size(); i++)
                    res[i].erase(res[i].end()-1);
                return res;
            }
        }
    };