上一篇我们主要介绍了关于ArrayList和顺序表的一些相关知识内容,从它的定义到对ArrayList无参和有参构造的刨根问底,再到对ArrayList的扩容机制展开深层次的解析,那么今天就来讲一讲如何具体的使用到ArrayList。
一 .杨辉三角
1.1 认识杨辉三角
什么是杨辉三角呢?杨辉三角,也被称为贾宪三角形或帕斯卡三角形,是一种二项式系数在三角形中的几何排列。 这个概念最早由中国的贾宪在《释锁算术》中提出,后来南宋数学家杨辉在《详解九章算法》一书中进行了详细说明。在欧洲,帕斯卡于1654年独立发现了这一规律,因此这个表也被称为帕斯卡三角形。杨辉三角的发现比帕斯卡早约393年,比贾宪早约600年,是中国数学史上的一个伟大成就。
杨辉三角前十行如下图所示:
1.2 解析
从上方的图中我们可知:每一行的第一个值为1,每一行的最后一个值为1;杨辉三角的每个数字都是它上方两个数字之和,且每行的数字左右对称,从1开始逐渐变大。第n行的数字有n项,且数字之和为2^(n-1)。第n行的第m个数和第n-m+1个数相等,即C(n-1,m-1)=C(n-1,n-m),这是组合数性质的一部分。每个数字等于上一行的左右两个数字之和,可用此性质写出整个杨辉三角。
1.3 演示
下面是杨辉三角的动态图演示:
1.4 代码
理解了杨辉三角的构造之后,我们就可以开始写代码了:
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> list = new ArrayList<>();
list.add(1);
ret.add(list);
for (int i = 1; i < numRows; i++) {
List<Integer> curRow = new ArrayList<>();
//第一个
curRow.add(1);
//中间的
for (int j = 1; j < i; j++) {
//[i][j] = [i-1][j] + [i-1][j-1];
List<Integer> preRow = ret.get(i-1);
int x1 = preRow.get(j);
int x2 = preRow.get(j-1);
curRow.add(x1+x2);
}
//当前行 最后一个 1
curRow.add(1);
ret.add(curRow);
}
return ret;
}
1.5 代码逐步解析
首先来看前两行:
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<>();
}
这是一个嵌套List,我们可以理解为:当我们进行写入杨辉三角时,我们要把输入的值一个一个放到我们的ret里去:
刚开始的时候,我们的ret里面是空的,当我们要放进第一行元素的时候,因为第一行只有一个1,所以只需要list.add(1)就可以了。接下来我们就要从第二行开始就要用for循环进行逐行打印,我们这有numRows行就需要打印出numRows行元素,而当我们从第二行开始打印的时候,我们都需要实例化一个List用来存放我们的元素。我们说过,杨慧三角的每一行的第一个和最后一个元素都是1,所以在当前行我们先添加一个1进去 :
for (int i = 1; i < numRows; i++) {
List<Integer> curRow = new ArrayList<>();
//第一个
curRow.add(1);
从第二行的第二个元素开始,比如说第二行第二个元素,它的值等于它前一行(preRow)两个数字相加之和,
//中间的
for (int j = 1; j < i; j++) {
List<Integer> preRow = ret.get(i-1);
int x1 = preRow.get(j);
int x2 = preRow.get(j-1);
curRow.add(x1+x2);
}
对于当前位置(curRow)的值,比如说处在[i][j]位置上,它上方的两个数字x1和x2的下标就分别是[i-1][j]和[i-1][j-1] 。
最后,因为杨辉三角每一行最后一个元素总是为1,所以把最后一个数设置为1:
//当前行 最后一个 1
curRow.add(1);
//打印当前行
ret.add(curRow);
二.去重
2.1 题目
现在给我们两个字符串:
str1:welcome to Earth
str2:come
要求:使用到ArrayList,删除第一个字符串中所有字符串2出现过的字符,例如上面两个字符串最后的结果应该为:wl t Earth 。
2.2 解析
当我们读完上面的题目的时候,我们其实就能想到可以用遍历的方法去做,即,我们将str1中的每一个字符都逐个与str2中的进行比较,如果相同则把该字符删掉,如果不相同就把该字符放到我们的ArrayList中
public static void func(String str1,String str2) {
List<Character> list = new ArrayList<>();
for (i=0;i<str1.length();i++){
char ch = str1.charAt(i);
if(!str2.contains(ch)){
list.add(ch);
}
}
}
但是,当我们写完的时候,发生了报错:
我们点击cotains来看一看它的源码:
我们发现contains它的参数是CharSequence,而这里的CharSequence是String实现的一个接口
这也就意味着,我们至少要传递一个字符串过去,可是我们传递的是一个字符,所以它就会报错。所以判断条件我们需要稍微进行修改
if(!str2.contains(ch+"")){
list.add(ch);
}
那我们现在进行输出是不是就大功告成了呢,其实还并没有,因为这时当我们打印就会发现:
当我们输出的时候是以字符串的形式输出的,这样看其实并不美观,我们要让它一个一个字符输出。所以我们的代码再进行最后的加工:
public static void func(String str1,String str2) {
List<Character> list = new ArrayList<>();
for (int i = 0; i < str1.length(); i++) {
char ch = str1.charAt(i);
if (!str2.contains(ch + "")) {
list.add(ch);
}
}
//System.out.println(list);
for (char ch:list){
System.out.println(ch);
}
}
打印结果: