当前位置：首页 > news >正文

【数据结构】ArrayList的具体使用（杨辉三角、扑克牌游戏）

news 来源：原创 2024/4/20 14:52:35

1、了解集合的框架

2、了解ArrayList类

2.1、认识ArrayList类当中的属性

2.1、认识ArrayList类库当中的方法

2.1.1、了解构造方法

2.2、ArrayList类当中的Add（新增元素）方法

2.3、了解ensureCapacityInternal（判断是否需要扩容）方法

2.4、认识grow（扩容）方法

2.5、在数组的某个位置新增元素

2.6、删除数组当中的元素

2.7、 get方法

2.8、clear方法（置空）

2.9、截取数组部分内容（subList）

2.9、ArrayList的遍历输出

3、来看一道面试题

4、杨辉三角

5、扑克牌游戏

1、扑克（Poker）类

2、游戏（Game）类

3、测试类

1、了解集合的框架

Java 集合框架 Java Collection Framework ，又被称为容器 container ，是定义在 java.util 包下的一组接口 interfaces 和其实现类 classes 。

2、了解ArrayList类

ArrayList是一个泛型类，同时他继承了AbstractList这个抽象类，同时他也实现了List，RandomAccess，Cloneable，java.io.Serializable接口。

2.1、认识ArrayList类当中的属性

ArrayList类当中定义了常量、不可修改的静态的数组。

2.1、认识ArrayList类库当中的方法

2.1.1、了解构造方法

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

1、ArrayList()无参构造方法

通过构造方法，将数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给数组elememtData ，当再实例化ArrayList时，调用无参构造方法，此时并没有为数组elemntData分配内存

2、ArrayList(int initialCapacity)有参构造方法

3、 ArrayList(Coiiection<? extends E> c)构造方法

可以这样测试这个方法

import java.util.ArrayList;
import java.util.LinkedList;
public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(12);
        list.add(35);
        list.add(55);
//当然这里指定的参数也可以修改为Number,Integer类是Number的子类，list指定的参数是Integer。
//ArrayList类在实例化的时候调用的第三种构造方法，list当作参数传给构造方法
        ArrayList<Integer> arrayList1 = new ArrayList<>(list);//将另一个集合拿过来作为这个集合的参数。
        //这样就可以将list数组当中的元素放到arrayList1当中去。
        arrayList1.add(1);
        System.out.println(arrayList1);
    }
}

2.2、ArrayList类当中的Add（新增元素）方法

第一步调用的方法ensureCapacityInternal，作用是，用来检查数组是否已满，
第二步，用来将添加的数据放在数组的最后，size再++，记录数组当中的个数。

再add方法中调用了 ensureCapacityInternal方法，所以这里来了解一下ensureCapacityInternal方法。

2.3、了解ensureCapacityInternal（判断是否需要扩容）方法

假设我们再定义add的时候，给了add方法的参数Integer类型的数据1.

在add方法中调用了ensureCapacityInternal方法，传给这个方法的值为size+1，实际值为1.

但是在 ensureCapacityInternal方法中，有调用了ensureExplicitCapacity方法，ensureExplicitCapacity方法中又调用了calculateCapacity方法，calculateCapacity方法的返回值作为ensureExplicitCapacity方法的参数。

来看calculateCapacity（比较方法）方法

if当中判断elememtData数组是否和数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA相等，在构造方法中数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA给elememtData数组赋值，所以这两数组的引用表示的是同一个数组。

因为DEFAULT_CAPACITY在定义ArrayList类的时候，指定了值，所以Math.max(DEFAULT_CAPACITY, minCapacity)；中比较的是10和1的最大值。

所以返回10。

10作为ensureExplicitCapacity方法的参数

数组需要的最小容量是10，现在数组大小为0，所以进入if 条件内部，调用grow方法进行扩容。

2.4、认识grow（扩容）方法

 newCapacity = oldCapacity + (oldCapacity >> 1);
这句代码表示的意思是：newCapacity 等于oldCapacity+oldCapacity/2，扩大到原来的二倍。

