杨辉三角-ii

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> dp(rowIndex+1,1);
        for(int i=2;i<=rowIndex;i++)
        	for(int j=i-1;j>0;j--)
        		dp[j] = dp[j] + dp[j-1];
        return dp;        	
    }
};

//合理规划dp转移方向降低一个维度
class Solution {
public:
    vector<int> getRow(int rowIndex) {
         vector<int> dp(rowIndex+1,0);
         dp[0]=1;
         for(int i=1;i<=rowIndex;i++)
             for(int j=i;j>=1;j--)
                 dp[j]+=dp[j-1];
         return dp;
     }
};

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> row=new ArrayList<Integer>();
        rowIndex++;
		if(rowIndex==0)
			return row;
		row.add(1);
		for(int i=1;i<rowIndex;i++)
		{
			for(int j=i-1;j>0;j--)
			{
				row.set(j, row.get(j-1)+row.get(j));				
			}
			row.add(1);
		}
		return row;
    }
}

//  从后往前迭代
class Solution {

	public:



	vector<int> getRow(introwIndex) {



	vector<int> dp(rowIndex+1, 1);



	for(inti=2; i<rowIndex+1; i++) {



	for(intj=i-1; j>0; j--)



	dp[j] = dp[j]+dp[j-1];



	}



	returndp;



	}



	};

