CS61B 课程笔记（Lecture 05）

双向链表 (Doubly Linked List) 实现

1. 基本结构

双向链表由节点组成，每个节点包含对前一个节点和下一个节点的引用。使用一个哨兵节点来简化边界条件的处理。

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
public class DLList<BleepBlorp> {
    private IntNode sentinel; // 哨兵节点
    private int size; // 链表大小

    // 节点类
    public class IntNode {
        public IntNode prev; // 指向前一个节点的引用
        public BleepBlorp item; // 存储的数据
        public IntNode next; // 指向下一个节点的引用

        // IntNode 构造器
        public IntNode(IntNode p, BleepBlorp x, IntNode n) {
            prev = p;
            item = x;
            next = n;
        }
    }

    // DLList 构造器
    public DLList() {
        sentinel = new IntNode(null, null, null); // 初始化哨兵节点
        sentinel.prev = sentinel; // 哨兵节点的前后引用指向自身
        sentinel.next = sentinel;
        size = 0;
    }
}

2. 添加元素的方法

我们可以实现多种添加元素的方法，包括在链表的开头和结尾添加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 在链表末尾添加元素
public void addLast(BleepBlorp x) {
    IntNode newNode = new IntNode(sentinel.prev, x, sentinel); // 创建新节点
    sentinel.prev.next = newNode; // 更新前一个节点的 next 引用
    sentinel.prev = newNode; // 更新哨兵节点的 prev 引用
    size++; // 增加链表大小
}

// 在链表开头添加元素
public void addFirst(BleepBlorp x) {
    IntNode newNode = new IntNode(sentinel, x, sentinel.next); // 创建新节点
    sentinel.next.prev = newNode; // 更新下一个节点的 prev 引用
    sentinel.next = newNode; // 更新哨兵节点的 next 引用
    size++; // 增加链表大小
}

3. 删除元素的方法

实现删除节点的方法时需要小心处理节点的引用。

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
// 删除给定节点
private void remove(IntNode node) {
    node.prev.next = node.next; // 更新前一个节点的 next 引用
    node.next.prev = node.prev; // 更新下一个节点的 prev 引用
    size--; // 减少链表大小
}

// 删除链表首元素
public BleepBlorp removeFirst() {
    if (size == 0) {
        throw new NoSuchElementException("链表为空");
    }
    BleepBlorp item = sentinel.next.item; // 获取首元素的值
    remove(sentinel.next); // 删除首元素
    return item; // 返回值
}

// 删除链表末尾元素
public BleepBlorp removeLast() {
    if (size == 0) {
        throw new NoSuchElementException("链表为空");
    }
    BleepBlorp item = sentinel.prev.item; // 获取末尾元素的值
    remove(sentinel.prev); // 删除末尾元素
    return item; // 返回值
}

4. 其他方法

实现一些常用方法，如获取链表大小和检查是否为空。

1
2
3
4
5
6
7
8
9
// 返回链表大小
public int size() {
    return size;
}

// 检查链表是否为空
public boolean isEmpty() {
    return size == 0;
}

5. 示例用法

创建一个双向链表并添加字符串元素的示例。

1
2
3
4
5
6
7
8
public static void main(String[] args) {
    DLList<String> d2 = new DLList<>();
    d2.addLast("hello");
    d2.addLast("world");
    System.out.println("链表大小: " + d2.size()); // 输出: 链表大小: 2
    System.out.println("删除首元素: " + d2.removeFirst()); // 输出: 删除首元素: hello
    System.out.println("链表大小: " + d2.size()); // 输出: 链表大小: 1
}