>>1表示：向右移动一位，二进制中向右移动一位，相当于除以2.

接下来判断，newCapacity - minCapacity是否大于0，因为minCapacity是10，而oldCapacity是0，导致newCapacity是0，所以他们的值小于0。
进入第一个if,将minCapacity赋值给newCapacity等于10.
接下来，进行第二次判断，判断newCapacity是否大于MAX_ARRAY_SIZE的最大数组大小，数组的容量要重新计算。

最后elementData数组分配的大小为10.

❗❗❗总结：

在第一次调用add方法新增元素的时候，才会为ArrayList类当中的elementData数组分配内存，且大小为10.
当后面新增元素，数组再满了的时候，他会以原数组大小的1.5倍扩容。

2.5、在数组的某个位置新增元素

他的思想和我们在上一个博客当中写的思路是一样。

2.6、删除数组当中的元素

他的思想和我们自己写的方法一致

remove方法，在这里稍微有一些特殊，我们想要删除数组中2元素，在我们自己写的remove方法中，要删某个元素，直接输入元素，在数组中找到就可以删除。

但是在源方法中，remove方法是重写的，他又两种删除方式

第一种：通过找下标删除元素，调用这个方法时，传入的参数代表的是下标
第二种：通过数组元素，找到对应的下标，删除该元素，调用这个方法时，传入的参数代表的是元素。

❗❗❗在这里我们要说一个知识点，在实例化类的时候，指定的类型Integer，Character等都是类类型。在第一次新增元素的时候，将1放入到ArrayList数组当中的时候，发生了装箱操作。

public class Test {
    public static void main(String[] args) {
    ArrayList<Integer> arrayList1 = new ArrayList<>();
//第一次新增元素的时候，由于Integer是类类型，将1放入到数组当中的时候发生了，装箱的操作
        arrayList1.add(1);
        arrayList1.add(1,10);
        System.out.println(arrayList1);
    }
}

当要删1的时候，就要这样来写

public class Test {
    public static void main(String[] args) {
    ArrayList<Integer> arrayList1 = new ArrayList<>();
//第一次新增元素的时候，由于Integer是类类型，将1放入到数组当中的时候发生了，装箱的操作
        arrayList1.add(1);
        arrayList1.add(1,10);
        arrayList1.remove(new Integer(1));//实例化一个Integer类，找到这个类型的对象
        System.out.println(arrayList1);
    }
}

2.7、 get方法

2.8、clear方法（置空）

2.9、截取数组部分内容（subList）

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList1 = new ArrayList<>( );
        arrayList1.add(11);
        arrayList1.add(12);
        arrayList1.add(13);
        arrayList1.add(14);
        arrayList1.add(15);
        arrayList1.add(16);
        List<Integer> sub = arrayList1.subList(1,3);//截取1下标到3下标的元素
        System.out.println(sub);
        sub.set(0,888);//修改截取数组的0下标元素为888.
        System.out.println(sub);
        System.out.println(arrayList1);
    }
}

❗❗❗总结：

subList方法截取数组的某一部分，实际上是将elementData数组的1下标给了sub引用，实际上，sub引用和arrayList1引用指向同一个数组，所以通过sub修改0下标的值，也就修改了elementData数组的1下标元素。

2.9、ArrayList的遍历输出

在上述的代码中，我们通过System.out.println();直接输出引用sub和arrayList1所指向的对象，

理论上引用sub应该存储arrayList1.subList()的地址，怎么通过System.out.println(sub)输出的呢？

说明ArrayList类一定是重写了toString方法。
但是通过查找ArrayList类当中没有找到toString方法。
由于ArrayList类是继承了父类的，ArrayList继承了父类的方法，我们可以看他的父类当中有没有toString方法。
最终在他父类的父类AbstractCollection当中找到了toString方法。

📕这是第一种遍历方式，可以通过 System.out.println()；直接输出。

