LeetCode & 118-Pascal's Triangle-Easy

Array

Description:

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]

]

这题依旧没写出来，看到要返回的是List<List<Integer>>直接就蒙了。感想就是，我好菜好菜好菜，一定一定要看Java源码！然后恶补了Arraylist源码，再次感叹Best Solution比我厉害多了。

Best Solution:

public class Solution {

    public List<List<Integer>> generate(int numRows) {

        List<List<Integer>> list = new ArrayList<List<Integer>>();

        ArrayList<Integer> row = new ArrayList<Integer>();

        for (int i = 0; i < numRows; i++) {

            // 注意每次在队首加1，其他元素后移

            row.add(0, 1);

            for (int j = 1; j < i; j++) {

                row.set(j, row.get(j) + row.get(j+1));

            }

            list.add(new ArrayList<Integer>(row));

        }

        return list;

    }

}

刚开始没有理解这个解法的思想，因为对大循环不理解，row.add(index, element)这一步很关键，把最新的这行数组复制了前一行内容，并在队首加1，其余元素后移，这样在row.set(index, element)就很自然的将两元素值相加得到新的值。

在此说明在看源码过程中得到的收获：

Arraylist.add(index, element)

public void add(int index, E element) {

  //判断索引位置是否正确

  rangeCheckForAdd(index);

  // 扩容检测

  ensureCapacityInternal(size + 1);  // Increments modCount!!

  // 复制现有数组，后移一位

  System.arraycopy(elementData, index, elementData, index + 1,

                         size - index);

  elementData[index] = element;

  size++;

}

Arraylist.add(element)

public boolean add(E e) {

  // 从队尾插入

  ensureCapacityInternal(size + 1);  // Increments modCount!!

  elementData[size++] = e;

  return true;

}

此处主要区分：add(0,1)和add(1)的区别，一个在队首插入，一个队尾插入

Arraylist.set(index, element)

public E set(int index, E element) {

  rangeCheck(index);

  // 在index位置上替代，故先add才能set

  E oldValue = elementData(index);

  elementData[index] = element;

  return oldValue;

}

巴特西

LeetCode & 118-Pascal's Triangle-Easy

最新文章

热门文章