使用ArrayList构建帕斯卡三角

2017-07-24  本文已影响0人  书胆文心录

以下是「Core Java for the Impatient」一书第一章的第15道习题及解答。
题目:

Write a program that stores Pascal’s triangle up to a given n in an ArrayList<ArrayList < Integer >>.

解答:
思路

  1. 把ArrayList的元素当成三角形的每一行
  2. 每行第一位和最后一位必然是1,每行第n位数等于上一行的第n-1位和第n位的和

代码

import java.util.ArrayList;

public class Solution15 {
    public static void main(String[] args) {
        for (ArrayList<Integer> line : storePascalTriangle(15)) {
            for (int i : line) {
                System.out.printf("%5d", i);
            }
            System.out.println();
        }
    }

    public static ArrayList<ArrayList<Integer>> storePascalTriangle(int n) {
        ArrayList<ArrayList<Integer>> triangle = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> row = new ArrayList<Integer>();
            // 每行第一个数必然是1
            row.add(0, 1);
            if (i != 0) {
                for (int j = 1; j < i; j++) {
                    row.add(j, triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));
                }
                // 每行最后一个数也是1
                row.add(1);
            }
            triangle.add(i, row);
        }

        return triangle;
    }
}
上一篇下一篇

猜你喜欢

热点阅读