介绍了双向搜索与meet-in-the-middle，是对BFS与DFS的进一步优化
【CS61B】Project1A-Linked List Deque 61B
Project1A-Linked List Deque 61B
这个项目要求我们用链表实现双端队列(Deque)
Javadoc comment
1
2
3
4
5
/** ...
* @param index index to get
* @return element at {@code index} in the deque
*/
T get(int index);如以上注释，该形式的注释为java文档注释
- @param表示方法的变量
- @return表示方法的返回值类型
- @code 用于格式化文本为代码风格
步骤
创建文件
我们希望创建的类可以接受多种数据类型，故需要实现泛型，在声明类时：
public class LinkedListDeque61B<T>
另外需要指定LinkedListDeque61B是Deque61B的子类，并且实现所有接口中的方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.List;
public class LinkedListDeque61B<T> implements Deque61B<T>{
@Override
public void addFirst(T x) {
}
@Override
public void addLast(T x) {
}
@Override
public List<T> toList() {
return List.of();
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public int size() {
return 0;
}
@Override
public T removeFirst() {
return null;
}
@Override
public T removeLast() {
return null;
}
@Override
public T get(int index) {
return null;
}
@Override
public T getRecursive(int index) {
return null;
}
}最后加入构造函数：
1
2
3
public LinkedListDeque61B(){
}JUnit Tests
打开LinkedListDeque61BTest文件，去除除最后一行的注释，就可以对编写代码进行本地测试
Writing and Verifying the Constructor
实现构造函数，更具体的，构造函数应传入0个参数，并在LinkedListDeque61B类中实现嵌套类Node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private class Node{
public T item;
public Node next;
public Node previous;
public Node(T i, Node p, Node n){
item = i;
next = n;
previous = p;
}
}
private Node sentinelFront;
private Node sentinelLast;
private int size;
public LinkedListDeque61B(){
sentinelFront = new Node(null, null, null);
sentinelLast = new Node(null, null, null);
size = 0;
}这里我们在类中嵌套实现了Node类用于定义每个节点，并且对双端队列设置了两个sentinel节点，方便双端操作，同时引入size记录大小
其中，Node类包括两个指针，同时指向前一个节点与后一个节点
构造函数中，对两个sentinel节点进行初始化，并设置size为0
Writing and
Verifying addFirst and addLast
addFirst与addLast需要以常数时间实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public void addFirst(T x) {
Node newNode = new Node(x, sentinelFront, sentinelFront.next);
sentinelFront.next.previous = newNode;
sentinelFront.next = newNode;
size++;
}
@Override
public void addLast(T x) {
Node newNode = new Node(x, sentinelLast.previous, sentinelLast);
sentinelLast.previous.next = newNode;
sentinelLast.previous = newNode;
size++;
}我们直接操作sentinel节点的next与previous来添加节点
Writing and Verifying
toList
实现toList，当调用时会自动返回以列表形式表示的Deque61B
例如，如果Deque61B已经调用了addLast(5)、addLast(9)、addLast(10)，然后对其调用addFirst(3)，那么toList()的结果应该是一个以3开头，然后是5、9、10的列表。如果在Java中打印，它将显示为[3, 5, 9, 10]。
toList方法的第一行应该类似于List<T> returnList = new ArrayList<>()，标志着可以使用该结构的位置
1
2
3
4
5
6
7
8
@Override
public List<T> toList() {
List<T> returnList = new ArrayList<>();
for (Node p = sentinelFront.next; p!=sentinelLast; p = p.next){
returnList.add(p.item);
}
return returnList;
}Writing Tests
写测试例的模板：Arrange-Act-Assert
- Arrange：组织测试样例，如初始化数据结构或往里面填充元素
- Act：执行想要执行的操作
- Assert：评估Act中的结果
在单个测试方法中通常有多个act与assert步骤
真值评估的模板：
格式：assertThat(actual).isEqualTo(expected);
添加信息：
1
2
3
assertWithMessage("actual is not expected")
.that(actual)
.isEqualTo(expected);判断列表包含内容：
1
2
3
assertThat(actualList)
.containsExactly(0, 1, 2, 3)
.inOrder();对于引用类型：
1
2
3
assertThat(actualList)
.containsExactlyElementsIn(expected) // `expected` is a List
.inOrder();注意：assert一个布尔值时，记得在后面使用.isTrue() 或者
.isFalse()判断正误
其余方法
isEmpty()与size()
要求常数时间实现
1
2
3
4
5
6
7
8
9
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public int size() {
return size;
}get()与getRecursive()
给予下标寻找下标对应元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@Override
public T get(int index) {
if (index<0||index>=size){
return null;
}
Node p = sentinelFront.next;
for (int i = 0; i<index; i++){
p = p.next;
}
return p.item;
}
private T getRecursiveHelper(Node p, int index){
if (index == 0) return p.item;
return getRecursiveHelper(p.next, index-1);
}
@Override
public T getRecursive(int index) {
if (index<0||index>=size){
return null;
}
return getRecursiveHelper(sentinelFront.next, index);
}写了一个辅助递归函数，可以接受当前节点与下标，进行节点的推进
removeFirst()与removeLast()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@Override
public T removeFirst() {
if (isEmpty()){
return null;
}
Node temp = sentinelFront.next;
sentinelFront.next = temp.next;
temp.next.previous = sentinelFront;
size--;
return temp.item;
}
@Override
public T removeLast() {
if (isEmpty()){
return null;
}
Node temp = sentinelLast.previous;
sentinelLast.previous = temp.previous;
temp.previous.next = sentinelLast;
size--;
return temp.item;
}【CS61B】Project1B-ArrayDeque 61B
Project1B - ArrayDeque 61B
这个项目中，我们需要用数组实现循环双端队列
初始化
创建类文件，并修改类声明以让该类是Deque61B接口的一个实现，且支持泛型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package deque;
import java.util.List;
public class ArrayDeque61B<T> implements Deque61B<T> {
@Override
public void addFirst(T x) {
}
@Override
public void addLast(T x) {
}
@Override
public List<T> toList() {
return List.of();
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public int size() {
return 0;
}
@Override
public T removeFirst() {
return null;
}
@Override
public T removeLast() {
return null;
}
@Override
public T get(int index) {
return null;
}
@Override
public T getRecursive(int index) {
return null;
}
}构造函数
使用到的成员有
- size：确定数组目前容量
- capacity：确定数组最大容量
- items：使用java内置数组存储数据
- nextFirst：指向队首（第一个空位置）
- nextLast：指向队尾（最后一个空位置）
1
2
3
4
5
6
7
public ArrayDeque61B(){
size = 0;
capacity = 8;
items = (T[])new Object[capacity];
nextFirst = 0;
nextLast = 0;
}addFirst() & addLast()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Override
public void addFirst(T x) {
if (size==capacity){
resize(size*2);
}
items[nextFirst] = x;
size++;
nextFirst = floorMod(nextFirst-1, capacity);
}
@Override
public void addLast(T x) {
if (size==capacity){
resize(size*2);
}
items[nextLast] = x;
size++;
nextLast = floorMod(nextLast+1, capacity);
}这里在添加时要考虑循环，若到队头了要转到队尾加
另外，当队列满了需要手动扩容，一般可以扩到原来都两倍，防止过多调用
get()
按下标获得元素，若无效返回null
1
2
3
4
5
6
7
8
@Override
public T get(int index) {
if (index<0||index>=size){
return null;
}
int realIndex = floorMod(index+nextFirst+1, capacity);
return items[realIndex];
}这里注意，get获得的是相对下标，我们需要转换成真实下标（即元素不一定是从0开始的，需要添加nextFirst偏移量）
getRecursive()没有什么必要，可以直接抛出一个异常
1
2
3
4
@Override
public T getRecursive(int index) {
throw new UnsupportedOperationException("No need to implement getRecursive for proj 1b");
}toList()
1
2
3
4
5
6
7
8
9
@Override
public List<T> toList() {
List<T> show = new ArrayList<>(size);
int cnt = 0;
for (int i = 0; i<size;i++){
show.add(get(i));
}
return show;
}结合get方法会更加方便
removeFirst() & removeLast()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Override
public T removeFirst() {
if (isEmpty()){
return null;
}
nextFirst = floorMod(nextFirst+1,capacity);
size--;
return items[nextFirst];
}
@Override
public T removeLast() {
if (isEmpty()){
return null;
}
nextLast = floorMod(nextLast-1,capacity);
size--;
return items[nextLast];
}不要忘记判空以及减小size
resize()
作为数组大小不够时的方案，一次扩容两倍使用
1
2
3
4
5
6
7
8
9
10
11
12
13
private void resize(int newCapacity){
T[] a = (T[]) new Object[newCapacity];
int cur = floorMod(nextFirst+1,capacity);
for(int i = 0; i<size;i++){
a[i] = items[cur];
cur = floorMod(cur+1, capacity);
}
items = a;
capacity = newCapacity;
nextFirst = newCapacity -1;
nextLast = size;
}这里要将原数组复制到一个新容量的数组中使用
采用的方法是将原数组元素按从0开始的下标复制到新数组，再用新数组覆盖
同时调整nextFirst与nextLast
iterator()
实现迭代器，让我们的双端队列可以迭代
即在内部嵌套一个Iterator类的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Override
public Iterator<T> iterator() {
return new ArrayDequeIterator();
}
public class ArrayDequeIterator implements Iterator<T>{
private int pos;
ArrayDequeIterator(){
pos = 0;
}
@Override
public boolean hasNext() {
return pos < size;
}
@Override
public T next() {
T returnItems = get(pos);
pos++;
return returnItems;
}
}注意：接口不允许提供覆盖Object方法的默认方法，故无法在接口中提供默认方法
equals()
重写equals方法，让该方法仅比较元素相等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public boolean equals(Object o){
if (o instanceof ArrayDeque61B<?> uAD){
if (this.size!=uAD.size){
return false;
}
for (int i = 0; i<size;i++){
if (!Objects.equals(this.get(i), uAD.get(i))){
return false;
}
}
return true;
}
return false;
}若想在instanceof中使用泛型，需要使用<?>通配符
toString()
返回自定义的string输出表示双端队列
1
2
3
4
5
6
7
8
9
10
11
@Override
public String toString(){
StringBuilder stringToReturn = new StringBuilder("[");
for (T x: this){
stringToReturn.append(x);
stringToReturn.append(", ");
}
stringToReturn.delete(stringToReturn.length()-2,stringToReturn.length());
stringToReturn.append("]");
return stringToReturn.toString();
}【CS61B】Project0-2048
Project0 - 2048
Hard Mode
项目结构
1
2
3
4
5
6
7
8
9
10
proj0_hardmode
├── game2048logic
| ├── GameLogic.java
| ├── MatrixUtils.java
├── game2048rendering
├── Board.java
... (some other files) ...
├── Main.java
├── Side.java
├── Tile.java分为了两个包：负责逻辑与负责渲染的，主要更改在负责逻辑的包中
Task1：游戏原理
2048的核心规则为Tilting，项目需要主要实现该功能
当两个方格发生融合时，遵循以下规则
两相同值的方格融合为一个，数值翻倍
由合并产生的新方块在该次移动中不会再次合并。例如，当[X, 2, 2, 4]（X 代表空格）向左移动时，结果应为[4, 4, X, X]而非[8, X, X, X]。这是因为最左侧的 4 已参与过合并，故不应二次合并
当融合方向上有三个相邻同值方块时，仅该方向最前方的两个方块会合并，第三个方块保不变。例如[X, 2, 2, 2]左移后应为[4, 2, X, X]，而非[2, 4, X, X]。
推论：若有四个相邻同值方块，则会合并出两个同值方块，如[2, 2, 2, 2]左移后应该为[4, 4, X, X]，但合并出的两个同值方块不会合并
Task2：实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static void compress(int[][] board, int c){
int n = board.length;
int[] comp = new int[n];
int index = 0;
for (int[] ints : board) {
if (ints[c] != 0) {
comp[index++] = ints[c];
}
}
for (int i = 0; i<n; i++){
board[i][c] = comp[i];
}
}
public static void merge(int[][] board, int c){
int n = board.length;
for (int i = 0; i<n-1; i++){
if(board[i][c]!=0 && board[i][c]==board[i+1][c]){
board[i][c] *= 2;
board[i+1][c] = 0;
i++;
}
}
}
public static void moveColumn(int[][] board, int c){
compress(board, c);
merge(board, c);
compress(board, c);
}
public static void moveUp(int[][] board){
for (int i = 0; i<board.length; i++){
moveColumn(board, i);
}
}compress函数用于压缩，即将所有数都移动到顶上，而不进行合并
merge函数用于将相邻的数进行合并
每次移动一列，然后循环处理每列，处理一列时移动后合并，合并后可能会出现中间合并剩下的空位置，需要再进行压缩
【CS61B】Lec16-Extends, Sets, Maps, and BSTs
Lec16 - Extends, Sets, Maps, and BSTs
Extends
从前，若一个类是接口的下位词，我们使用implements来书写方法的实现
但若想实现一个类是另一个类的下位词，我们需要使用extends
extends可以用于类与类、接口与接口之间
例：实现RotatingSLList
即让最后一个元素右旋到第一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package Lec16;
public class RotatingSLList<Item> extends SLList<Item> {
public void rotateRight(){
Item x = removeLast();
addFirst(x);
}
public static void main(String[] args){
RotatingSLList<Integer> rsl = new RotatingSLList<>();
rsl.addLast(10);
rsl.addLast(11);
rsl.addLast(12);
rsl.addLast(13);
rsl.rotateRight();
rsl.print();
}
}extends继承了SLList中的所有成员：
- 所有实例与静态变量
- 所有方法（除了构造函数）
- 所有嵌套类
但若成员是私有的就无法访问了
例：实现VengefulSLList
记录被删除的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package Lec16;
import java.util.ArrayList;
import java.util.List;
public class VengefulSLList<Item> extends SLList<Item>{
private SLList<Item> deletedItems ;
public VengefulSLList(){
deletedItems = new SLList<Item>();
}
@Override
public Item removeLast(){
Item removedItem = super.removeLast(); // 使用父类的方法
deletedItems.addLast(removedItem);
return removedItem;
}
public void printLostItems(){
deletedItems.print();
}
public static void main(String[] args){
VengefulSLList<Integer> vsl = new VengefulSLList<>();
vsl.addLast(1);
vsl.addLast(5);
vsl.addLast(10);
vsl.addLast(15);
vsl.removeLast();
vsl.removeLast();
vsl.printLostItems();
}
}这里我们实现了对继承方法的重写
其中，我们可以使用super来调用父类中的方法
BST
随机表
链表的搜索效率较慢，我们可以在不同节点间随机额外添加一些链接，这样可以依赖随机性获得更好的效率
二叉搜索树的原理
若我们将每次搜索都折半，就能大幅提高效率，一个链表可以进行如下改造：
这是一棵二叉搜索树
二叉搜索树是一个有根的二叉树，对于书中的每个节点
- 左子树中的每个节点的值都小于该节点的值
- 右子树中的每个节点的值都大于该节点的值
寻找特定元素
- 若待寻找元素等于当前元素，返回
- 若待寻找元素小于当前元素，前往左子树寻找
- 若待寻找元素大于当前元素，前往右子树寻找
时间复杂度：\(\Theta(\log n)\)
因此搜索一颗完全BST的速度是很快的
1
2
3
4
5
6
7
8
9
10
static BST find(BST T, key sk){
if (T==null)
return null;
if (sk.equals(T.key))
return T;
else if (sk<T.key)
return find(T.left, sk);
else
return find(T.right, sk);
}添加元素
首先寻找待插入元素
- 若找到了就不进行操作
- 若没找到
- 创建一个新节点
- 创建合适链接
使用递归书写
1
2
3
4
5
6
7
8
9
static BST insert(BST T, key ik){
if (T==null)
return new BST(ik);
if (ik<T.key)
T.left = insert(T.left, ik);
else if (ik>T.key)
T.right = insert(T.right, ik);
return T;
}删除元素
删除没有孩子的节点：
直接删除，即将其父节点对应的左/右节点置空
删除一个孩子的节点：
要在维持BST性质的前提下删除：可以发现该节点的孩子一定大于（右侧）或小于（左侧）该节点
故我们可以寻找该节点的孩子，将指向它的节点指向他的孩子即可
删除两个孩子的节点：
找到左子树最大的节点或右子树最小的节点，替代待删除节点即可
【CS61B】Lec15-Disjoint Sets
Lec15 - Disjoint Sets
解决连通性问题
较好的方法是只需要记录每个相连元素属于哪个集合，至于如何连接不必关心
数据结构的选择
sets
过于复杂并且耗时高
arrays
另一个想法是：起始将每个元素设置为不同id，只需要记录每个元素所在集合的id，连通只需要将该元素所在集合id改变为目标id即可；检查是否连通只需要检查id是否一致
时间复杂度：
连通方法复杂度还是高了一些
trees
想法是：给每一个元素分配一个父节点来代替id
对于连通操作：可以找到要连通的两个集合的根节点，将一个的根节点设置为另一个
对于检查连通操作：从待检查节点向上寻找父节点，一直找到根节点看是否相同即可
操作本质即寻根并操作根节点
时间复杂度：
优化树结构
我们需要最小化树高
- 将较短的树连接到较长的树下
- 若高度相同，则需要打破相同
规定：总是将更小的树根连接到更大的树上
注意：使用权重衡量才能最小化平均步数，而使用高度衡量只能最小化最坏步数
时间复杂度：
再次进行优化：
查找后将所有节点都连接到根节点上，这样再次查找不必再遍历
这样，随着操作继续，我们的树会变得越来越矮，直到树高为1，这样所有操作都很快
其中\(\alpha(N)\)为逆阿克曼函数，该函数的增长速度特别缓慢，对于具有意义的值x，\(\alpha(x)\)的值始终不大于4，故可以看作常数时间
【CS61B】Lec13-Asymptotics II
Lec13 - Asymptotics II
大\(\Theta\)
对于一个表达运行时间的式子\(R(N)\in \Theta(f(N))\)
意味着存在两个整数\(k_1\)与\(k_2\)使得\(k_1\cdot f(N)\leq R(N)\leq k_2 \cdot f(N)\)
对于所有\(N\geq N_0\)
常用该表示法描述函数的增长顺序与运行时长的增长率
大O
\(R(N)\in O(f(N))\)
意味着存在整数与\(k_2\)使得\(R(N)\leq k_2 \cdot f(N)\)
对于所有\(N\geq N_0\)
即大O表示仅被上界约束，描述小于等于\(f(N)\)
大\(\Omega\)
\(R(N)\in \Omega(f(N))\)
意味着存在两个整数\(k_1\)与\(k_2\)使得\(k_1\cdot f(N)\leq R(N)\)
对于所有\(N\geq N_0\)
常用该表示法描述函数的增长顺序与
即大\(\Omega\)表示仅被下界约束，描述大于等于\(f(N)\)
关系证明
证明若\(f(x)\in O(g(x))\)且\(f(x)\in \Omega(g(x))\)，则\(f(x)\in \Theta(g(x))\)
另一种表示形式
将\(g(x)\)除到\(f(x)\)下面，有\(a\leq \frac{f(x)}{g(x)}\leq b\)
若\(\frac{f(x)}{g(x)}\)有上界，则\(f(x)\in O(g(x))\)
若\(\frac{f(x)}{g(x)}\)有下界，则\(f(x)\in \Omega(g(x))\)
若\(\frac{f(x)}{g(x)}\)有界，则\(f(x)\in \Theta(g(x))\)
【CS61B】Lec11-Asymptotics I
Lec11 - Asymptotics I
衡量计算花费的方法
使用客户端程序测量执行时间
优点：易测量，意义明显
缺点：可能需要大量计算时间，结果可能因机器、编译器、数据不同而不同
计算可能的操作数
对于输出的大小为N的数组，计算可能的操作数
优点：独立于机器，输入基于给到的模型，显示了算法如何进行拓展
缺点：很难计算
对给定N大小数组，选择一个特定输入来代表输入规模，计算该操作数
特定输入包括：
- 最差情况
- 最好情况
渐进表现
大多数情况下，对于很大的数据N，我们只关心其渐进表现
具有较好规模（如线性）的算法会比具有相对差规模（如抛物线型）有着更好的运行时间表现
简化等式
将表格用多个变量的等式表示
忽略低阶项
- 将所有系数转换为一个常数，即\(CN^2\)，将拥有这些常数的函数归到一类，称为\(\Theta(N^2)\)
即\(\Theta(N^2)\)是包含了最坏运行时间的函数集合，用于表达运行时间
【CS61B】Lec10-Iterators, Object Methods
Lec10 - Iterators, Object Methods
Iterators
使用迭代器可以让自己的数据类型可以被迭代（支持for-each loop）
- 需要让对应类实现
Iterable接口 - 具有
Iterator方法来返回迭代器对象（实现一个嵌套类） - 迭代器需要具有
hasNext()和next()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package Lec10;
import java.util.Iterator;
public class ArraySet<T> implements Iterable<T> {
private T[] items;
private int size;
public ArraySet(){
items = (T[]) new Object[100];
size = 0;
}
private class ArraySetIterator implements Iterator<T>{
private int pos;
ArraySetIterator(){
pos = 0;
}
@Override
public boolean hasNext() {
if (pos<size){
return true;
}
return false;
}
@Override
public T next() {
T itemToReturn = items[pos];
pos++;
return itemToReturn;
}
}
public Iterator<T> iterator(){
return new ArraySetIterator();
}
}（注：仅有迭代器部分，没有其他具体实现）
Object Method
Java中所有类都是Object的子类
toString()
给予一个object的字符串表示
println方法也调用了toString()方法
该方法类似于python中的repr方法，可以给类一个自定义的字符串输出形式
1
2
3
4
5
6
7
8
9
10
@Override
public String toString(){
StringBuilder stringToReturn = new StringBuilder("{");
for(T x: this){
stringToReturn.append(x);
stringToReturn.append(", ");
}
stringToReturn.append("}");
return stringToReturn.toString();
}this
this是当前对象的一个引用，可以使用this来访问自己的实例变量和方法
但java中this是不必须的
若方法中的局部变量和实例变量重名，此时必须要用this加以区分
equals()
equals()方法通过判断两个对象的地址来判断是否相同
当然，可以通过重写方法来改变其他判断相同的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public boolean equals(Object o){
if (o instanceof ArraySet uSet){
if (this.size != uSet.size()){
return false;
}
for (T x: this){
if (!uSet.contains(x)){
return false;
}
}
return true;
}
return false;
}其中，关键字A instanceof B的用处如下
- 检查o是否指向类B，若不是返回false
- 若是，返回true并将A作为B类并命名为B后面的名字
- o是null也可以运行
【CS61B】Lec9-Subtype Polymorphism, Comparators, Comparables, Generic Functions
Lec9-Subtype Polymorphism, Comparators, Comparables, Generic Functions
Subtype Polymorphism
Java中没有重载运算符，故我们需要使用Comparable接口来实现类似功能
Java源码中对该接口的描述如下：
我们需要实现该接口
e.g. 定义Dog类，通过size属性比较两只狗的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package Lec9;
public class Dog implements Comparable<Dog>{
public String name;
public int size;
public Dog(String n, int s){
name = n;
size = s;
}
@Override
public int compareTo(Dog o) {
if (size < o.size){
return -1;
}
else if (size > o.size){
return 1;
}
return 0;
}
}另一种写法
java规定了若更小则返回负数
1
2
3
4
@Override
public int compareTo(Dog o) {
return size - o.size;
}这种操作被称为子类型多态
- 超类指定了可以干什么（如Comparable接口指定了比较功能）
- 子类通过重写超类的抽象方法，来使java根据调用方法的对象来决定运行时该做什么
Comparator
Java提供了接口Comparator用来比较其他对象
语法：
1
2
3
4
public interface Comparator<T>{
int compare(T o1, T o2);
...
}Dog类中
1
2
3
4
5
6
7
public static class NameComparator implements Comparator<Dog> {
@Override
public int compare(Dog a, Dog b) {
return a.name.compareTo(b.name);
}
}其中Dog.NameComparator()的数据类型为Comparator<Dog>
更现代的方式是使用lambda表达式定义comparator
1
2
Comparator<Dog> dc =(d1, d2) -> d1.name.compareTo(d2.name);
Dog maxNameDog = Collection.max(dogs,dc);泛型函数
如何编写自己的方法
e.g. 实现一个方法，从数组中随机选择一个元素，并且接受各种类型
在这里，选择随机元素的方法是静态的，正确方式是让方法本身变为泛型，而非让类变为泛型
即声明了一个公共静态函数，用于处理类型T的对象
因为如果让整个类泛型化，你需要实例化那个类来获得泛型行为，但把该方法作为一个静态方法来看，并不需要实例化
1
2
3
4
5
6
7
publicc class RandomPicker{
public static <T> T pickRandom(T[] x){
Random random = new Random();
int randomIndex = random.nextInt(x.length);
return x[randomIndex];
}
}