目录
一、顺序表
1.1. 接口的实现
二、ArrayList简介
2.1. ArrayList的构造
2.2. ArrayList的常见操作
2.3. ArrayList的扩容机制
三、ArrayList的具体使用
3.1. 洗牌算法
3.2. 杨辉三角
一、顺序表
上一期我们讲到过,顺序表本质上和数组是差不多的,只不过数组只能访问或修改某个元素,而作为顺序表,需要实现更多的功能。
1.1. 接口的实现
//新增元素,默认在数组最后新增
public void add(int data) { }
// 在pos位置新增元素
public void add(int pos, int data) { }
//判定是否包含某个元素
public boolean contains(int toFind) { return true; }
//查找某个元素对应的位置
public int indexOf(int toFind) { return -1; }
//获取pos位置的元素
public int get(int pos) { return -1; }
// 给pos位置的元素设为
value
public void set(int pos, int value) {
//删除第⼀次出现的关键字key
public void remove(int toRemove) {
// 获取顺序表⻓度
public int size() { return 0; }
//清空顺序表
public void clear() {
}
二、ArrayList简介
2.1. ArrayList的构造
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
//第一种方式,创建ArrayList对象,构造空的顺序表
ArrayList<String> arrayList1 = new ArrayList<>();
//第二种方式
List<String> list = new ArrayList<>();
}
}
其中ArrayList里面,也是实现了List的接口。也就是说,我们完全可以通过向上转型,把List引用指向ArrayList的实例。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
我们来看下面两段代码的,两个都是构造空的顺序表,二者有什么区别呢?第一个是创建了一个盒子,盒子里面为空,而第二个却连盒子都没有。
ArrayList<String> arrayList1 = new ArrayList<>();
ArrayList<String> arrayList2 = null;
//使用arrayList1复制一份,生成arrayList3
ArrayList<String> arrayList3 = new ArrayList<>(arrayList1);
//构造的同时,可以去指定初始容量
ArrayList<String> arrayList4 = new ArrayList<>(10);
当前构造出来的ArrayList初始容量为10,这里与数组的区别是:数组我们在一开始就规定好了它的容量,不能在进行修改了;而ArrayList的容量可以进行动态扩容,只要机器内存允许,就能一直扩容,把想要的元素容纳进去。
2.2. ArrayList的常见操作
(1)add尾插操作
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
System.out.println(list);
}
}
(2)获取元素个数
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
//获取元素个数,数组提供了.length属性获取到元素个数,集合类提供了size()方法获取元素个数
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
System.out.println(list.size());
}
}
事实上,不仅是List,只要是集合类,都可以通过.size来获取长度。
(3)ArrayList的访问和修改
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
//获取或者设置list中的元素
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");//进行了自动扩容
System.out.println(list.get(0));
System.out.println(list.get(1));
System.out.println(list.get(2));
System.out.println(list.get(3));
System.out.println(list.get(4));
}
}
如果我们运行一下,此时也会出现下标越界访问的异常。
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
//获取或者设置list中的元素
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");//进行了自动扩容
list.set(0,"eee");
System.out.println(list);
}
}
(4)ArrayList的遍历
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");
//遍历是可能会进行各种操作的,不一定是打印
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();
//for-each写法
for (String s : list) {
System.out.print(s+" ");
}
}
}
并不是所有的类都能写进for-each里面,要求这个类必须能够实现Iterable接口。实现Iterable接口中的iterator方法,得到一个迭代器对象,进行近一步循环遍历。
public interface List<E> extends Collection<E>
public interface Collection<E> extends Iterable<E>
Iterator<E> iterator();
迭代也是计算机中的专业术语,可以理解成“逐渐接近目标”。集合类中用到迭代。上面的for-each循环,我们可以看作是以下代码的简化。
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
hasNext用于判断有没有下一个元素,iterator.next用于取出当前元素,并准备下一个元素。hasNext的工作机理可以如下图所示,按照箭头从上到下依次去遍历。
(5)其他的一些操作
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
//通过contains判读元素是否存在
List<String> list1 = new ArrayList<>();
list1.add("aaa");
list1.add("bbb");
list1.add("ccc");
list1.add("ccc");
list1.add("ccc");
list1.add("ddd");
System.out.println(list1.contains("aaa"));
//通过indexOf获取元素第一次出现的位置
System.out.println(list1.indexOf("ccc"));
//通过lastIndexOf获取元素最后一次出现的位置
list1.lastIndexOf("ccc");
main1(args);
main2(args);
main3(args);
}
public static void main3(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("aaa");
list1.add("bbb");
list1.add("ccc");
list1.add("ddd");
//按照元素内删除
list1.remove("ddd");
System.out.println(list1);
}
public static void main2(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("aaa");
list1.add("bbb");
list1.add("ccc");
list1.add("ddd");
//按照下标删除元素
list1.remove(2);
System.out.println(list1);
}
public static void main1(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("aaa");
list1.add("bbb");
list1.add("ccc");
list1.add("ddd");
//在任意位置添加元素
list1.add(1,"eee");
System.out.println(list1);
}
}
2.3. ArrayList的扩容机制
当ArrayList内存不够时,就会自动申请额外的内存空间。ArrayList内部持有一个数组,设置的初始容量相当于数组的大小。比如说我们初始容量为10,当循环到第11次的时候,发现元素已经满了;add真正写进元素之前,就要创建一个更大的数组。新的数组要把旧的数组里的元素添加进来,新的元素也要添加进新的数组里面,原来旧的数组要进行释放。
三、ArrayList的具体使用
3.1. 洗牌算法
问题描述:现有一副扑克牌,对其进行洗牌。
我们先来定义一个Card类,用来表示一张扑克牌。
class Card {
public String suit;//表示花色
public String rank;//表示点数
public Card(String suit, String rank) {
this.suit = suit;
this.rank = rank;
}
public String getSuit() {
return suit;
}
public void setSuit(String suit) {
this.suit = suit;
}
public String getRank() {
return rank;
}
public void setRank(String rank) {
this.rank = rank;
}
@Override
public String toString() {
return this.suit+this.rank;
}
}
接下来要先把Card这个对象实例化,并用ArrayList把所有的牌添加进去。
public class Main {
public static void main(String[] args) {
//使用ArrayList表示一副扑克牌
}
public static ArrayList<Card> CreateDeck() {
//创建一副扑克牌
ArrayList<Card> deck = new ArrayList<>();
String[] suits = {"♠","♦","♥","♣"};
//通过两层for循环,第一层先循环花色,第二层在循环点数
//每个花色中,生成对应的点数
for (String suit:suits){
for (int i = 2; i <= 10; i++) {
Card cardNum = new Card(suit,""+i);
deck.add(cardNum);//添加到扑克牌中
}
Card cardJ = new Card(suit,"J");
Card cardQ = new Card(suit,"Q");
Card cardK = new Card(suit,"K");
Card cardA = new Card(suit,"A");
deck.add(cardJ);
deck.add(cardQ);
deck.add(cardK);
deck.add(cardA);
}
return deck;
}
}
然后我们调用CreateDeck方法,对这副牌进行一个打印。
public class Main {
public static void main(String[] args) {
//使用ArrayList表示一副扑克牌
ArrayList<Card> deck = CreateDeck();
System.out.println(deck);
}
}
接下来是进行洗牌的操作,在Java标准库中,提供了进行洗牌的方法shuffle。
import java.util.Collections;
public class Main {
public static void main(String[] args) {
//使用ArrayList表示一副扑克牌
ArrayList<Card> deck = CreateDeck();
System.out.println("原始牌组:"+deck);
//洗牌
Collections.shuffle(deck);
System.out.println("洗牌之后:"+deck);
}
}
我们也可以自己写一个方法,来进行洗牌。
public static void shuffle(ArrayList<Card> deck){
//把整个ArrayList从后往前遍历
//每次取一张牌,生成一个随机下标,用当前的拍和随机下标的牌进行交换
Random random = new Random();
for (int i = deck.size(); i >0 ; i--) {
int j = random.nextInt(deck.size());//生成随机下标[0,deck.size)
//交换操作
Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标,不能交换的时候发生修改
deck.set(i, deck.get(j));
deck.set(j, tmp);
}
}
下面是发牌,一共有3个人,每个人发5张牌。我们可以看成一个3行5列的一个二维数组。
ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组
//先创建 3 个人手里的牌
for (int i = 0; i < 3; i++) {
ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌
hands.add(hand);//发到每个人手里
//已经添加了3个元素进去,但还是长度为0的ArrayList
}
最后是发牌的过程。
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
//发牌是轮流的过程.
ArrayList<Card> currentHand = hands.get(j);
Card card = deck.remove(0);
currentHand.add(card);
//一次循环,相当于取出一张牌交给玩家
}
}
完整代码:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
class Card {
public String suit;//表示花色
public String rank;//表示点数
public Card(String suit, String rank) {
this.suit = suit;
this.rank = rank;
}
public String getSuit() {
return suit;
}
public void setSuit(String suit) {
this.suit = suit;
}
public String getRank() {
return rank;
}
public void setRank(String rank) {
this.rank = rank;
}
@Override
public String toString() {
return this.suit+this.rank;
}
}
public class Main {
public static void main(String[] args) {
//使用ArrayList表示一副扑克牌
ArrayList<Card> deck = CreateDeck();
System.out.println("原始牌组:"+deck);
//洗牌
//Collections.shuffle(deck);
System.out.println("洗牌之后:"+deck);
ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组
//先创建 3 个人手里的牌
for (int i = 0; i < 3; i++) {
ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌
hands.add(hand);//发到每个人手里
//已经添加了3个元素进去,但还是长度为0的ArrayList
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
//发牌是轮流的过程.
ArrayList<Card> currentHand = hands.get(j);
Card card = deck.remove(0);
currentHand.add(card);
//一次循环,相当于取出一张牌交给玩家
}
}
//打印每个人的手牌
for (int i = 0; i < 3; i++) {
System.out.println("第"+i+"个人的手牌"+hands.get(i));
}
}
public static void shuffle(ArrayList<Card> deck){
//把整个ArrayList从后往前遍历
//每次取一张牌,生成一个随机下标,用当前的拍和随机下标的牌进行交换
Random random = new Random();
for (int i = deck.size(); i >0 ; i--) {
int j = random.nextInt(deck.size());//生成随机下标[0,deck.size)
//交换操作
Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标,不能交换的时候发生修改
deck.set(i, deck.get(j));
deck.set(j, tmp);
}
}
public static ArrayList<Card> CreateDeck() {
//创建一副扑克牌
ArrayList<Card> deck = new ArrayList<>();
String[] suits = {"♠","♦","♥","♣"};
//通过两层for循环,第一层先循环花色,第二层在循环点数
//每个花色中,生成对应的点数
for (String suit:suits){
for (int i = 2; i <= 10; i++) {
Card cardNum = new Card(suit,""+i);
deck.add(cardNum);//添加到扑克牌中
}
Card cardJ = new Card(suit,"J");
Card cardQ = new Card(suit,"Q");
Card cardK = new Card(suit,"K");
Card cardA = new Card(suit,"A");
deck.add(cardJ);
deck.add(cardQ);
deck.add(cardK);
deck.add(cardA);
}
return deck;
}
}
3.2. 杨辉三角
问题描述:给定一个非负整数 numRows
,生成「杨辉三角」的前 numRows
行。在「杨辉三角」中,每个数是它左上方和右上方的数的和。
示例 1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2: 输入: numRows = 1 输出: [[1]]
通过上面的图,我们可以总结出以下规律:1.第i行有i+1个列(因为要用二维数组解决,所以把第一行定义第0行);2.每一行的第一列和最后一列都是1;3.第i行第j列的元素 = 第i-1行第j-1列的元素 + 第i-1行第j列的元素。
完整代码:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public List<List<Integer>> generate(int numRows) {
//先写一个表示结果的二维数组
List<List<Integer>> result = new ArrayList<List<Integer>>();
//先来构造行
for (int i = 0; i < numRows; i++) {
List<Integer> rows = new ArrayList<>();//用到了向上转型。需要往这一行里面里面添加元素
for (int j = 0; j < i+1; j++) {
if (j==0 || j==i){
rows.add(1);
} else {
List<Integer> prevRow = result.get(i - 1);
int current = prevRow.get(j - 1) + prevRow.get(j);
rows.add(current);
}
}
//一行构造好了之后,把这一行添加到result中
result.add(rows);
}
return result;
}
public static void main(String[] args) {
Main m = new Main();
Scanner num = new Scanner(System.in);
int b = num.nextInt();
List<List<Integer>> result = m.generate(b);
System.out.println(result);
}
}