菜鸟之路Day08一一集合进阶(一)

作者：blue

时间：2025.1.26

1.五道经典算法题

为什么要做算法题，个人理解一个是锻炼解决问题的思维，另一个是熟悉如何用这个语言来解决具体的问题，所以练习算法题是非常有必要的，断然不可跳过这个阶段。

1.1自定义排序

定义数组存储一些女朋友对象，利用Arrays中的sort方法

要求1：属性有姓名，年龄，身高

要求2：按照年龄大小进行排序，年龄一样，按照身高排序，身高一样按照姓名的字母进行排序

解题：

①先创造女朋友类，注意在这个Javabean类中，我重写了toString方法，为了一会打印出来方便查看

package Test;

public class Girl {
   
    private String name;
    private int age;
    private double high;

    public Girl() {
   
    }

    public Girl(String name, int age, double high) {
   
        this.name = name;
        this.age = age;
        this.high = high;
    }

    public String getName() {
   
        return name;
    }

    public void setName(String name) {
   
        this.name = name;
    }

    public int getAge() {
   
        return age;
    }

    public void setAge(int age) {
   
        this.age = age;
    }

    public double getHigh() {
   
        return high;
    }

    public void setHigh(double high) {
   
        this.high = high;
    }

    @Override
    public String toString() {
   
        return "Girl{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", high=" + high +
                '}';
    }
}

②创建对象，加入数组，进行自定义排序

package Test;

import java.util.Arrays;
import java.util.Comparator;

public class Test1 {
   
    public static void main(String[] args) {
   
        Girl g1 = new Girl("xm",20,173);
        Girl g2 = new Girl("xw",20,173);
        Girl g3 = new Girl("xn",20,173);

        Girl[] arr = {
   g1,g2,g3};
        System.out.println(Arrays.toString(arr));
        //匿名内部类
        /*Arrays.sort(arr, new Comparator<Girl>() {
            @Override
            public int compare(Girl o1, Girl o2) {
                int temp1;
                double temp2;
                int temp3;
                temp1 = o1.getAge()- o2.getAge();
                temp2 = o1.getHigh() - o2.getHigh();
                temp3 = o1.getName().compareTo(o2.getName());
                if(temp1==0&&temp2==0) return temp3;
                if(temp1==0){
                    if(temp2>0) return 1;
                    else if(temp2<0) return -1;
                }
                return temp1;
            }
        });*/

        //Lambda表达式
        Arrays.sort(arr, (Girl o1, Girl o2)->{
   
            int temp1;
            double temp2;
            int temp3;
            temp1 = o1.getAge()- o2.getAge();
            temp2 = o1.getHigh() - o2.getHigh();
            temp3 = o1.getName().compareTo(o2.getName());
            if(temp1==0&&temp2==0) return temp3;     //针对返回值的解释：
            if(temp1==0){
                              //负数：表示当前插入的元素是小的，放在前面
                if(temp2>0) return 1;                //正数：表示当前插入的元素是大的，放在后面
                else if(temp2<0) return -1;             //0：表示当前插入的元素是一样大的，也放在后面
            } 
            return temp1;
        });
        System.out.println(Arrays.toString(arr));
    }
}

1.2不死神兔

有一个很有名的数学逻辑题叫做不死神兔问题，有一对兔子，从出生后第三个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子不死，问第12个月的兔子对数为多少

解题：没什么特别的，画完图之后发现是fibonacci数列，dp切了

public class Test2 {
   
    public static void main(String[] args) {
   
        int[] dp = new int[13];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=12;i++) dp[i]=dp[i-1]+dp[i-2];
        System.out.println("第12个月的兔子数量为："+dp[12]);
    }
}

1.3猴子吃桃子

有一堆桃子，猴子第一天吃了其中的一半，并多吃了一个！以后每天猴子都吃了当前剩下来的一半，然后再多吃一个，第10天的时候（还没吃），发现只剩下一个桃子了，请问，最初有多少个桃子。

dp切了

public class Test3 {
   
    public static void main(String[] args) {
   
        int[] dp = new int[10];//dp[i],表示第i天剩下dp[i]个桃子
        dp[9]=1;//第十天没吃，剩1个，说明第9天剩1个
        for(int i=8;i>=0;i--) dp[i]=(dp[i+1]+1)*2;
        System.out.println("最初的桃子数为："+dp[0]);
    }
}

1.4爬楼梯

可爱的小明非常喜欢爬楼梯，他一次可以爬1个或2个台阶，如果这个楼梯有20个台阶，请问小明一共有多少种爬法

解题：dp经典题目，搞清楚dp数组的含义便不难理解

public class Test4 {
   
    public static void main(String[] args) {
   
        int[] dp = new int[21];
        dp[1]=1;
        dp[2]=2;//可以从第0阶两步上来，可以从第1阶一步上来
        for(int i=3;i<=20;i++) dp[i]=dp[i-1]+dp[i-2];
        //dp[i]表示爬上第i阶楼梯的方法数为dp[i]
        //dp[i]可以由第i-1阶楼梯爬1级上来，也可以由i-2阶楼梯爬2级上来
        //故而dp[i]=dp[i-1]+dp[i-2]
        System.out.println("登上第20级台阶，有"+dp[20]+"种爬法");
    }
}

1.5爬楼梯plus

现在小明升级了，他一次可以爬1个或2个台阶或3个台阶，那么问如果有20个台阶，有几种爬法

public class Test5 {
   
    public static void main(String[] args) {
   
        int[] dp = new int[21];
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;//(1+1+1),(1+2),(2+1),(3)
        for(int i=4;i<=20;i++) dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        System.out.println("登上第20级台阶，有"+dp[20]+"种爬法");
    }
}

2.单列集合

2.1单列集合体系结构

2.2Collection

2.2.1Collection的常用方法

Collection是所有单列集合的祖宗接口，他的功能所有单列集合都可以继承使用，以下对其6个功能做一个实验

package Collection;

import java.util.ArrayList;
import java.util.Collection;

public class CollectionTest {
   
    public static void main(String[] args) {
   
        //因为Collection是一个接口，所以这里我们只能以多态的方式来创建它的对象
        Collection<String> coll = new ArrayList<>();

        //1.public boolean add(E e)  添加
        coll.add("aaa");//注意其返回值为boolean类型，添加成即为true，失败为false
        coll.add("bbb");//List永远是成功的，而Set由于不能重复，所以有可能会false
        coll.add("ccc");
        System.out.println(coll);

        //2.public void clear() 清空

        //3.public boolean remove(E e) 删除
        coll.remove("aaa");//它是根据对象来删除，因为Set是无索引的，所以这种共性的方法，是不能用索引来删除的
        System.out.println(coll);

        //4.public boolean contain(Object obj)  判断集合是否包含
        //这个方法底层是Object的equals方法实现的，对于引用数据类型他是根据地址值来进行判断的
        //所以如果针对我们自定义类型的集合，想实现用值来查询是否包含，必须在自定义的javabean中重写equals方法
        System.out.println(coll.contains("aaa"));

        //5.public boolean isEmpty() 判断是否为空
        System.out.println(coll.isEmpty());

        //6.public int size() 集合长度
        System.out.println(coll.size());
    }
}

2.2.2Collection系列集合的通用遍历方式

由于Collection系列中的Set系列是无索引的，所以针对Collection系列，我们应该有通用的遍历方式

2.2.2.1迭代器遍历

public class CollectionTest1 {
   
    public static void main(String[] args) {
   
        /*
            迭代器遍历相关的三个方法(注意是三个方法！！！！)
                Iterator<E> iterator(); 获取一个迭代器对象
                boolean hasNext();      判断当前指向的位置是否有元素
                E next();               获取当前指向的元素并移动指针
        */

        Collection<String> coll = new ArrayList<>();
        coll.add("aaa");
        coll.add("bbb");
        coll.add("ccc");
        coll.add("ddd");

        //迭代器遍历
        Iterator<String> it = coll.iterator();
        while(it.hasNext()){
   
            System.out.println(it.next());//获取当前指向的元素并移动指针
        }
        /*注意点：1.迭代器遍历结束，指针不会复位，想再次遍历必须再次获取迭代器对象
                2.循环中只能用1次next方法
                3.迭代器遍历时不能用集合的方法进行增加或删除，这样子会有并发错误
                只能用迭代器自身的remove方法来删除元素
        */ 
    }
}

2.2.2.2增强for遍历

增强for是JDK5以后出现的，底层就是迭代器，注意只有Collection系列的集合才能用增强for

比如刚才的代码，就可以变成

Collection<String> coll = new ArrayList<>();
coll.add("aaa");
coll.add("bbb");
coll.add("ccc");
coll.add("ddd");

//增强for遍历
//s是一个第三方变量，如果你对s做修改，是不会影响集合中的元素的
for (String s : coll) {
   
    System.out.println(s);//获取当前指向的元素并移动指针
}

2.2.2.3Lambda表达式遍历

package Collection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.function.Consumer;

public class CollectionTest2 {
   
    public static void main(String[] args) {
   
        Collection<String> coll = new ArrayList<>();
        coll.add("aaa");
        coll.add("bbb");
        coll.add("ccc");

        /*匿名内部类的方式
        coll.forEach(new Consumer<String>() {
            @Override
            //s依次表示集合中的每一个数据
            public void accept(String s) {
                System.out.println(s);
            }
        });
        */

        //Lambda表达式
        coll.forEach((String s)->{
   
            System.out.println(s);
        });
    }
}

2.3List

List是Collection中的一种，特点是有序，有索引，可重复，Collection中的所有方法List都继承了。

List其实也是一个接口，所以我们依然不能直接创建它的对象，只能创建它实现类的对象。

2.3.1List的特有方法

List是有索引的，所以List中有很多与索引有关的操作，以下实验其针对索引的操作

public class ListTest1 {
   
    public static void main(String[] args) {
   
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");

        //1.void add(int index,E element) 在指定位置插入元素
        list.add(1,"AAA");
        System.out.println(list);//原来位置上的元素，会被依次往后退一个

        System.out.println("==================================");

        //2.E remove(int index) 删除指定位置的元素，并且会返回这个被删除的元素
        String x = list.remove(1);
        System.out.println(x);

        System.out.println("==================================");

        //3.E set(int index,E element) 修改指定索引处的元素，返回被修改的元素
        String y = list.set(1,"xxx");
        System.out.println(list);
        System.out.println(y);

        System.out.println("==================================");

        //4.E get(int index) 返回指定索引处的元素
        String s = list.get(1);
        System.out.println(s);
    }
}

2.3.2List的遍历方式

List比起Collection，多两种与索引有关的遍历方式

普通for

public class ListTest2 {
   
    public static void main(String[] args) {
   
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        for(int i=0;i<list.size();i++){
   
            System.out.println(list.get(i));
        }
    }
}

列表迭代器

public class ListTest2 {
   
    public static void main(String[] args) {
   
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");

        //列表迭代器
        //额外添加了一个方法，在遍历的过程中，可以添加元素
        ListIterator<String> it = list.listIterator();
        while(it.hasNext()){
   
            String str = it.next();
            if("bbb".equals(str)){
   
                it.add("qqq");
            }
        }
        System.out.println(list);
    }
}

2.4LinkedList

LinkedList底层的数据结构是双向链表，查询慢，增删快，但是如果操作的是首尾元素，速度也是极快的，所以它多了很多首位操作特有的API（混个眼熟）

基本都可以见名知意

public void addFirst(E e);
public void addLast(E e);
public E getFirst();
public E getLast();
public E removeFirst();
public E removeLast();