leetcode 119. Pascal's Triangle II 杨辉三角形2

旧城等待， 2022-06-08 04:17 130阅读 0赞

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,  
Return \[1,3,3,1\].

就是中国最伟大的杨辉三角形。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class Solution 
    {
        public List<Integer> getRow(int rowIndex)
        {
            List<List<Integer>> res=new ArrayList<>();
            if(rowIndex==0)
            {
                List<Integer> one=new ArrayList<>();
                one.add(1);
                res.add(one);
                return res.get(0);
            }else
            {
                List<Integer> one=new ArrayList<>();
                one.add(1);
                one.add(0);
                res.add(one);
                for(int i=1;i<rowIndex+1;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.get(rowIndex);
            }
        }
    }

下面是C++的做法，和上面的一道题一模一样，就是做一个迭代计算即可完成

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<int> getRow(int rowIndex) 
        {
            if (rowIndex == 0)
                return vector<int>(1,1);
            else
            {
                vector<vector<int>> res;
                vector<int> one{ 1 ,0 };
                res.push_back(one);
                for (int i = 1; i < rowIndex+1; 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[rowIndex];
            }
        }
    };