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? vector<int> getRow(int rowIndex) { if(rowIndex == 0) return vector<int>(1,1); vector<int>res(rowIndex+1,0); //approach 1: O(N^2) for(int i=1; i<= rowIndex; i++){ for(int j=i; j>=0; j--){ if(j == i || j == 0){ res[j] = 1; } else{ res[j] += res[j-1]; } } } /* //approach 2: O(N) for(int i=1; i<= rowIndex/2; i++){ res[i] = res[rowIndex-i] = (long long int)res[i-1]*(rowIndex-i+1)/i; } */ return res;} 赞微海报分享
近期评论