【leetcode】118. Pascal's Triangle

@requires_authorization
@author johnsondu
@create_time 2015.7.23 19:54
@url [Pascal‘s Triangle](https://leetcode.com/problems/pascals-triangle/)
/************************
 * @description: simple.
 * @time_complexity:  O(n)
 * @space_complexity: O(n)
 ************************/
 class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;

        for(int i = 1; i <= numRows; i ++) {
            vector<int> layer;
            if(i == 1) layer.push_back(1);
            else {
                for(int j = 1; j <= i; j ++) {
                    if(j == 1 || j == i)  layer.push_back(1);
                    else layer.push_back(ans[i-2][j-2] + ans[i-2][j-1]);
                }
            }
            ans.push_back(layer);
        }
        return ans;
    }
};
@requires_authorization
@author johnsondu
@create_time 2015.7.23 19:54
@url [Pascal‘s Triangle](https://leetcode.com/problems/pascals-triangle/)
/************************
 * @description: simple.
 * @time_complexity:  O(n)
 * @space_complexity: O(n)
 ************************/
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        if(numRows < 1) return ans;

        vector<int> first;
        first.push_back(1);
        ans.push_back(first);
        if(numRows < 2) return ans;

        vector<int> second;
        second.push_back(1);
        second.push_back(1);
        ans.push_back(second);

        for(int i = 3; i <= numRows; i ++) {
            vector<int> layer;
            layer.push_back(1);
            for(int j = 0; j < ans[i-2].size()-1; j ++) {
                layer.push_back(ans[i-2][j] + ans[i-2][j+1]);
            }
            layer.push_back(1);
            ans.push_back(layer);
        }
        return ans;
    }
};

版权声明:本文为博主原创文章,未经博主允许不得转载。

【leetcode】118. Pascal's Triangle

时间: 07-22

【leetcode】118. Pascal's Triangle的相关文章

【LeetCode】119 - Pascal&#39;s Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3,Return [1,3,3,1]. Note:Could you optimize your algorithm to use only O(k) extra space? Solution: 1 class Solution { 2 public: 3 vector<int> getRow(int rowIndex){

[LeetCode] NO. 118 Pascal&#39;s Triangle

[题目] Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5,Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] [题目解析] 帕斯卡三角,又称杨辉三角,给一个行数,输出杨辉三角,需要结合杨辉三角的性质.我们主要根据这条性质来产生结果:每个数字等于上一行的左右两个数字之和.可用此性质写出整个杨辉三角.即

【LeetCode】Pascal&#39;s Triangle

Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5,Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这题别想用通项公式做,n choose m里面的连乘必然溢出,老老实实逐层用定义做. class Solution { public: vector<vector<

【LeetCode】【Python题解】Pascal&#39;s Triangle

Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 要求输入一个整数,返回一个表示杨辉三角的数组.我的方法是计算通项公式,首先是编写阶乘函数,然后计算C00,C10,C11即可 利用Python 的map嵌套可以很简洁地实现,核心代码只有一行! class So

【Leetcode】Pascal&#39;s Triangle II

题目链接:https://leetcode.com/problems/pascals-triangle-ii/ 题目: Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return [1,3,3,1]. Note: Could you optimize your algorithm to use only O(k) extra space? 思路: 要求空间复杂度为O

【leetcode】Pascal&#39;s Triangle I &amp; II (middle)

Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5,Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 思路:杨辉三角,直接按规律生成即可 vector<vector<int> > generate(int numRows) { vector<vector<int>>

【Leetcode】Pascal&amp;#39;s Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return [1,3,3,1]. Note: Could you optimize your algorithm to use only O(k) extra space? 思路:最简单的方法就是依照[Leetcode]Pascal's Triangle 的方式自顶向下依次求解,但会造成空间的浪费.若仅仅用一个vect

【LeetCode从零单排】No118 Pascal&#39;s Triangle

题目 Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5,Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 代码 public class Solution { public List<List<Integer>> generate(int numRows) { List<List

【leetcode】Pascal&#39;s Triangle II (python)

其实每一行的结果是二项式展开的系数,但是考虑到当给定的参数过大的时候,在求组合的过程中会出现溢出(中间过程要用到乘法),但是这样的算法的时间复杂度是O(N),所以在参数不太大的时候,还是不错的. 这里用迭代的方法来求,当然复杂度就高了,是O(N^2),这里主要说下迭代时候的技巧,即在一个列表(数组)里进行迭代,实现如此的操作,要求在求下一行的时候,要从后往前进行,若是从前向后,就把后面要用的变量给改掉了,产生"脏"数据.从后向前不会(为何?),因为下一行比上一行多一个.(自己写写例子看