数组 (Arrays)

  1. 基础知识：

    • 数组具有固定的长度，所有元素必须为相同类型。
    • 数组可以通过 new 关键字或数组字面量来创建。
    1
    2
    3
    int[] x = new int[3]; // 创建一个长度为3的整型数组
    int[] y = new int[]{1, 2, 3, 4, 5}; // 使用数组字面量创建数组
    int[] z = {9, 10, 11, 12, 13}; // 简化的数组创建方式

  2. 访问与修改：

    • 可以通过索引访问数组元素，例如 s[4]。
    • 使用 System.arraycopy 方法进行数组的高效复制。
    1
    System.arraycopy(b, 0, x, 3, 2); // 将数组b的前两个元素复制到x数组中

  3. 二维数组：

    • 在Java中，二维数组实际上是一个数组的数组。
    1
    2
    int[][] pascalsTriangle = new int[4][]; // 创建一个长度为4的二维数组
    pascalsTriangle[0] = new int[]{1}; // 初始化第一行

Lists3 学习指南

  • 数组是Java中的一种特殊对象，由一系列编号的内存框组成。
  • 数组的长度不可更改，且所有元素必须为相同类型。
  • 数组和类的主要区别：
    • 数组使用 [] 符号访问元素；类使用点符号访问成员。
    • 数组中的所有元素必须是同一种类型；类的成员变量可以是不同类型。
    • 数组的索引可以在运行时计算；类的成员变量名在运行时不能计算。

示例问题

  1. 按纬度分组：

    1
    2
    3
    4
    5
    6
    public Piece[][] groupByLat(Piece[] p) {
        int width = (int) Math.sqrt(p.length); // 计算数组的宽度
        Piece[][] latGroup = new Piece[width][width]; // 创建二维数组
        // 填充latGroup的逻辑...
        return latGroup;
    }

  2. 排序操作：

    • 处理对象数组的排序和管理，基于特定属性进行排序。

  3. 长度比较器：

    1
    2
    3
    4
    5
    6
    public int LengthComparator(String s1, String s2) {
        if (s1 == null && s2 == null) return 0; // 两个字符串均为null
        if (s1 == null) return -1; // s1为null，s2不为null
        if (s2 == null) return 1; // s2为null，s1不为null
        return s1.length() - s2.length(); // 返回长度差
    }

A+级问题

  • 重点关注图论，尤其是有向图中两点之间的最远距离问题。

题外话：

1. 双向链表 (DLList) 的缺点与解决方案

1.1 SLList 的缺点

  • 添加到末尾的速度慢：在单向链表 (SLList) 中，addLast() 方法需要从头遍历到尾才能添加元素。
  • 无法在中间插入：SLList 只支持在头部或尾部添加元素，无法快速插入到中间。

1.2 解决方案

  • 缓存末尾元素：通过缓存链表的最后一个元素，可以快速实现 addLast()。但这导致 removeLast() 仍然很慢，因为需要找到倒数第二个元素。
  • 双向链表 (DLList)：通过为每个节点添加一个 prev 指针，创建一个双向链表，允许快速在前后添加和删除元素。

1.3 哨兵节点

  • 单个循环哨兵：在双向链表中，可以使用一个循环的哨兵节点。哨兵节点的 next 指向第一个元素，prev 指向最后一个元素，形成一个循环结构。
  • 空链表的情况：在空链表中，哨兵节点的 next 和 prev 都指向自身。

1.4 泛型 DLList

  • 泛型定义：将 DLList 类定义为 public class DLList<T>，使其支持任何类型的对象。

  • 使用示例：创建一个字符串类型的双向链表：

    1
    DLList<String> list = new DLList<>("hello");

2. 数组

2.1 数组的基本概念

  • 内存盒子：数组是一种特殊对象，由编号序列的内存盒子组成。
  • 固定长度：数组长度不可更改，且所有元素必须为同一类型。

2.2 数组的声明与初始化

  • 声明与默认值：

    1
    int[] y = new int[3]; // 创建一个长度为3的数组，填充默认值0

  • 具体值的初始化：

    1
    2
    int[] x = new int[]{1, 2, 3, 4, 5}; // 指定初始值
    int[] w = {1, 2, 3, 4, 5}; // 另一种语法

2.3 数组的操作

  • 访问和赋值：

    1
    A[3] = 4; // 设置数组 A 的第四个元素为 4

  • 数组复制：

    1
    System.arraycopy(sourceArray, srcPos, destArray, destPos, length);

