码疯窝

LeetCode 每日一题 — Pascal’s Triangle

2014/12/29 11:39:16    分类: 日志连载    0人评论 次浏览

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]
]

算法分析: 帕斯卡三角, 又称杨辉三角. 每个节点为上一层左右两个节点之和. 算法可以根据这个特性来写

Java:

public class Solution {
    public List> generate(int numRows) {
        List> rst = new ArrayList>();
        List line = new ArrayList();
        int i = -1;
        int p = -1;
        while((++i) < numRows) {
            line = new ArrayList();
            if (i == 0) {
                line.add(1);
            } else {
                p = -1;
                while((++p) < i + 1)
                    line.add((p == 0 || p == i) ? 1 : (rst.get(i - 1).get(p) + rst.get(i - 1).get(p - 1)));
            }
            rst.add(line);
        }
        return rst;
    }
}

C++:

class Solution {
public:
    vector > generate(int numRows) {
        vector> rst;
        vector line;
        int i = -1;
        int p = -1;
        while ((++i) < numRows) {
            if (i == 0) {
                line.push_back(1);
            } else {
                p = -1;
                while ((++p) < i + 1)
                    line.push_back((p == 0 || p == i) ? 1 : (rst[i - 1][p] + rst[i - 1][p - 1]));
            }
            rst.push_back(line);
        }
        return rst;
    }
};

Python:

class Solution:
    # @return a list of lists of integers
    def generate(self, numRows):
        rst = []
        line = []
        i = 0
        p = 0
        while (i < numRows):
            line = []
            if (i == 0):
                line.append(1)
            else:
                p = 0
                while (p < i + 1):
                    line.append(1 if (p == 0 or p == i) else rst[i - 1][p] + rst[i - 1][p - 1])
                    p += 1
            rst.append(line)
            i += 1
        
        return rst    
        
继续查看有关 日志连载的文章

0个访客评论