专栏首页Euclid学习日记杨辉三角 II(leetcode.119)
原创

杨辉三角 II(leetcode.119)

1.数学方法

图片来自互联网

我们只需计算所求行的值就可以了

Cnk​=n!/(k!(n−k)!)=(n∗(n−1)∗(n−2)∗...(n−k+1))/k!

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result;
        for(int i = 0;i <= rowIndex;i++){
            result.push_back(C(rowIndex, i));
        }
        return result;
    }
    int C(int n, int k){
        long res = 1;
        for(int i = 1;i <= k;i++){
            res = res * (n - k + i)/i; 
        }
        return (int)res;
    }
};

2.常规方法

因为只需要返回第k行的数组,所以只需要两个数组pre和res;

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

3.大佬的做法(✪ ω ✪)

膜拜~

可以看作是方法二的提升版本

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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最大子序列和(leetcode)

    euclid
  • 合并两个有序数组(leetcode.88)

    euclid
  • 杨辉三角动态规划(leetcode.118)

    euclid
  • 牛客练习赛33 D. tokitsukaze and Inverse Number(逆序数定理)

    题目链接:https://ac.nowcoder.com/acm/contest/308/D

    Ch_Zaqdt
  • CodeForces D.Powerful array(Div.1)

     大意是是说,问区间[L,R]内的的一个值,这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle,...

    mathor
  • HDU 6318 树状数组求逆序数

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6318

    用户2965768
  • ECJTUACM16 Winter vacation training #5 题解&源码

    A-------------------------------------------------------------------------------...

    Angel_Kitty
  • 图论--LCA--树上倍增法(在线)

    风骨散人Chiam
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack

扫码关注云+社区

领取腾讯云代金券