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

菜鸟之路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;}@Overridepublic 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>() {@Overridepublic 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，失败为falsecoll.add("bbb");//List永远是成功的，而Set由于不能重复，所以有可能会falsecoll.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();