Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle. In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]题意：给定一个非负整数 numRows ，生成杨辉三角的前 numRows 行。
开始写的C++代码如下：
class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> ans; if (numRows == 0) return ans; ans.push_back(vector<int>{1}); if (numRows == 1) return ans; ans.push_back(vector<int>{1, 1}); if (numRows == 2) return ans; for (int i = 2; i < numRows; ++i) { ans.push_back(vector<int>{1}); int size = ans[i - 1].size(); for (int j = 0; j < size - 1; ++j) ans[i].push_back(ans[i - 1][j] + ans[i - 1][j + 1]); ans[i].push_back(1); } return ans; } };运行效率如下：
执行用时：4 ms, 在所有 C++ 提交中击败了38.91% 的用户 内存消耗：6.9 MB, 在所有 C++ 提交中击败了5.03% 的用户20201206 Update 今日打卡更新Java代码：
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> ans = new ArrayList<>(); int[][] arr = new int[numRows][numRows]; for (int i = 0; i < numRows; ++i) { List<Integer> subList = new ArrayList<>(); for (int j = 0; j <= i; ++j) { if (j == 0 || j == i) arr[i][j] = 1; else arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; subList.add(arr[i][j]); } ans.add(subList); } return ans; } }运行效率见下：
执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：36.5 MB, 在所有 Java 提交中击败了34.00% 的用户这样写得太繁琐了，简化如下：
class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> ans(numRows); for (int i = 0; i < numRows; ++i) { for (int j = 0; j < i + 1; ++j) { //第i行的数字个数为i+1 if (j == 0 || j == i) ans[i].push_back(1); //第i行的第0,i个数为1 else ans[i].push_back(ans[i - 1][j - 1] + ans[i - 1][j]); } } return ans; } };提交后效率如下：
执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户 内存消耗：6.6 MB, 在所有 C++ 提交中击败了40.46% 的用户