📕第二种方式：可以通过for循环输出。

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList1 = new ArrayList<>( );
        arrayList1.add(11);
        arrayList1.add(12);
        arrayList1.add(13);
        arrayList1.add(14);
        arrayList1.add(15);
        arrayList1.add(16);
        System.out.println("============");
        for (int i = 0; i < arrayList1.size(); i++) {
            System.out.print(arrayList1.get(i)+" ");//加空格，尚在输出的时候数字之间可以隔开
        }
        System.out.println();

       

        for(Integer x:arrayList1){
            System.out.print(x+" ");
        }
        System.out.println();

📕第三种方式：迭代器

        ListIterator<Integer> it = arrayList1.listIterator();
        while(it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();

❗❗❗总结:

常用的遍历输出，是第一种和第二种输出方式，迭代器用的很少，迭代器会用就行。

3、来看一道面试题

给出两个字符串

s1:"welcome to world"

s2:"come"

要求删除s1当中的字符，这些字符都是s2中出现的。

删完之后s1：只剩wl t bit.

public class Test {
    public static void main(String[] args) {
        ArrayList<Character> list = new ArrayList<>();
        String s1 = "welcome to bit";
        String s2 = "come";
        for (int i = 0; i < s1.length(); i++) {
            char ch = s1.charAt(i);//多次循环，将s1当中的每个字符存入ch中
            if(!s2.contains(ch+"")){//判断s2中不包含ch当中的这个字符
                list.add(ch);//将s2中不包含的字符，放入ArrayList类当中elementData数组中
            }
        }
        //这里是为了让输出的结果更加美观
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i));
        }
    }

❓❓❓上述代码中，出现了一个小问题若这样写，编译器会报错。

而String类，是实现了这个接口的

所以我们在传参数的时候，最起码要传一个字符串类型的数据，不能传字符类型的数据。

📕第一种解决方式

