初刷leetCode--数组系列--Pascal's Triangle&Pascal's Triangle II(杨辉三角)

前言

接着上一章节的Maximum Subarray（最大连续子序列）的问题，继续筛选题目，中间跳过了几道题目

1. Plus One:需要注意最后一位为9与全为9的情况；
2. Merge Sorted Array：则是插入排序的问题，不了解的人请去翻阅数据结构；

接下来的连续两道杨辉三角的题目挺有趣，作为本文的重点。

这是杨辉三角第一题，这里在计算第k层的数组时，有个状态方程，首先定义初始状态

解题思路

k=1, PT[1][0] = 1;
k=2时, PT[1][0/1]=1,;
通过上边可知，当k>2时，每一层首尾都为1， PT[k][0]=1, PT[k][i]=PT[k-1][i-1]+PT[k-1][i]
对应的代码实现如下：

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

杨辉三角 II 问题描述

问题分析

这道题是上道题的变种，求第k层的结果。最简单的方法是，求出每一层，然后输出第k层的结果。但是这样不满足题目的空间复杂度是O(k)的要求。

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