博客

解题思路：杨辉三角可以用队列（list）来做，杨辉三角从第一行开始就是没两个相邻数相加得到下面的一个数，其中的1可以看做是0+1得来的，所以第一行可以设为list1=（0,1,0），设一个队列头=0，每次从list1集合里面取出一个，加上队列头，然后存入list2队列中，再将取出来的值设为队列头。遍历完后，就在list2里面加上一个0，因为上一行最后一个数是没有的，再将这个队列赋值给list1以此下去，将list2里面的值都放到list3中。

这是在B站看到的

实现代码：

package 蓝桥杯;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import 编程练习题.foreach语句;

public class 杨辉三角 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		long N=scanner.nextLong();
		//list1用来存放用来生成下一行数字的层
		List<Long> list1=new ArrayList<>();
		//list2用来存放生成的层
		List<Long> list2=new ArrayList<>();
		//list3是用来存放所有的层
		List<Long> list3=new ArrayList<>();
		//list4用来找N所在位置的
		List<Long> list4=new ArrayList<>();
		//初始化第一行
		list1.add(0L);list1.add(1L);list1.add(0L);
		//将第一层放list3里面去
		list3.addAll(list1);
		//设置队列头
		long pre=0;
		//设置循环的次数（杨辉三角的层数）,具体多少层，这是个坑，后面会说
		for (int i = 0; i < 40; i++) {
			while (list1.size()!=0) {
				//每次从队列取出第一个数据
				long now=list1.remove(0);
				//将pre和now的和加入list2，作为下一行的值
				list2.add(pre+now);
				//然后将now作为队列头
				pre=now;
			}
			//此时list2后面是缺少一个0的，我们加上
			list2.add( 0L);
			
			//将list2的值放到list3中去
			list3.addAll(list2);
			
			//将list1中的数据清掉，用来存放list2，进行下一轮的遍历
			list1.clear();
			list1.addAll(list2);
			list2.clear();
			
			
			
		}
		//遍历list3，将不是零 的值加到list4里面
		
		for(long l:list3) {
			if (l!=0) {
				list4.add(l);
			}
		}
		for(long l:list4) {
			System.out.println(l);
		}
		//从list中找出N的位置
		System.out.println(list4.indexOf(N)+1);
		
	}

}

要是杨辉三角中的数N不存在的话，就会返回0，题目他不是指最大数达到1000000000就可以了，而是到底要多少层，才会有1000000000内的所有数字，要是层数太大的话，内存就会超限。

这就是我不懂的地方，

所以在这里请教一下大家