数据结构-ArrayList

ArrayList的使用

ArrayList的构造方法

 第二种构造方法,实现了collection接口的都可以传进来.但是需要注意的是E是泛型通配符的上界,只有类型相同是E或者是E的子类的时候,才可以传进来.

当我们调用不带参数的构造方法的时候,只有第一个add的时候,我们才会为其分配大小为10的内存.

扩容是采用1.5倍的扩容方式.如果用户所需大小超过预估的1.5倍大小,则按照用户所需大小进行扩容,并且在真正的扩容之前会检测能否扩容成功,防止太大导致扩容失败.扩容是采用copyOf进行扩容.

ArrayList的常用方法

subList方法需要注意的是:截取的部分并没有创建新的顺序表,而是新的引用(截取的部分)还是指向了原来的顺序表.所以修改截取部分的内容就是将原来顺序表的内容给修改了.

对于remove需要注意的是,编译器会将我们传入的int类型的值统一认定为是下标而不是实际内容的值.

比如有一个ArrayList:[1,7]两个元素.

public static void main(String[] args) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(1);
    arrayList.add(7);
    System.out.println(arrayList);
    //我们要删除值为7的元素
    //arrayList.remove(7);//编译器会把7当成下标,而不是实际的值,所以我们执行起来会报越界错.
    //正确的做法是传入一个引用类型
    arrayList.remove(new Integer(7));
}

ArrayList的遍历

ArrayList的遍历有三种:for循环+下标的方式,foreach,和迭代器.

public static void main(String[] args) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(1);
    arrayList.add(2);
    arrayList.add(3);
    arrayList.add(4);
    //for循环+下标
    for (int i = 0; i < arrayList.size(); i++) {
        System.out.printf(arrayList.get(i)+" ");
    }
    System.out.println();
    //foreach
    for (int x:arrayList) {
        System.out.printf(x+" ");
    }
    System.out.println();
    //使用迭代器
    //必须实现了Iterable接口
    Iterator<Integer> it = arrayList.iterator();
    while (it.hasNext()){
        //it指向上一个数据
        //it.next()会使it访问下一个元素并且向下走一步
        System.out.printf(it.next()+" ");
    }
    System.out.println();
}

实现简单的ArrayList

import java.util.Arrays;

public class MyArrayList {
    public int[] elem;//数组
    public int usedSize;//记录有效的数据的个数
    public static final int DEFAULT_SIZE = 10;

    public MyArrayList(){
        this.elem = new int[DEFAULT_SIZE];
    }

