LeetCode－118. Pascal's Triangle，119. Pascal's Triangle II

浅浅的花香味﹌ 2022-08-20 13:28 155阅读 0赞

**118**  
Problem:

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

Analysis:  
把握住原则：每一层的第i个位置，等于上一层第i-1与第i个位置之和。  
有的题解也用另一个列表记录上一层的列表，就像一个temp。本方法没有这么做

Answer:

public class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> result=new LinkedList<List<Integer>>();
            if(numRows==0) return result;
            for(int i=1;i<=numRows;i++){
                List<Integer> innerlist =new LinkedList<Integer>();
                innerlist.add(1);
                for(int j=1;j<i-1;j++){
                    int temp=result.get(i-2).get(j-1)+result.get(i-2).get(j);
                    innerlist.add(temp);
                }
                if(i>1) innerlist.add(1);
                result.add(innerlist);
            }
            return result;
        }
    }

--------------------

**119**  
Problem：

> Given an index k, return the kth row of the Pascal’s triangle.  
> For example, given k = 3,  
> Return \[1,3,3,1\].  
> Note:  
> Could you optimize your algorithm to use only O(k) extra space?

Analysis：  
这个题目和上一个题目差不多，如果不考虑占用空间的话，只在上一个答案的返回改为result.get(rowIndex)即可，  
Answer：

public class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> temp = new LinkedList<Integer>();
            for(int i=1;i<=rowIndex+1;i++){
                List<Integer> result =new LinkedList<Integer>();
                result.add(0,1);
                for(int j=1;j<i-1;j++){
                    result.add(j,(temp.get(j)+temp.get(j-1)));
                }
                if(i>1) result.add(i-1,1);
                temp=result;
            }
            return temp;
        }
    }

如果要满足题目use only O(k) extra space要求，则应该将temp删掉，这个时候需要列表的set函数替代add函数，因为add函数添加后其余之后的元素都自动向后移位，而set函数只是将其替换。  
Answer：

public class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> result =new LinkedList<Integer>();
            for(int i=1;i<=rowIndex+1;i++){
                for(int j=1;j<i-1;j++){
                    result.set(j-1,(result.get(j-1)+result.get(j)));
                }
                result.add(0,1);
            }
            return result;
        }
    }