if(!s2.contains(ch+"")){//给字符拼接一个"",让ch当中的字符呈现的形式为"w"(字符串的形式)。

📗第二种解决方式

可以直接使用valueOf方法来解决。这样也就满足了contains方法的参数类型实现了CharSequence接口
if(!s2.contains(valueOf(ch))){//valueOf方法的返回值是String类型的，满足了contains方法的 要求

4、杨辉三角

给定一个非负整数numRows，生成【杨辉三角】的前numRows行。在【杨辉三角】中，每个数据是他左上方和右上方的数的和。

示例：
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]

这里了解一个知识点：

   List<List<Integer>>generate(int numRows){

他表示的意思是：集合类型表示的二维数组

❗❗❗代码的大致思路：

就是将row数组中的元素，通过[i][j] = [i-1][j]+[i-1][j-1]补齐，并将row数组放入到ret数组中。

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

public class Test {
   List<List<Integer>>generate(int numRows){
       List<List<Integer>> ret = new ArrayList<>();//这里实例化，相当于这个数组是ArrayList类型的，数组中的元素是List类型的，而数组元素指向的数组元素是Integer类型的
       //创建第一行数组
       List<Integer> row = new ArrayList<>();
       row.add(1);
       ret.add(row);//这里是让ret引用当中的数组，与row引用当中的数组产生联系
       for (int i = 0; i < numRows; i++) {//举例：调用这个方法者，想要3行，到2下标
           List<Integer> prevRow = ret.get(i-1);//获取前一行
           List<Integer> curRow = new ArrayList<>();
           curRow.add(1);//第一个1
           //中间curRow  list的赋值
           for (int j = 1; j < i; j++) {//j<i表示的意思是，当ret数组中第二个元素的时候，第二行row数组有俩个元素，ret数组当中第三个元素，第三行row数组有三个元素。
               int x = prevRow.get(j)+prevRow.get(j-1);
                curRow.add(x);
           }
           curRow.add(1);//最后一个1
           ret.add(curRow);//将最后一行的数组放到ret所引用的数组当中。
       }
        return ret;
   }

}

5、扑克牌游戏

功能描述：

抽象出扑克牌类。包括四种花色（黑桃、红心、梅花、方块），每种都有十三张牌（1-13，J,Q,K用11，12，13代替），不考虑大小王。
创建一个游戏类，包含洗牌方法，生成扑克牌的方法，揭牌的方法
要求：每人揭五张牌，没人一次只揭一张牌

代码实现：

1、扑克（Poker）类

package demo;

public class Poker {
    private String suit;//颜色
    private int rank;//数字

    public Poker(String suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }
//由于这个类当中的属性是用private分装起来的，所以给两个属性提供get和set方法。
    public String getSuit() {
        return suit;
    }

    public void setSuit(String suit) {
        this.suit = suit;
    }

    public int getRank() {
        return rank;
    }

    public void setRank(int rank) {
        this.rank = rank;
    }

    @Override
    public String toString() {
        return "{"+suit+" "+rank+"}";
    }
}

2、游戏（Game）类

package demo;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Game {
    private static final String[] suits = {"♥","♠","♣","♦"};
    public List<Poker> buyPoker(){//生成52张扑克牌
        List<Poker> pokers = new ArrayList<>();//生成的牌要放在数组当中
        for (int i = 0; i < 4; i++) {//表示4中花色
            for (int j = 1; j <= 13; j++) {//每种花色都有13张牌，每种花色都从1开始。
                String suit = suits[i];//每次循环的花色
                int rank = j;//循环生成的牌的点数
                Poker poker = new Poker(suit,rank);//生成一张牌
                //牌这个对象放在pokers这个对象的数组中。
                pokers.add(poker);
            }
        }
        return pokers;
    }
    //洗牌
    public void shuffle(List<Poker> pokers){//这个方法只是将牌打乱。
        for (int i = pokers.size()-1; i > 0 ; i--) {
            Random random = new Random();//利用random生成随机数
            int index = random.nextInt(i);
            swap(pokers,i,index);
        }
    }
    private void swap(List<Poker> pokers,int i,int j){//数组元素交换方法
        Poker tmp = pokers.get(i);
        pokers.set(i,pokers.get(j));
        pokers.set(j,tmp);
    }
    //揭牌
    public List<List<Poker>> game(List<Poker> pokers){
        List<List<Poker>> hand = new ArrayList<>();//这里利用二维数组，让下边的三个手产生联系。
        List<Poker> hand1 = new ArrayList<>();
        List<Poker> hand2 = new ArrayList<>();
        List<Poker> hand3 = new ArrayList<>();
        hand.add(hand1);
        hand.add(hand2);
        hand.add(hand3);
        for (int i = 0; i < 5; i++) {//最外层控制揭牌的轮数
            for (int j = 0; j < 3; j++) {//控制揭牌的人数
                Poker removePoker = pokers.remove(0);//揭完之后，每次删除0下标位置元素。
                hand.get(j).add(removePoker);//每个人揭的牌，就是数组中删除的元素。
            }
        }
        return hand;
    }
}

揭牌的方法中示例化三个ArrayList类，分别用List类型的hand1、2、3接收，这样写的好处是：拿接口来接收，可以做到接受不同的对象，只要实现了这个接口的都可以。
并且示例化一个ArrayList类，用 List<List<Poker>>类型的对象接收，实现一个二维数组。
通过hand.add(hand1);这样的操作，让对象hand和hand1、2、3产生联系。

3、测试类

ackage demo;

import java.util.List;

public class Test {
    public static void main(String[] args) {
        Game game = new Game();
        List<Poker> pokers = game.buyPoker();
        System.out.println(pokers);
        //洗牌
        game.shuffle(pokers);
        System.out.println("洗牌");
        System.out.println(pokers);
        //揭牌
        List<List<Poker>> hand = game.game(pokers);
        System.out.println("揭牌");
        for (int i = 0; i < hand.size(); i++) {
            System.out.println("第 "+(i+1)+"个人的牌："+hand.get(i));
        }
        System.out.println("剩下的牌：");
        System.out.println(pokers);
    }
}