【数据结构Java版】杨辉三角中ArrayList的运用

左手的ㄟ右手 2024-04-03 11:54 30阅读 0赞

前情提要：关于List<List<String>>的理解

List<List<String>>可以拆解成

List<这个List的元素的类型>

List<元素的类型>

![0be4888f78c0478f8fbf7e63e1fa2861.png][]

import java.util.ArrayList;
    import java.util.List;
    
    public class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> ans = new ArrayList<>();
            if (numRows == 0) {
                return ans;   // 里面一行都没有
            }
    
            ans.add(new ArrayList<>());
            ans.get(0).add(1);
            if (numRows == 1) {
                return ans; // { { 1 } }
            }
    
            ans.add(new ArrayList<>());
            ans.get(1).add(1);
            ans.get(1).add(1);
            if (numRows == 2) {
                return ans; // { { 1 }, { 1, 1 } }
            }
    
            for (int i = 3; i <= numRows; i++) {
                // 结果中需要多添加一行
                List<Integer> curLine = new ArrayList<>();
                ans.add(curLine);
                // 新添加的这行的第一个元素一定是 1
                ans.get(i - 1).add(1);  // 等价于 curLine.add(1)
                // 处理除了最后一个元素以外的其他元素
                // 这个是第 i 行，一共有 i 个元素，除去第一个和最后一个，还剩 i - 2 个元素
                for (int j = 0; j < i - 2; j++) {
                    // j = 0 的时候，需要计算该行的第 2 个元素
                    // 由上一行的第 1 个元素和第 2 个元素相加
                    // j = 1 的死后，需要计算该行的第 3 个元素
                    // 由上一行的第 2 个元素和第 3 个元素相加
                    // 计算该行的 j + 2 个元素
                    // 由上一行的 j + 1 个元素和 j + 2 个元素
                    // 换成下标之后，统一减一
                    // 上一行的 [j] 和 [j + 1] 的元素
                    // 当前行的下标 [i - 1]，上一行的下标就是 [i - 2]
                    // 先得到上一行
                    List<Integer> prevLine = ans.get(i - 2);
                    int first = prevLine.get(j);
                    int second = prevLine.get(j + 1);
                    int e = first + second;
                    curLine.add(e);
                }
                // 该行的最后一个元素还是 1
                curLine.add(1);
            }
    
            return ans;
        }
    
        public static void main(String[] args) {
            Solution solution = new Solution();
            System.out.println(solution.generate(0));
            System.out.println(solution.generate(1));
            System.out.println(solution.generate(2));
            System.out.println(solution.generate(3));
            System.out.println(solution.generate(4));
        }
    }

![373fd27dbdfa43fba47755405e38ad41.png][]

[0be4888f78c0478f8fbf7e63e1fa2861.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/cf93c410719649f195c4753f65d5875e.png
[373fd27dbdfa43fba47755405e38ad41.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3bc9738431424cf2ab242b0ff64e85a2.png