2.4 多维数组

  • 二维数组的声明：

    1
    2
    int[][] array = new int[4][]; // 创建一个长度为4的二维数组
    array[0] = new int[]{0, 1, 2, 3}; // 手动创建内层数组

3. 数组与类的比较

特性 数组 类
组织方式 一组固定大小的盒子 对象，可以包含不同类型的变量
访问方式 使用方括号语法 使用点语法
元素类型 所有元素必须相同 元素可以是不同类型
索引计算 运行时计算 变量名称在编译时固定

练习：

以下是练习题的中文翻译及解答：

C 级练习

练习 1：创建一个不同类型的二维数组

在 Java 中，数组中的元素必须是相同类型的。然而，你可以创建一个对象数组，其中每个对象可以是不同类型的。下面是一个例子：

1
2
3
4
5
6
7
Object[][] mixedArray = new Object[2][];
mixedArray[0] = new String[]{"Hello", "World"}; // 字符串子数组
mixedArray[1] = new Integer[]{1, 2, 3}; // 整数子数组

// 访问元素
String firstString = (String) mixedArray[0][0]; // "Hello"
Integer firstInt = (Integer) mixedArray[1][0]; // 1

B 级练习

练习 1：理解 Deck 类和卡片内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Deck {
    public static int[] cards;
    
    Deck() {
        cards = new int[]{1, 3, 4, 10}; // 数组初始化的正确语法
    }
}

// 创建 Deck 实例
Deck dingie = new Deck();
dingie.cards[3] = 3; // 修改最后一个元素

// dingie 的数组内容
// dingie.cards = {1, 3, 4, 3}

练习 2：修改另一个 Deck 实例的卡片

1
2
3
4
5
6
Deck pilates = new Deck();
pilates.cards[1] = 2; // 修改第二个元素

// pilates 和 dingie 的数组内容
// pilates.cards = {1, 2, 4, 10} 
// dingie.cards = {1, 3, 4, 3}

练习 3：数组引用的变化

1
2
3
4
5
6
7
8
int[] newArrWhoDis = {2, 2, 4, 1, 3};
dingie.cards = pilates.cards; // dingie 的 cards 现在引用 pilates 的 cards
pilates.cards = newArrWhoDis; // pilates 的 cards 现在引用 newArrWhoDis
newArrWhoDis = null; // newArrWhoDis 现在引用 null

// 最终数组的内容
// dingie.cards = {1, 2, 4, 10}
// pilates.cards = {2, 2, 4, 1, 3}

练习 4：添加到二维 DList

为了实现一个方法，使元素在二维 DList 中尽可能均匀地添加，你可以创建一个如下的方法：

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
public class DList {
    private List<List<Integer>> rows;

    public DList() {
        this.rows = new ArrayList<>();
    }

    public void addElement(int element) {
        for (List<Integer> row : rows) {
            if (row.size() < (getMaxRowSize() + 1)) {
                row.add(element);
                return;
            }
        }
        List<Integer> newRow = new ArrayList<>();
        newRow.add(element);
        rows.add(newRow);
    }

    private int getMaxRowSize() {
        int maxSize = 0;
        for (List<Integer> row : rows) {
            maxSize = Math.max(maxSize, row.size());
        }
        return maxSize;
    }
}

这个方法将尝试尽可能均匀地填充行。如果一行已经达到最大容量（最大的行大小 + 1），它将移动到下一行，直到找到合适的位置或创建新行。

A+ 级思路

You are a lonesome tortoise trying to find their way in the galaxy. Suddenly, a portal opens up in front of you and holy mackerel, it leads to a new galaxy! You almost leap into the new galaxy, but you are scared- after all, you want to be able to come home so, at some point, you can have your porridge. After some asking around, you realized that at certain points in a given galaxy you can transport to a different galaxy (though you may not be able to take the same point back); however, if you are in a galaxy, you can reach any point in that galaxy for sure.

You want to try to maximize the amount of galaxies that you can visit while still ensuring that you can make it back home. Provide an idea of how you will do this (no need to code; however, you can if you want).

