使用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 >>.
解答:
思路
- 把ArrayList的元素当成三角形的每一行
- 每行第一位和最后一位必然是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;
}
}