LeetCode

118.Pascal's Triangle

question:

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

题解

杨辉三角可以看成是一个二维数组

以numRows=4为例
[
 [1],
 [1,1],
 [1,2,1],
 [1,3,3,1]
]
Y[i][j]=Y[i-1][j]+Y[i-1][j-1]
但是每一行两端的值为1

代码

class Solution {
public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1); //将两端的值设置为1
                } else {
                    row.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
                }
            }
            list.add(row); 
        }
        return list;
    }
}

119. Pascal's Triangle II

question

Given an integer rowIndex, return the rowIndexth row of the Pascal's triangle.

Notice that the row index starts from 0.

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

题解

首先每行都让它从0开始,以rowIndex = 3作为例

1
1, 1
1, 2, 1
1, 3, 3, 1

Y[i][j] = Y[i- 1][j-1] + Y[i - 1][j]
在处理第i行的时候,就是在覆盖i - 1行的内容, 所以其实上面二维优化成一维也就变成: Y[j] = Y[j - 1] + Y[j],
Y[j]在被覆盖前其实就是前一行的值Y[i-1][j], 但是Y[j-1]必须在覆盖前保存下来, 一个临时变量Left就足够了.

代码

class Solution {
 public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<Integer>();
     //填充list,将每个元素初始化为0
        for (int i = 0; i < rowIndex + 1; i++) {
            list.add(0);
        }
        for (int i = 0; i <= rowIndex; i++) {
            list.set(0,1); //设置第一个元素为1
            int left = 1;//先标记y-1为1
            for (int j = 1; j < i; j++) {
                int current = list.get(j); //便于下次运y[j+1],因为下一步操作会改变y[j]的值
                list.set(j, left+current);//y[j]=y[j]+y[j-1]
                left = current; //保存y[j]
            }
            list.set(i,1); //设置最后一个元素为1
        }
        return list;
    }
}
Pay by WeChat

Pay by WeChat

Comment

This is just a placeholder img.