leetcode 随笔 Pascal's Triangle Pascal's Triangle II

最近没有停止刷题，只不过大概从90到117几乎全部是二叉树的问题，所有的问题考察的几乎都是深度优先，广度优先等等，重复性很高，code基本都是一遍过，感觉没有什么整理的必要

今天终于不是二叉树了。。o(╯□╰)o

Pascal's Triangle

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> res(numRows);if(numRows<1) return res;int i=1;res[0].push_back(1);while(res[numRows-1].empty()){res[i].push_back(1);for(int k=1;k<i;k++){res[i].push_back(res[i-1][k-1]+res[i-1][k]);}res[i].push_back(1);i++;}return res;}
};

Pascal's Triangle II

这个问题稍微有点意思，由于题目限制的空间大小，开始我的思路与第一题类似，只不过存储的范围变成了一个向量，我隐隐觉得这个题应该是存在简单算法的，但是一开始没想到。

一开始的代码：

class Solution {
public:vector<int> getRow(int rowIndex) {vector<int> res;res.push_back(1);if (rowIndex == 0) return res;int index = 0;while (++index <= rowIndex){int t = res[0], i = 1;for (; i<ceil(index / 2.0); i++){int r = t;t = res[i];res[i] = res[i] + r;}if ((1 + index) % 2){res.push_back(2*t);}}int now_index = res.size() - 1;if ((1 + rowIndex) % 2) now_index--;for (int i = now_index; i >= 0; i--)res.push_back(res[i]);return res;}
};

提交完代码ac之后我看了一下discuss，下面的代码让我感受到了“代码之美”

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