    // 打印顺序表
    public void display() {
        for (int i = 0;i < this.usedSize; i++){
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }
    // 新增元素,默认在数组最后新增
    public void add(int data) {
        //1.检查当前的顺序表是不是满了
        if (isFull()){
            //2.如果满了就要扩容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //3.
        this.elem[usedSize] = data;
        //4.
        usedSize++;
    }

    public boolean isFull(){
        if (this.usedSize > elem.length){
            return true;
        }
        return false;
    }

    // 在 pos 位置新增元素
    //负数下标不可以
    //越过数组的长度不可以
    //不能隔着元素放
    public void add(int pos, int data) throws PosWrongfulException {
        if (isFull()){
            System.out.println("满了!");
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        if (pos < 0 || pos > this.usedSize){
            System.out.println("pos的位置不合法!");
            throw new PosWrongfulException("Pos位置不合法!");
        }

        //pos一定是合法的
        //1.开始挪动数据
        for (int i = this.usedSize-1; i >= pos; i--) {
            this.elem[i+1] = this.elem[i];
        }
        //2.插入数据
        this.elem[pos] = data;
        //3.usedSize++
        usedSize++;
    }
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }
    // 获取 pos 位置的元素
    public int get(int pos) {
        //判空
        if (isEmpty()){
            throw new EmptyException("当前顺序表为空!");
        }
        //判断pos位置的合法性
        if (pos < 0 || pos >= this.usedSize){
            throw new PosWrongfulException("get获取元素的时候,Pos位置不合法!");
        }
        return this.elem[pos];
    }
    //判空
    public boolean isEmpty(){
        return size() == 0;
    }
    // 给 pos 位置的元素更新为 value
    public void set(int pos, int value) {
        //判空
        if (isEmpty()){
            throw new EmptyException("当前顺序表为空!");
        }
        //判断pos位置的合法性
        if (pos < 0 || pos >= this.usedSize){
            throw new PosWrongfulException("pos位置不合法!");
        }
        this.elem[pos] = value;
    }
    //删除第一次出现的关键字key
    public void remove(int key) {
        if (isEmpty()){
            throw new EmptyException("顺序表为空!");
        }
        int index = this.indexOf(key);
        if (index == -1){
            System.out.println("没有这个数字!");
            return;
        }
        // 9 3 4 8 6
        // 0 1 2 3 4
        //usedSize==5,i<4,i最大到3
        //index==4的情况下直接不走循环,usedSize--即可.
        for (int i = index; i <size()-1 ; i++) {
            this.elem[i] = this.elem[i+1];
        }
        usedSize--;
    }
    // 获取顺序表长度
    public int size() { return this.usedSize; }
    // 清空顺序表
    public void clear() {
        this.usedSize = 0;
    }

}

洗牌算法

使用ArrayList实现三个人轮流摸牌的过程.

1.先买一副扑克牌,四种花色,每种花色13张.

2.洗牌

3.揭牌,每人按序摸一张,总共摸五轮.文章来源地址https://www.toymoban.com/news/detail-537614.html

public class Poker {
    //花色
    private String suit;
    //数值
    private int rank;

    public Poker(String suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

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

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

    public String getSuit() {
        return suit;
    }

    public int getRank() {
        return rank;
    }

    @Override
    public String toString() {
        return "["+"suit= " + suit + ", rank=" + rank +"]";
    }
}

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



//1.买一副扑克牌
//2.洗牌
//3.三个人轮流揭牌,每个人揭5次
public class Pokers {
    public static final String[] SUITS = {"♥","♠","♣","♦"};

    /**
     *买一副扑克牌
     */

    public static List<Poker> bugPokers(){
        List<Poker> pokerList = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 13; j++) {
                String suit = SUITS[i];
                int rank = j;
                Poker poker = new Poker(suit,rank);
                pokerList.add(poker);
            }
        }
        return pokerList;
    }
    //洗牌
    public static void shuffle(List<Poker> list){
        Random random = new Random();
        for (int i = list.size()-1; i > 0 ; i--) {
            int index = random.nextInt(i);
            swap(list,i,index);
        }
    }

    private static void swap(List<Poker> list, int i, int index) {
        Poker tmp = list.get(i);
        list.set(i,list.get(index));
        list.set(index,tmp);
    }

    public static void main(String[] args) {
        List<Poker> list = bugPokers();
        System.out.println("买牌:"+list);
        //洗牌
        shuffle(list);
        System.out.println("洗牌:"+list);
        //揭牌 3个人 每个人轮流抓五张牌
        //1.如何描述3个人
        List<Poker> hand1 = new ArrayList<>();
        List<Poker> hand2 = new ArrayList<>();
        List<Poker> hand3 = new ArrayList<>();
        //2.如何区分往哪个人手里送牌
        List<List<Poker>> hand = 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++) {
                List<Poker> handTmp = hand.get(j);
                handTmp.add(list.remove(0));
            }
        }
        for (int i = 0; i < hand.size(); i++) {
            System.out.println("第"+(i+1)+"个人的牌是:"+hand.get(i));
        }
        System.out.println("剩余的牌是: "+ list);
    }
}

删除公共字符串问题

//删除第一个字符串当中出现的第二个字符串中的字符,使用集合
//str1:welcome to bit
//str2:come
//输出wel t bit
//需要注意的是contains方法传的是一个字符串,字符+""就是将字符传为字符串,也可以字符包装类的toString方法将一个字符转为字符串
public static void main(String[] args) {
    String s1 = "welcome to bit";
    String s2 = "come";
    ArrayList<Character> arrayList = new ArrayList<>();
    for (int i = 0; i < s1.length(); i++) {
        if (!s2.contains(s1.charAt(i)+"")){
            arrayList.add(s1.charAt(i));
        }
    }
    for (Character a:arrayList) {
        System.out.printf(a.toString());
    }
}

杨辉三角

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> list1 = new ArrayList<>();
    list1.add(1);
    ret.add(list1);
    for (int i = 1; i <numRows ; i++) {
        //当前行
        List<Integer> curRow = new ArrayList<>();
        curRow.add(1);//一行中开始的1
        //前一行
        List<Integer> prevRow = ret.get(i-1);
        //中间位置需要计算
        for (int j = 1; j < i; j++) {
            int num = prevRow.get(j)+prevRow.get(j-1);
            curRow.add(j,num);
        }
        curRow.add(1);//一行中最后的那个1
        ret.add(curRow);
    }
    return ret;
}