118. 杨辉三角

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

很简单，只要按照题目中所给的动画实现就可以了

class Solution {
          
   
    public List<List<Integer>> generate(int numRows) {
          
   
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        ArrayList<Integer> array;
        for(int i=0;i<numRows;i++){
          
   
            array=new ArrayList<Integer>();
            for(int j=0;j<=i;j++){
          
   
                if(j==0||j==i){
          
   
                //如果是一行的头或者尾，直接1即可
                    array.add(1);
                }else{
          
   
                //如果上一行左右都有数字，则为二者的和
                    array.add((int)ans.get(i-1).get(j-1)+(int)ans.get(i-1).get(j));
                }
            }
            ans.add((ArrayList)array.clone());
        }
        return ans;
    }
}

119. 杨辉三角 II

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

偷个懒其实上一题结果拿来输出第k行就完事了

但是效率嘛有点低

其实杨辉三角的每一个特定位置都是可以直接算出来的

这就要从杨辉三角怎么来的说起了

杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。 ——某度某科

简单来说，杨辉三角中第n行其实就是（X+Y）n 的多项式展开系数，以X（或Y）幂次大小顺序排列。

比如说，第1行就是（X+Y）¹ 也就是1X+1Y所以第一行为2个1，第3行是（X+Y）³ 等于1X³+3X² Y+3XY² +1Y³ 对应的就是[1，3，3，1]…

第一行那个1大概是为了凑个三角形？

为啥能像题目中动画一样计算三角中每一个数的值呢？

假设我们已经知道第三行[1,3,3,1]

需要求第四行第二个数，通过动画我们知道是1+3=4，为啥？

首先我们知道第三行对应（X+Y）³ =1X³+3X² Y+3XY² +1Y³

其次我们知道第四行对应（X+Y）4 =（X+Y）3 *（X+Y），而我们要找的系数是X3Y对应的系数

而：X3Y=X3*Y||X2Y*X 也就是说，（X+Y）3 中所有X3乘以多加的那个（X+Y）中的Y再加上（X+Y）3中所有X2Y乘以多加的那个（X+Y）中的X

就是下一行对应的所有 X3Y，即1+3=4

那么怎么直接计算第n行的第m个数呢？

只要算出n个（X+Y）相乘展开的多项式中，Xn-m+1Ym-1 的系数就可以了

也就是从n个（X+Y）中，无顺序得取出n-m+1个X，剩下的Y自然就出来了

直接算C（n,n-m+1）就是答案

其实第n行就是[C(n,0),C(n,1),C(n,2),…C(n,n-1),C(n,n)]

因为对于i+j=n C(n,i)=C(n,j)所以三角是对称的（XY等价也可以解释）

class Solution {
          
   
    public List<Integer> getRow(int rowIndex) {
          
   
        List<Integer> ans=new ArrayList<Integer>();
        int a=1,b=rowIndex;
        ans.add(1);
        for(int i=0;i<rowIndex;i++){
          
   
            ans.add((int)((long)ans.get(i)*(long)b/(long)a));
            a++;
            b--;
        }
        return ans;
    }
}