Leetcode 118) Pascal’s Triangle

21 May 2021 in Algorithms

• deep copy, shallow copy에 대해서
• 다른 코드는 for문 앞에 항상 어레이를 초기화 해서 deep copy 굳이 필요하지 않게 했다

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList<Integer>(Arrays.asList(1)));
        if(numRows==1){
            return result;
        }
        List<Integer> prev = new ArrayList<>();
        result.add(new ArrayList<Integer>(Arrays.asList(1,1)));

        prev.add(1);
        prev.add(1);
        for(int i =2;i<numRows;i++){
            List<Integer> now = new ArrayList<>();
            now.add(1);
            for(int j=0; j<prev.size()-1;j++){
                int val=prev.get(j)+prev.get(j+1);
                now.add(val);
            }
            now.add(1);
            prev.clear();
            for(int p : now) {
                prev.add(p);
            }
            result.add(now);
        }
        return result;
    }
}

다른 풀이

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList();

        for(int i = 1; i <= numRows; i++){
            List<Integer> list = new ArrayList(i);
            for(int j = 0; j < i; j++){
                if(j == 0 || j == i - 1){
                    list.add(1);
                }
                else{
                    list.add(result.get(i-2).get(j-1) + result.get(i-2).get(j));
                }

            }
            result.add(list);
        }
        return result;
    }
}