118. 杨辉三角

题目：

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

在杨辉三角中，每个数是它左上方和右上方的数的和。

解法：

class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> res; if (numRows < 1) return res; for (int i = 0; i < numRows; i++) { //每一行 vector<int> tmp(i+1, 1); //每一行初始化 for (int j = 1; j < i; j++) tmp[j] = res[i-1][j-1] + res[i-1][j]; //对除收尾的数计算赋值 res.push_back(tmp); } return res; } };

119. 杨辉三角 II

题目：

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

解法1：在118的基础上，保留上一行的结果

class Solution { public: vector<int> getRow(int rowIndex) { //行的index vector<int> res; if (rowIndex < 0) return res; for (int i = 0; i < rowIndex+1; i++) { //每一行 vector<int> tmp(i+1, 1); //新一行初始化 for (int j = 1; j < i; j++) tmp[j] = res[j-1] + res[j]; //根据上一行结果对新一行除收尾的数计算赋值 res = tmp; //保存上一行结果 } return res; } };

解法2：数组中数的个数原地扩充

class Solution { public: vector<int> getRow(int rowIndex) { //行的index if (rowIndex < 0) return vector<int>(); vector<int> res(rowIndex+1, 1); for (int i = 2; i < rowIndex+1; i++) { for (int j = i-1; j > 0; j--) //从右往前 res[j] = res[j-1] + res[j]; //计算前一个数和当前数对当前数进行覆盖 } return res; } };

         这种解法的关键点是每行从右向左算新一行的值，因为新一行的数个数更多，又是原地覆盖，从前往后会导致后面的数据不正确。这种思路就像原地替换空格一样，将空格用" "替代，需要从右往前操作，而若将“ ”用空格替代，需要从前往后操作，就是避免未处理数据被覆盖。