LC-杨辉三角-记忆版
上一篇:LC-杨辉三角
上一篇讲了杨辉三角的算法,不过之前的算法存在一个问题,比如:文章来源:https://www.toymoban.com/news/detail-638950.html
a[5][3] = a[4][2] + a[4][3]
a[5][4] = a[4][3] + a[4][4]
我们可以看到计算a[5][3]和a[5][4]时都需要a[4][3]的值,之前我们是需要每次用到都重新计算,这样就比较耗时,有没有办法记住已经算过的值呢,当下次用的时候直接获取就不用重新计算了,以空间来换取时间。
我们可以新增一个二维数组,把计算的结果放到数组中,每次计算前先查看一下数组中是否存在,如果已存在就获取值,不存在再计算。
下面是修改后的代码:文章来源地址https://www.toymoban.com/news/detail-638950.html
public List<List<Integer>> generate(int numRors){
int[][] catchs = new int[numRors][numRors];
List<List<Integer>> a = new ArrayList<List<Integer>>();
for (int k = 0; k < numRors; k++) {
List temp= new ArrayList();
for (int l = 0; l <= k; l++) {
System.out.print(f(catchs,k, l)+" ");
temp.add(f(catchs,k, l));
}
a.add(temp);
System.out.println();
}
return a;
}
private int f(int[][] catchs,int i, int j) {//0 1
if (j == 0 || i == j) {
return 1;
}
if(catchs[i][j] != 0){
return catchs[i][j];
}
int i1 = f(catchs, i - 1, j - 1) + f(catchs, i - 1, j);
catchs[i][j] = i1;
return i1;
}
到了这里,关于LC-杨辉三角-记忆版的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!