本文共 4092 字，大约阅读时间需要 13 分钟。
杨辉三角介绍
首先我们先看一下杨辉三角长什么样子
[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] 以此类推...分析
不难发现，观察后可以得出以下结论：
1.两边都是数字"1"
2.从第三行开始，除了两边的数字"1"之外的数字都是由"肩膀上"的数字相加得到的。
代码实现
对于一些对算法不太熟悉的人，如果直接去打印，可能就比较困难，所以我们不妨拆开几步来做。
第一步：打印一个数字都是"0"的三角形
这是比较简单的，第一行是1个数字，第二行是2个数字，第三行是3个数字，以此类推，我们可以归纳得到这样一个规律：第n行有n个数字。于是很容易我们就可以写出以下代码：
public class Main { public static void main(String[] args) throws Exception { List<List<Integer>> list = new Main().generate(5); System.out.println(list); } public List<List<Integer>> generate(int numRows) { if (numRows == 0) { return new ArrayList<>(); } List<List<Integer>> linkedList = new LinkedList<>(); //行数 for (int i = 1; i <= numRows; i++) { List<Integer> list = new LinkedList<>(); //列数 for (int j = 0; j < i; j++) { list.add(0); } linkedList.add(list); } return linkedList;}调用main方法我们可以在控制台看到以下输出：
[[0], [0, 0], [0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0, 0]]这里已经可以看出我们获得了一个都是"0"的三角形了！只是打印出来不好看，所以我们再写一个方法，遍历一下这个集合，打印得更好看一点。没什么技术含量，可以照抄，代码如下：
public static void printGenerate(List<List<Integer>> list){ for (int i = 0; i < list.size(); i++) { for (int j = 0; j < list.size() - i; j++) { //打印每一行前面的空格 System.out.print(" "); } List<Integer> integers = list.get(i); for (Integer integer : integers) { //后面的数字，再加上一个空格 System.out.print(integer + " "); } //换行 System.out.println(); }}然后运行一下，我们就可以看到一个很漂亮的三角形。但是这只是第一步。
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 第二步：把边上的数字"0"换成数字"1"
这个其实很简单，只需要把每一列的第一个和最后一个换成1，其他的不变即可。代码如下：
public List<List<Integer>> generate(int numRows) { if (numRows == 0) { return new ArrayList<>(); } List<List<Integer>> linkedList = new LinkedList<>(); for (int i = 1; i <= numRows; i++) { List<Integer> list = new LinkedList<>(); for (int j = 0; j < i; j++) { //判断每一列的第一个或者最后一个 if(j == 0 || j == i-1){ //数字为1 list.add(1); }else { //其他列保持不变，还是0 list.add(0); } } linkedList.add(list); } return linkedList;}于是我们就可以打印出这样子的三角形：
1 1 1 1 0 1 1 0 0 1 1 0 0 0 1第三步：中间为"0"的数字都改成用"肩膀上"的数字相加的结果
分析发现：
[1], 第1行 0 <--对应的索引值 [1,1], 第2行 0 1 [1,2,1], 第3行 0 1 2 [1,3,3,1], 第4行 0 1 2 3 [1,4,6,4,1] 第5行 0 1 2 3 4第三行的"2"是当前集合索引是[1]的值，是由第二行(上一个集合)索引是[0]的值"1"和索引是[1]的值"1"相加得到的。
第四行的第1个"3"是当前集合索引是[1]的值，是由第三行(上一个集合)索引是[0]的值"1"和索引是[1]的值"2"相加得到的。第2个"3"是当前集合索引是[2]的值，是由第三行(上一个集合)索引是[1]的值和索引是[2]的值相加得到的。
以此类推，我们可以得到这样一个结论：
除了首位和末尾的值以外，第n行的索引值为[ j ]的值是由第n-1行的索引值为[ j-1 ]和[ j ]相加得到。
所以我们可以判断从第3行开始，获取上一行的集合，然后除了首位和末尾的数值外(在第二步已经做了处理了)，其他的数值都是上一行索引值为[ j-1 ]和[ j ]的值相加而成的。
public List<List<Integer>> generate(int numRows) { if (numRows == 0) { return new ArrayList<>(); } List<List<Integer>> linkedList = new LinkedList<>(); List<Integer> preList = null; for (int i = 1; i <= numRows; i++) { List<Integer> list = new LinkedList<>(); if (i >= 3) { //大于或等于三行则获取上一行的集合 preList = linkedList.get(i - 2); } for (int j = 0; j < i; j++) { if (j == 0 || j == i - 1) //首位和末尾的数值都是1 list.add(1); else { //非首位，非末尾的情况 if (preList != null) { //数值是由上一行索引值为[j-1]和索引值为[j]相加得到的 list.add(preList.get(j - 1) + preList.get(j)); } } } linkedList.add(list); } return linkedList;}于是就写完了，我们可以打印出来看看结果：
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 如果输入的行数比较多，数字打印出来不对称，比如以下这样：
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 我们可以调整一下，以下就不去做打印的优化了，大家可以在评论里讨论，补上。
我还写了很多关于java技术的分享，有兴趣可以关注一下公众号，互相交流一下。
发表评论
最新留言
关于作者
