java - Pascal's Triangle - 算法在 C++ 中工作，但在 java 中得到“超过时间限制”

Question

一个 leetcode 问题：给定 numRows，生成 Pascal 三角形的前 numRows。

该算法的 C++ 版本被 Leetcode 接受。谁能告诉我为什么这个 Java 版本不能被接受？

    public class Solution {

    public List<List<Integer>> generate(int numRows) {

    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (numRows == 0) return result;

    List<Integer> raw = new ArrayList<Integer>();
    raw.add(1);
    result.add(raw);
    if (numRows == 1) return result;

    List<Integer> row  = raw;
    List<Integer> row2 = raw;
    for (int i = 2; i <= numRows; i++) {
        for (int j = 0; j < row.size()-1; j++)
            row2.add(row.get(j) + row.get(j+1));
        row2.add(1);
        result.add(row2);
        row = row2;
        row2 = raw;
    }

    return result;
}
}

Answer 1

谁能告诉我为什么这个 Java 版本不能被接受？

因为你的代码永远运行。

你正好有一个 List<Integer>，而且还在不断增长：

for (int j = 0; j < row.size()-1; j++)
        row2.add(row.get(j) + row.get(j+1));

在每次迭代中，您向前移动一个元素并将一个元素添加到同一个列表中，本质上是永远追逐不断消失的终点。

（我在 uni 有一个朋友，他最初也不了解引用在 Java 中是如何工作的，并且在使用 Lists 时犯了类似的错误。他在 Swing GUI 中得到了无数个按钮。）