你是一只孤独的乌龟，正在努力寻找在银河系中的路。突然，一个传送门在你面前打开，哇哦，它通向一个新的星系！你差点就跳进新的星系，但你感到害怕——毕竟，你希望能够回家，好在某个时候吃你的粥。经过一番询问，你意识到在给定星系中的某些点，你可以传送到不同的星系（尽管你可能无法从同一个点返回）；然而，如果你在一个星系中，你可以肯定地到达该星系中的任何点。

你想尽量多访问一些星系，同时确保能够回家。请提供一个想法，说明你将如何做到这一点（不需要编码，但如果你想的话可以）。

如果考虑到边权都是1的情况，可以将问题转化为有向图的最长路径问题，以确保在访问星系时找到最大可达的星系数量。

有向图最长路径问题建模

  1. 节点：每个星系。
  2. 有向边：可以从一个星系传送到另一个星系的路径。
  3. 起点：乌龟的家。

数据结构

我们仍然使用邻接表表示图，但这次我们需要考虑路径的方向，并且需要实现一个算法来计算最长路径。

实现代码

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
51
52
53
54
55
56
57
58
59
60
61
import java.util.*;

class Galaxy {
    private Map<String, List<String>> graph; // 有向图的邻接表
    private Map<String, Integer> longestPath; // 存储每个星系的最长路径
    private String home; // 乌龟的家

    public Galaxy(String home) {
        this.graph = new HashMap<>();
        this.longestPath = new HashMap<>();
        this.home = home;
    }

    // 添加星系间的有向连接
    public void addDirectedConnection(String from, String to) {
        graph.putIfAbsent(from, new ArrayList<>());
        graph.get(from).add(to);
    }

    // 深度优先搜索计算最长路径
    private int dfs(String galaxy, Set<String> visited) {
        if (longestPath.containsKey(galaxy)) {
            return longestPath.get(galaxy);
        }

        visited.add(galaxy);
        int maxLength = 0;

        for (String neighbor : graph.getOrDefault(galaxy, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                maxLength = Math.max(maxLength, dfs(neighbor, visited) + 1);
            }
        }

        visited.remove(galaxy);
        longestPath.put(galaxy, maxLength);
        return maxLength;
    }

    // 启动最长路径计算
    public int startLongestPath() {
        return dfs(home, new HashSet<>());
    }
}

public class Main {
    public static void main(String[] args) {
        Galaxy galaxyMap = new Galaxy("Earth"); // 假设乌龟的家是地球

        // 添加有向连接
        galaxyMap.addDirectedConnection("Earth", "GalaxyA");
        galaxyMap.addDirectedConnection("GalaxyA", "GalaxyB");
        galaxyMap.addDirectedConnection("GalaxyB", "GalaxyC");
        galaxyMap.addDirectedConnection("GalaxyC", "GalaxyD");
        galaxyMap.addDirectedConnection("GalaxyA", "GalaxyC"); // 额外路径

        // 计算最长路径
        int maxPathLength = galaxyMap.startLongestPath();
        System.out.println("从家到可达的最大星系数量: " + (maxPathLength + 1)); // 加1是因为包括起点
    }
}

说明

  1. 添加有向连接：addDirectedConnection 方法用于在星系之间建立有向连接。
  2. 深度优先搜索：dfs 方法用于计算从当前星系出发的最长路径，并使用记忆化技术优化计算。
  3. 启动计算：startLongestPath 方法从乌龟的家开始计算最长路径。
  4. 输出结果：输出从乌龟的家到可达的最大星系数量。

课程补充：

静态变量与静态方法

静态变量

  • 定义：静态变量是属于类的变量，而不是类的实例。所有实例共享同一份静态变量。

  • 访问方式：应该通过类名来访问静态变量，而不是通过实例。例如：

    1
    2
    3
    4
    5
    public class MyClass {
        static int staticVar = 10;
    }

    int value = MyClass.staticVar; // 推荐的访问方式

