LeetCode 118. 杨辉三角    原题链接    简单

作者： 作者的头像   小呆呆 ,  2020-07-31 01:11:55 ,  所有人可见 ,  阅读 650

6


1

题目描述

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

PascalTriangleAnimated2.gif

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

样例

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

算法分析

模拟

  • 对于每一行的元素，除了第一个和最后一个元素都是1之外，其余的元素(i,j)都是(i - 1,j - 1)和(i - 1,j)坐标的元素累加出来的结果

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    static List<Integer> path = new ArrayList<Integer>();//当前行的元素
    public List<List<Integer>> generate(int n) {
        ans.clear();
        path.clear();
        if(n == 0) return ans;
        path.add(1);
        ans.add(new ArrayList(path));
        for(int i = 1;i < n;i ++)
        {
            path.clear();
            List<Integer> t = ans.get(ans.size() - 1);
            path.add(1);
            for(int j = 1;j < i;j ++)
                path.add(t.get(j - 1) + t.get(j));
            path.add(1);
            ans.add(new ArrayList(path));
        }
        return ans;
    }
}

2 评论

用户头像
hiJoe   2020-09-30 16:09         踩      回复

https://www.acwing.com/solution/content/7011/

class Solution {
    public List<List<Integer>> generate(int n) {
        List<List<Integer>> res = new ArrayList<>();
        int[] f = new int[n + 1];

        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>();
            f[i] = 1;
            for (int j = i - 1; j > 0; j--) {
                f[j] = f[j] + f[j - 1];
            }
            for (int k = 0; k <= i; k++) list.add(f[k]);
            res.add(list);
        }
        return res;
    }
}
用户头像
k8s   2022-03-08 14:18         踩      回复

tql