/**
 * 119. Pascal's Triangle II
 * 杨辉三角 II
 * 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
 * 在杨辉三角中，每个数是它左上方和右上方的数的和。
 * 示例: 输入: 3 输出: [1,3,3,1]
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> result = solution.getRow(4);
        System.out.println(result.toString());
    }

    public List<Integer> getRow(int rowIndex) {

        if (rowIndex < 0) {
            return null;
        }
        List<Integer> result = new ArrayList<>();
        result.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = result.size() - 2; j >= 0; j--) {
                result.set(j + 1, result.get(j) + result.get(j + 1));
            }
            result.add(1);
        }

        return result;

    }

}

import java.util.ArrayList;
 
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i <= rowIndex;i ++){
            list.add(1);
        }
        for(int i = 0; i <= rowIndex; i++){
        //从后往前遍历，防止上一行的左右两个数中的左边数在使用时已被更改
            for(int j = i; j >= 0; j--){
                if(j == i || j == 0){
                    continue;
                }
                else{
                    list.set(j, list.get(j-1) + list.get(j));
                }
            }
        }
        return list;
    }
}

import java.util.ArrayList;
 
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<>();
        int n = rowIndex + 1;
        //防止溢出，使用long
        long number = 1;
        for(int i = 1; i <= n; i++){
           list.add((int)number);
           number = number * (n - i) / i;
        }
        return list;
    }
}

//思路:从后往前计算，从而避免了之前的数据被覆盖。满足空间复杂度为O(n)
public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> row=new ArrayList<>();
        if(rowIndex<0) return row;
        for(int i=0;i<rowIndex+1;i++){
            for(int j=i-1;j>0;j--){
                row.set(j,row.get(j)+row.get(j-1));
            }
            row.add(1);
        }
        return row;
    }

比各位的还要快一点点 由于杨辉三角是对称的
只要dp一半就可以了
ps:一开始赋初值为1简化运算

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> res(rowIndex + 1, 1);
        for(int i = 1; i < rowIndex; i++)
            for(int j = (i + 1)/2; j >= 1; j--)
                res[i + 1 - j] = res[j] += res[j-1];          
        return res;
    }
};

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int>res;
        int dp[rowIndex+1];
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=0;i<rowIndex;i++){
          for(int j=i+1;j>=1;j--){
             dp[j]+=dp[j-1];
         }   
        }
        for(int i=0;i<rowIndex+1;i++)
            res.push_back(dp[i]);
        return res;
    }
};

import java.util.*;
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<>(rowIndex+1);
        list.add(1);
        for(int i = 1; i <= rowIndex; i++){
            list.add(0);
        };
        for(int i = 1; i <= rowIndex; i++){
            int tmp = 1;
            for(int j = 1; j <= i; j++ ){
                int now = tmp+list.get(j);
                tmp = list.get(j);
                list.set(j, now);
            }
        }
        return list;
    }
}

O(k)做法。
杨辉三角，第n行第m个数的值为C(m-1,n-1).
用double来进行乘除运算，会出现精度问题，
所以我们要进行精度控制，若大于等于eps我们则向上取整，若小与我们则向下取整即可。

public ArrayList<Integer> getRow(int rowIndex) {
        double eps=1e-6;
        ArrayList<Integer> res=new ArrayList<Integer>();
        if(rowIndex==0){
            res.add(1);
            return res;
        }
        rowIndex+=1;
        res.add(1);
        double up;
        double down;
        double re=1;
        for (int i = 2; i <= rowIndex-1; i++) {
            down=i-1;
            up=rowIndex-i+1;
            re=re/down*up; 
            if(re-(int)re<eps){  
                re=Math.floor(re);
            }else{
                re=Math.ceil(re);
            }
            res.add((int) re);
        }
        res.add(1);
        return res;
    }

class Solution {
public:
    //看大家都是直接用数组搞定的，我这里来一种稍微麻烦的一种做法，
    //主要是根据杨辉三角的性质来做：1、第k行的数字个数为k；2、第n行的
    //第m个数为C(n-1，m-1)，即为从n-1个不同元素中取m-1个元素的组合数。
    long permutation(int n,int m)
    {
         //递归求解组合数的函数
        if(m==0)
        {
            return 1;
        }else if(m==1)
        {
            return n;
        }else
            return n*permutation(n-1,m-1)/m;
    }
    vector<int> getRow(int rowIndex) {
        if(rowIndex<0)
            return vector<int>();
        vector<int> vRes;
        for(int i=0;i<=rowIndex;i++)
        {
            vRes.push_back(permutation(rowIndex,i));
        }
        return vRes;
    }
};

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result[2];
        int flag = 0;
        result[flag].push_back(1);
        for (int i = 1; i <= rowIndex; ++i) {
            int t_falg = flag ^ 1;
            result[t_falg].clear();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    result[t_falg].push_back(1);
                }
                else {
                    result[t_falg].push_back(result[flag][j-1] + result[flag][j]);
                }
            }
            flag ^= 1;
        }
        return result[flag];
    }
};

    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list =  new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++){
            if(i==0) {list.add(1);continue;}
            for(int j=0;j<list.size()-1;j++){
                int m=list.get(j+1);
                list.set(j+1,list.get(0)+list.get(j+1));
                list.set(0,m);
            }
            list.set(0,1);
            list.add(1);
        }
        return list;
    }

做这种模拟类型的算法题，有三个要诀：快、准、狠，缺一不可：

1. 快，时间控制在30分钟以内，这样才能预留充分时间给后面的题目
2. 准，找准边界条件
3. 狠，一旦有把握，毫不犹豫的动手写代码

此类题目很重要的几个特性：🅐对称 🅑旋转 🅒重复...，利用这些特性可以大大减少代码量

由于模拟类型题目变化多端，要做到快准狠实属不易，需要我们快速分析，快速找规律。以本题为例，当rowIndex=5时，数组为1 5 10 10 5 1，我们用1初始化这个数组，再一步步得出结果：

1. 1 1 1 1 1 1 边界为(0, 0) 中间节点为0
2. 1 1 1 1 1 1 边界为(0, 1) 中间节点为0
3. 1 2 1 1 1 1 边界为(0, 2) 中间节点为1
4. 1 3 3 1 1 1 边界为(0, 3) 中间节点为1
5. 1 4 6 4 1 1 边界为(0, 4) 中间节点为2
6. 1 5 10 10 5 1 边界为(0, 5) 中间节点为2

由于在边界内部是对称的，我萌可以从中间节点向一侧边界遍历，循环几遍即可得到最终的结果。

//
// Created by jt on 2020/9/2.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param rowIndex int整型
     * @return int整型vector
     */
    vector<int> getRow(int rowIndex) {
        // write code here
        vector<int> res(rowIndex+1, 1);
        for (int i = 2; i <= rowIndex; ++i) {
            for (int j = i / 2; j > 0; --j) {
                res[j] = res[j] + res[j-1];
                res[i-j] = res[j];    // 对称
            }
        }
        return res;
    }
};