119. Pascal's Triangle II

https://leetcode.com/problems/pascals-triangle-ii

 

D 풀이

-0- 다구하고 그냥 반환함 2차원 벡터 만들 필요없이 vector 2 개 선언해서 풀어도 가능해 보임

time complexity O(n)^2

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> arr;
        int cand = rowIndex + 1;
        arr.reserve(cand);
        for (int i = 1; i < cand + 1; i++) {
            vector<int> vi;
            for (int j = 0; j < i; j++) {
                vi.push_back(1);
            }
            arr.push_back(vi);
            vi.clear();
        }

        for (int i = 2; i < cand; i++) {
            int size = arr[i].size();
            for (int j = 1; j < size - 1; j++) {
                arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
            }
        }

        return arr[rowIndex];
    }
};

 

time complexity O(n)^2

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        rowIndex++;
        vector<int> arr(rowIndex);
        vector<int> brr(rowIndex);
        arr[0] = brr[0] = 1;
        if (rowIndex > 1) {
            brr[1] = 1;
        }
        if (rowIndex == 2) {
            return brr;
        }
        for (int i = 2; i < rowIndex; i++) {
            int cand = i + 1;
            for(int j=1; j<cand; j++) {
                arr[j] = brr[j] + brr[j - 1];
            }
            brr = arr;
        }
        return arr;
    }
};