1 预备知识-泛型(Generic)

1.1 泛型的引入

问题： 我们之前实现过的顺序表，只能保存 int 类型的元素，如果现在需要保存 指向 Person 类型对象的引用的顺序表，请问应该如何解决？如果又需要保存指向 Book 对象类型的引用呢？
回答：
首先，在学习多态过程中已知一个前提，基类的引用可以指向子类的对象。
其次，也已知 Object 是 java 中所有类的祖先类。
那么，要解决上述问题，我们很自然的想到一个解决办法，将我们的顺序表的元素类型定义成 Object 类型，这样我们的 Object 类型的引用可以指向 Person 类型的对象或者指向 Book 类型的对象了。这样，我们也就可以很自由的存储指向任意类型对象的引用到我们的顺序表了。
现在的 MyArrayList 虽然可以做到添加任意类型的引用到其中了，但会产生向下转型不安全，需要强制转换才能解决这个问题。
具体代码示例如下所示：

package Generic;
import org.omg.CORBA.Object;
/*
* 泛型是一个在java当中 比较难的语法
* *//*
* 题目：写一个通用的顺序表?
*     Object是所有类的父类，哪怕这个类没有继承Object
* *///通用的顺序表（不用泛型）
class MyArrayList{//public int elem;此时只能放int类型的元素public Object[] elem;//此时就能放所有类型的元素了public int usedSize;public MyArrayList(){this.elem = new Object[10];}public void add(Object data){this.elem[this.usedSize] = data;this.usedSize++;}public Object get(int pos){return this.elem[pos];}
}public class TestDemo {public static void main(String[] args) {/*Object[] elem = new Object[10];elem[0] = 10;elem[1] = "fsasa";*/MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(19.8);myArrayList.add("fsfsa");//String str = myArrayList.get(2);此时会报错，这里发生了向下转型，向下转型本来就是不安全的。所以此时要进行强制类型转换才不会报错String str = (String) myArrayList.get(2);System.out.println(str);}
}

注意： 问题暴露的越早，影响越小。编译期间的问题只会让开发者感觉到，运行期间的错误会让所有的软件使用者承受错误风险。所以我们需要一种机制，可以 （1）增加编译期间的类型检查；（2）取消类型转换的使用。泛型就此诞生！

1.2 泛型类的定义的简单演示

泛型类的定义:

// 1. 尖括号 <> 是泛型的标志
// 2. E 是类型变量(Type Variable)，变量名一般要大写
// 3. E 在定义时是形参，代表的意思是 MyArrayList 最终传入的类型，但现在还不知道
public class MyArrayList<E>{private E[] array;private int size;...
}

注意： 泛型类可以一次有多个类型变量，用逗号分割。

1.3 泛型背后作用时期和背后的简单原理

1. 泛型是作用在编译期间的一种机制，即运行期间没有泛型的概念。
2. 泛型代码在运行期间，就是我们上面提到的，利用 Object 达到的效果（这里不是很准确，以后会做说明）。

1.4 泛型类的使用

具体代码示例如下所示：

package Generic;
import org.omg.CORBA.Object;
/*
* 泛型是一个在java当中 比较难的语法
* 了解泛型就ok了 保存这份代码
* 以后可以当作字典进行查询
* *//*
* 泛型：只存在于编译时期 只是编译时期
*    意义：
*    1、自动进行类型的检查
*    2、自动进行类型转换
* 泛型 在编译的时候，并不会进行指定类型的替换，而是拿着指定的类型进行检查
*     也就是说在编译的时候，拿着你指定的类型进行检查，记住并没有说是替换
*
* 编译的时候会进行类型擦除，编译的时候 编译都会把泛型擦除为Object，不是替换为Object
*
* 题目：写一个通用的顺序表?
*     Object是所有类的父类，哪怕这个类没有继承Object
*
* 1、class MyArrayList<T>{   <T>:代表占位符，表示当前这个类是一个泛型类
* 2、简单类型不能做泛型类型的参数：
*         MyArrayList<int> myArrayList1 = new MyArrayList<String>();
* 3、不能new 泛型类型的数组  this.elem = new T[10];
* 4、泛型类型的参数 不参与类型的组成 --》 泛型就是在编译时期的一种机制
* *//*//通用的顺序表（不用泛型）
class MyArrayList{//public int elem;此时只能放int类型的元素public Object[] elem;//此时就能放所有类型的元素了public int usedSize;public MyArrayList(){this.elem = new Object[10];}public void add(Object data){this.elem[this.usedSize] = data;this.usedSize++;}public Object get(int pos){return this.elem[pos];}
}*/
//通用的顺序表（用泛型）
class MyArrayList<T>{//public int elem;此时只能放int类型的元素public T[] elem;//此时就能放所有类型的元素了public int usedSize;public MyArrayList(){// this.elem = new T[10];会报错，正确书写方式如下所示：this.elem = (T[])new Object[10];}public void add(T data){this.elem[this.usedSize] = data;this.usedSize++;}public T get(int pos){return this.elem[pos];}
}class Anima{}
class Cat extends Anima{}
class Bird extends Anima{public void fly(){}
}
class Person{}
public class TestDemo {public static void main(String[] args) {Person person = new Person();System.out.println(person);//类型@地址MyArrayList<String> myArrayList1 = new MyArrayList<>();System.out.println(myArrayList1);MyArrayList<Integer> myArrayList2 = new MyArrayList<Integer>();System.out.println(myArrayList2);MyArrayList<Double> myArrayList3 = new MyArrayList<Double>();System.out.println(myArrayList3);}public static void main4(String[] args) {MyArrayList<String> myArrayList1 = new MyArrayList<>();//后面尖括号里的东西可写可不写，一般情况下都不写myArrayList1.add("fsfsa");myArrayList1.add("feihan");myArrayList1.add("bit");String str = myArrayList1.get(2);//泛型自动进行了强制类型转换System.out.println(str);}public static void main3(String[] args) {Anima anima = new Cat();Bird bird = (Bird)anima;bird.fly();//此时是飞不起来的//这里牵扯到一个编译时多态和运行时多态//就是在编译的时候是anima这个对象，但是在运行时就是cat这个对象，所以说第一条语句执行完毕以后这个anima就是一个cat对象//现在要把cat这个对象转成bird对象肯定不行的，因为：//类型转换只能是父类子类之间相互转换，同类的不同派生的对象之间是不能相互转换的//所以它此时强转失败了，自然也不能飞起来了}public static void main2(String[] args) {//MyArrayList<int> myArrayList1 = new MyArrayList<String>();}public static void main1(String[] args) {/* *//*Object[] elem = new Object[10];elem[0] = 10;elem[1] = "fsasa";*//*MyArrayList myArrayList = new MyArrayList();myArrayList.add(1);myArrayList.add(19.8);myArrayList.add("fsfsa");//String str = myArrayList.get(2);此时会报错，这里发生了向下转型，向下转型本来就是不安全的。所以此时要进行强制类型转换才不会报错String str = (String) myArrayList.get(2);System.out.println(str);*/MyArrayList<String> myArrayList1 = new MyArrayList<String>();//后面尖括号里的东西可写可不写，一般情况下都不写//myArrayList1.add(1);//myArrayList1.add(19.8);myArrayList1.add("fsfsa");myArrayList1.add("feihan");myArrayList1.add("bit");String str = myArrayList1.get(2);//泛型自动进行了强制类型转换System.out.println(str);MyArrayList<Integer> myArrayList2 = new MyArrayList<Integer>();myArrayList2.add(1);myArrayList2.add(2);int val = myArrayList2.get(1);System.out.println(val);MyArrayList<Double> myArrayList3 = new MyArrayList<Double>();myArrayList3.add(19.8);}
}

通过以上代码，我们可以看到泛型类的一个使用方式：只需要在所有类型后边跟尖括号，并且尖括号内是真正的类型，即 T 可以看作的最后的类型。
注意： myArrayList 只能想象成 T 的类型，但实际上 T 的类型还是 Object。

1.5 泛型总结

1. 泛型是为了解决某些容器、算法等代码的通用性而引入，并且能在编译期间做类型检查。
2. 泛型利用的是 Object 是所有类的祖先类，并且父类的引用可以指向子类对象的特定而工作。
3. 泛型是一种编译期间的机制，即MyArrayList <Person> 和MyArrayList<Book> 在运行期间是一个类型。
4. 泛型是 java 中的一种合法语法，标志就是尖括号 <>。

2 预备知识-包装类（Wrapper Class）

Object 引用可以指向任意类型的对象，但有例外出现了，8 种基本数据类型不是对象，那岂不是刚才的泛型机制要失效了？
实际上也确实如此，为了解决这个问题，java 引入了一类特殊的类，即这 8 种基本数据类型的包装类，在使用过程中，会将类似 int 这样的值包装到一个对象中去。

2.1 基本数据类型和包装类直接的对应关系

基本数据类型和包装类直接的对应关系如下图所示：

基本就是类型的首字母大写，除了 Integer 和 Character。

2.2 包装类的使用，装箱(boxing)和拆箱(unboxing)

装包/装箱： 把简单类型 包装成 对应的包装类。
拆包/拆箱： 把包装类 变为 简单类型。
我们通过代码对装箱和拆箱进行理解，具体代码示例如下所示：

package Generic;
public class TestDemo {/** 装包/装箱：把简单类型 包装成 对应的包装类*    自动装包：*    显示装包：* 拆包/拆箱：把包装类 变为 简单类型*    自动拆箱：*    显示拆箱：* */public static void main(String[] args) {/** 选择题* */Integer a = 139;Integer b = 139;System.out.println(a == b);//范围的问题导致这个结果是true，还是false不一定}public static void main1(String[] args) {Integer i = 10;int a = i;//自动拆箱   底层其实也是调用了i.intValue()System.out.println(a);int a2 = i.intValue();//显示拆箱System.out.println(a2);double d = i.doubleValue();System.out.println(d);}public static void main2(String[] args) {int a = 10;Integer integer1 = new Integer(a);//显示的装包System.out.println(integer1);Integer integer2 = Integer.valueOf(a);//显示装包System.out.println(integer2);Integer integer3 = a;//自动装包  其实也是调用了Integer.valueOf}}

注意： 自动装箱和自动拆箱是工作在编译期间的一种机制。

3 List的使用

List是位于java.util下的一个接口,有序集合(也称为序列)。

3.1 常见方法

List（线性表）：

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

ArrayList（顺序表）：

方法	解释
ArrayList()	无参构造
ArrayList(Collection<? extends E> c)	利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)	指定顺序表初始容量

LinkedList(链表)：

方法	解释
LinkedList()	无参构造

代码示例如下所示：

package Generic;import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;public class TestDemo2 {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list);/* List<Integer> list1 = new ArrayList<>();list1 = list.subList(1,3);System.out.println(list1);list1.set(0,88);System.out.println(list1);System.out.println(list);*///迭代器 用来打印集合中的元素的Iterator<Integer> iterator = list.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}//建议大家慎用iterator.remove()iterator.remove();System.out.println(list);}public static void main1(String[] args) {ArrayList<Integer> list = new ArrayList<>();/** ArrayList底层是一个数组，每次放元素的时候都是放在了数组的最后。* public boolean add(E e){}  add的是一个boolean类型* public void add(int index,E element){}  这个方法是放在index位置* 问题：ArrayList底层是数组，那么他有多大？* 1.new ArrayList<>() 调用的是不带有参数的构造方法*   那么大小默认为0。* 2.当调用默认的构造方法之后，当你添加第一个元素的时候会进行扩容，第一系扩容的时候，大小为10；* 3.当后续进行扩容的时候，是进行了1.5倍的方式进行扩容* */list.add(1);System.out.println(list);ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(10);arrayList.add(20);list.addAll(arrayList);System.out.println(list);list.remove(1);/** remove这块要注意如果要remove的不是1下标对应的数字，而要remove数组中第一个见到的1，则应该这样做：*  Integer integer = 1;*  list.remove(integer);* */System.out.println(list);}
}

3.2 练习题

题目1： 学校有若干学生（学生对象放在一个List中），每个学生有一个姓名（String）、班级（String）和考试成绩属性（double）。每次考试结束后，每个学生都获得了一个考试成绩。遍历list集合，并把学生对象的属性打印出来。
解题代码如下所示：

package Generic;import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
class Student{public String name;public int age;public double score;//构造方法和toString方法的快捷键是alt+insertpublic Student(String name, int age, double score) {this.name = name;this.age = age;this.score = score;}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +", score=" + score +'}';}
}
public class TestDemo2 {public static void main(String[] args) {ArrayList<Student> list = new ArrayList<>();list.add(new Student("feihan",19,89.9));list.add(new Student("feihan1",29,99.9));//下面为四种不同的打印方式：/* for(int i = 0;i < list.size();i++){System.out.println(list.get(i));}*//*for(Student student : list){System.out.println(student);}*//*Iterator<Student> iterator = list.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}*/System.out.println(list);}}

题目2： 有一个List当中存放的是整型的数据，要求使用Collections.sort对List进行排序。
解题代码如下所示：

package Generic;import java.util.*;
public class TestDemo2 {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(10);list.add(9);Collections.sort(list);System.out.println(list);}}

题目三： 删除第一个字符串当中出现的第二个字符串中的字符。例如：

String str1 = “welcome to feihan”;
String str2 =“come”;
输出结果：wl t fihan

解题思路：

str1 = “welcome to feihan”
str2 =“come”;
拿着str1的每个字符，判断str2当中是否包含这个字符，如果不包含，那么就把这个字符放到ArrayList当中。

利用 ArrayList 解题代码如下所示：

package Generic;import java.util.*;public class TestDemo2 {public static List<Character> func(String str1,String str2){List<Character> ret = new ArrayList<>();for(int i =0;i < str1.length();i++){char ch = str1.charAt(i);//wif(!str2.contains(ch+"")){ret.add(ch);}}return ret;}public static void main(String[] args) {List<Character>  list = func("welcome to feihan","come");System.out.println(list);//换种打印方式for(int i = 0; i < list.size();i++){System.out.print(list.get(i));       }}}

利用 StringBuilder 解题代码如下所示：

package Generic;import java.util.*;public class TestDemo2 {public static String func(String str1,String str2){StringBuilder sb = new StringBuilder();for(int i =0;i < str1.length();i++){char ch = str1.charAt(i);//wif(!str2.contains(ch+"")){sb.append(ch);}}return sb.toString();}public static void main(String[] args) {String ret = func("welcome to feihan","come");System.out.println(ret);}}

题目四： 模拟扑克牌买牌、洗牌和发牌的过程。
解题代码如下所示：

package Generic;import java.util.*;class Card{public String suit;public int rank;public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {/* return "Card{" +"suit='" + suit + '\'' +", rank=" + rank +'}';*/return "["+suit+","+rank+"]";}
}
class DeckCard{public static final String[] suits ={"♥","♠","♦","♣"};public List<Card> buyCard(){List<Card> cardList = new ArrayList<>();for(int i = 0; i < 4;i++){for (int j = 0; j <=13 ; j++) {String suit = suits[i];int rank = j;Card card = new Card(suit,rank);cardList.add(card);}}return cardList;}public void swap(List<Card> cardList,int i,int j){Card tmp = cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}public void washCard(List<Card> cardList){for (int i = cardList.size()-1; i > 0 ; i--) {Random random = new Random();int rand = random.nextInt(i);swap(cardList,i,rand);}}
}public class TestDemo2 {public static void main(String[] args) {DeckCard deckCard = new DeckCard();List<Card> cardList = deckCard.buyCard();System.out.println("=========买牌============");System.out.println(cardList);System.out.println("=========洗牌============");deckCard.washCard(cardList);System.out.println(cardList);System.out.println("=========发牌============");//3个人 每个人5张牌 轮流List<Card> hands1 = new ArrayList<>();List<Card> hands2 = new ArrayList<>();List<Card> hands3 = new ArrayList<>();List<List<Card>> hands = new ArrayList<>();hands.add(hands1);hands.add(hands2);hands.add(hands3);/*   一把揭for (int i = 0; i < 3 ; i++) {for (int j = 0; j < 5; j++) {//揭牌Card card = cardList.remove(0);hands.get(i).add(card);}}*///轮流揭牌for (int i = 0; i < 5 ; i++) {for (int j = 0; j < 3; j++) {//揭牌Card card = cardList.remove(0);hands.get(j).add(card);}}System.out.println("第一个人：");System.out.println(hands1);System.out.println("第二个人：");System.out.println(hands2);System.out.println("第三个人：");System.out.println(hands3);System.out.println("剩余的牌：");System.out.println(cardList);}}

题目五： 杨辉三角
题目链接：https://leetcode.cn/problems/pascals-triangle/
解题思路如下图所示：
解题代码如下所示：

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();if(numRows <= 0) return ret;//第一行的listList<Integer> list = new ArrayList<>();list.add(1);//把第一行的list放到ret当中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++){//确定的是当前行的每个元素 == 上一行的当前列+上一行的前一列就是我当前需要添加的数字List<Integer> preRow = ret.get(i-1);int num = preRow.get(j-1)+preRow.get(j);curRow.add(num);      }//手动在当前行的最后一个位置添加一个1curRow.add(1);ret.add(curRow);}return ret;}
}