力扣118，1920题解

记录

2525.5.6

题目：

思路：

用一个二维数组dp[numRows][numRows]保存每一次动态规划的结果
1.令dp[0][0]=1(第一列)
2.找规律
3.得到如下规律(以下情况均为列数大于1)
if(col==0){
dp[row][col]=1
} else {
dp[row][col]=dp[row-1][col-1]+dp[row-1][col]
}

代码：

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> result=new ArrayList<List<Integer>>();int[][] dp=new int[numRows][numRows];dp[0][0]=1;for (int i = 1; i < numRows; i++) {for (int j = 0; j <=i; j++) {if(j==0)dp[i][j]=1;else dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}}for (int i = 0; i < dp.length; i++) {List<Integer> tmp=new ArrayList<>();for (int j = 0; j < dp.length; j++) {if(dp[i][j]==0) break;tmp.add(dp[i][j]);}result.add(new ArrayList<>(tmp));}return result;}
}

复杂度：

O（N²）
O（N²）

题目：

思路：

构建一个与原数组 nums 等长的新数组，同时令新数组中下标为 i 的元素等于 nums[nums[i]]。

代码：

class Solution {public int[] buildArray(int[] nums) {int n = nums.length;int[] ans = new int[n];for (int i = 0; i < n; ++i) {ans[i] = nums[nums[i]];}return ans;}
}

复杂度：

O（N）
O（N）