静态方法

  • 定义：静态方法不依赖于类的实例，可以直接通过类名调用。

  • 实例变量访问：静态方法不能直接访问实例变量，因为实例变量属于特定的对象，而静态方法不需要对象实例。

  • 调用方式：尽管可以通过实例调用静态方法，但不推荐这样做，因为可能会引起混淆。实际上，Java会查找对象的静态类型并运行相应类的静态方法。例如：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public class MyClass {
        static void staticMethod() {
            System.out.println("Static method called");
        }
    }

    MyClass obj = new MyClass();
    obj.staticMethod(); // 这虽然可以，但不推荐
    MyClass.staticMethod(); // 推荐的方式

迭代与递归的转换

在许多情况下，递归可以转换为迭代，以节省内存或提高性能。以下是一些要点：

  1. 递归：使用函数自身调用自身，通常伴随着条件检查和基线条件（即停止递归的条件）。

    1
    2
    3
    4
    public int factorialRecursion(int n) {
        if (n <= 1) return 1;
        return n * factorialRecursion(n - 1);
    }

  2. 迭代：使用循环结构（如for或while）来重复执行代码。通常使用临时变量来存储状态。

    1
    2
    3
    4
    5
    6
    7
    public int factorialIteration(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }

灵活使用临时变量

在将递归转换为迭代时，通常需要使用临时变量来维护状态。例如，在计算阶乘时，可以用一个变量来存储当前的结果。对于更复杂的递归问题，如树的遍历，可以使用栈来模拟递归的调用栈。

示例：树的深度优先遍历

  • 递归方式：

    1
    2
    3
    4
    5
    6
    public void dfsRecursive(TreeNode node) {
        if (node == null) return;
        // 处理节点
        dfsRecursive(node.left);
        dfsRecursive(node.right);
    }

  • 迭代方式：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public void dfsIterative(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                // 处理节点
                stack.push(node.right); // 注意顺序，先右后左
                stack.push(node.left);
            }
        }
    }

Scope, Pass-by-Value, Static

1. 静态变量（Static Variables）

  • 定义：静态变量是属于类的，不属于任何特定实例。所有实例共享相同的静态变量。

  • 用途：通常用于追踪类级别的信息或状态。例如，计数器统计所有实例的数量。

  • 访问方式：可以通过类名访问静态变量，而不需要实例。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public class Example {
        static int count = 0; // 静态变量

        public Example() {
            count++; // 每次创建实例时增加计数
        }
    }

    // 访问静态变量
    int totalInstances = Example.count;

2. 作用域（Scope）

  • 局部变量：局部变量的作用范围仅限于其定义的代码块（通常是 {} 之间）。一旦代码块执行完毕，局部变量就会被销毁。

    1
    2
    3
    4
    5
    6
    7
    public void myMethod() {
        int localVar = 10; // 局部变量
        if (localVar > 5) {
            int innerVar = 20; // innerVar 仅在此 if 块内可用
        }
        // innerVar 不能在这里访问
    }

  • 类变量和实例变量：它们的作用域在整个类中有效，可以在类的任何方法中访问。

3. 传值（Pass-by-Value）

  • 定义：Java 中所有方法参数的传递都是“传值”。这意味着方法接收的是参数的副本，而不是原始变量的引用。

  • 基本类型：传递基本数据类型时，实际传递的是值的副本。

    1
    2
    3
    public void modifyValue(int x) {
        x = 20; // 修改的是副本，不会影响外部的变量
    }

  • 对象类型：传递对象时，传递的是对象引用的副本。虽然引用本身是一个副本，但通过该引用可以修改对象的内容。

    1
    2
    3
    public void modifyObject(MyObject obj) {
        obj.value = 20; // 修改的是对象内容
    }

4. Quik Maths

  • 数学运算符：Java 支持基本的数学运算符，包括 +, -, *, / 和 %。

  • 运算顺序：运算符的优先级决定了表达式的计算顺序，例如乘法和除法优先于加法和减法。

  • 示例：

    1
    2
    3
    int a = 10;
    int b = 20;
    int c = a + b * 2; // 结果为 50，因为乘法优先

  • 自增自减：使用 ++ 和 -- 运算符，可以方便地增加或减少变量的值。

    1
    2
    int x = 5;
    x++; // x 变为 6