Lecture 1.1 - Arrays

一、数组基础：为什么需要数组？

核心问题引入

假设要读取 100 个数字并计算平均值，还要找出大于平均值的数字个数。如果为每个数字都创建一个变量，显然不现实。这时，数组就能派上用场，它可以用一个变量存储多个同类型的数据。

数组的定义与特点

• 定义：数组是相同数据类型元素的集合，有固定的长度，通过索引（从 0 开始）访问元素。
• 内存存储：数组在内存的堆区分配空间，变量存储的是数组的引用（内存地址）。

二、数组的声明与创建

1. 声明数组变量

• 语法：

  1 2	数据类型[] 数组名; // 推荐写法，如 double[] myList; 数据类型 数组名[]; // 允许但不推荐，如 double myList[];

2. 创建数组（分配内存）

• 语法：

  1	数组名 = new 数据类型[长度]; // 如 myList = new double[10];

• 示例：

  1 2	double[] myList; // 声明 myList = new double[10]; // 创建，长度为 10

3. 声明与创建合并

1

double[] myList = new double[10]; // 一步完成

三、数组初始化

1. 默认值

• 数值型（如 int、double）：默认值为 0。
• 布尔型：默认值为 false。
• 引用类型（如 String）：默认值为 null。

2. 手动赋值

• 通过索引赋值：

  1 2	myList[0] = 5.6; // 给第一个元素赋值 myList[1] = 4.5; // 给第二个元素赋值

3. 快捷初始化（数组初始化器）

• 语法：

  1	数据类型[] 数组名 = {值1, 值2, 值3, ...}; // 声明、创建、赋值一步完成

• 示例：

  1	int[] scores = {85, 90, 78}; // 长度为 3

四、数组常用操作

1. 遍历数组

• 普通 for 循环（带索引）：

  1 2 3

  for (int i = 0; i < myList.length; i++) { System.out.println(myList[i]); // length 是数组属性，获取长度 }

• 增强 for 循环（for-each，无索引）：

  1 2 3

  for (double value : myList) { // 依次取出每个元素赋值给 value System.out.println(value); }

2. 常见算法

• 求和：

  1 2 3 4

  double sum = 0; for (double num : myList) { sum += num; }

• 找最大值：

  1 2 3 4 5 6

  double max = myList[0]; // 假设第一个元素是最大值 for (int i = 1; i < myList.length; i++) { if (myList[i] > max) { max = myList[i]; // 发现更大值，更新 max } }

• 数组复制：
  • 错误做法（引用复制）：

    1 2	int[] arr1 = {1, 2, 3}; int[] arr2 = arr1; // arr2 和 arr1 指向同一个数组，修改 arr2 会影响 arr1

  • 正确做法（元素复制）：

    1 2 3 4 5

    int[] arr1 = {1, 2, 3}; int[] arr2 = new int[arr1.length]; for (int i = 0; i < arr1.length; i++) { arr2[i] = arr1[i]; // 逐个元素复制 }

五、数组作为方法参数

1. 传递数组（按值传递引用）

• Java 中传递数组时，实际传递的是数组的引用（内存地址），因此方法内对数组元素的修改会影响原始数组。
• 示例：

  1 2 3 4 5 6 7 8 9

  public static void changeArray(int[] arr) { arr[0] = 100; // 修改数组第一个元素 } public static void main(String[] args) { int[] numbers = {1, 2, 3}; changeArray(numbers); // 调用方法 System.out.println(numbers[0]); // 输出 100（原始数组被修改） }

2. 返回数组

• 方法可以返回一个数组，例如反转数组：

  1 2 3 4 5 6 7

  public static int[] reverse(int[] list) { int[] result = new int[list.length]; for (int i = 0, j = result.length - 1; i < list.length; i++, j--) { result[j] = list[i]; // 首尾元素交换 } return result; // 返回新数组 }

六、搜索与排序算法

1. 线性搜索（适用于未排序数组）

• 原理：从数组第一个元素开始，逐个与目标值比较，直到找到或遍历完数组。
• 代码：

  1 2 3 4 5 6 7 8

  public static int linearSearch(int[] list, int key) { for (int i = 0; i < list.length; i++) { if (list[i] == key) { return i; // 找到，返回索引 } } return -1; // 未找到，返回 -1 }

2. 二分搜索（适用于已排序数组，效率更高）

• 原理：每次将数组分成两半，根据中间元素与目标值的大小关系，缩小搜索范围。
• 时间复杂度：O(log n)（最坏情况）。
• 代码：

  1 2 3 4 5 6 7 8 9 10

  public static int binarySearch(int[] list, int key) { int low = 0, high = list.length - 1; while (low <= high) { int mid = (low + high) / 2; if (key == list[mid]) return mid; // 找到 else if (key < list[mid]) high = mid - 1; // 目标值在左半部分 else low = mid + 1; // 目标值在右半部分 } return -1; // 未找到 }

3. 选择排序（简单直观，效率较低）

• 原理：每次从剩余元素中找到最小值，与当前位置元素交换。
• 代码：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  public static void selectionSort(int[] list) { for (int i = 0; i < list.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < list.length; j++) { if (list[j] < list[minIndex]) { minIndex = j; // 更新最小值索引 } } // 交换当前元素与最小值 int temp = list[i]; list[i] = list[minIndex]; list[minIndex] = temp; } }

七、练习与 Quiz

练习 1：数组初始化判断

下面哪个是正确的数组初始化方式？

1
2
3

A. int[] arr = new int {1, 2, 3};
B. int[] arr = {1, 2, 3};
C. int arr[3] = {1, 2, 3};

答案：B（A 缺少长度；C 是 C/C++ 语法，Java 不支持）。

练习 2：增强 for 循环

1
2
3
4
5

int[] numbers = {1, 2, 3, 4, 5};
for (int num : numbers) {
    num *= 2; // 修改的是副本，不影响原数组
}
System.out.println(numbers[2]); // 输出什么？

答案：3（增强 for 循环中无法通过 num 修改原数组元素）。

练习 3：二分搜索时间复杂度

二分搜索的最坏时间复杂度是？

1

A. O(1)  B. O(n)  C. O(log n)  D. O(n²)

答案：C（每次折半，时间复杂度为对数级）。

八、总结

• 重点知识：数组的声明与创建、初始化、遍历、作为方法参数传递、搜索与排序算法。
• 常见误区：
  • 数组长度不可变，创建后无法修改。
  • 直接赋值 arr2 = arr1 是引用复制，而非元素复制。
  • 二分搜索必须在已排序数组上使用。

Lecture 1.2 - Objects and Classes

一、核心概念：对象与类

1. 什么是对象？

• 定义：对象是现实世界中可唯一标识的实体，例如“一个圆形”“一个学生”。
• 特征：
  • 状态（State）：用数据字段（属性）表示，如圆形的半径radius。
  • 行为（Behavior）：用方法（函数）表示，如计算面积的getArea()。

2. 什么是类？

• 定义：类是对象的模板/蓝图，用于创建具有相同属性和方法的对象。
• 组成：
  • 数据字段（Fields）：如private double radius;（非静态，属于每个对象）。
  • 方法（Methods）：如public double getArea()（非静态方法需通过对象调用）。
  • 构造函数（Constructors）：用于创建对象，名称必须与类名相同，无返回类型。

示例：Circle类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class Circle {
    private double radius = 1.0; // 数据字段（默认值1.0）

    // 无参构造函数
    public Circle() { }

    // 有参构造函数
    public Circle(double newRadius) {
        radius = newRadius;
    }

    // 实例方法：计算面积
    public double getArea() {
        return radius * radius * 3.14159;
    }
}

二、创建对象与内存分析

1. 对象创建步骤

1. 声明引用变量：Circle myCircle;（此时变量值为null，未指向任何对象）。
2. 实例化对象：myCircle = new Circle(5.0);（通过new关键字调用构造函数，分配内存）。

2. 内存示意图

1

myCircle  →  { radius: 5.0 }  // 对象在堆内存中，引用变量指向对象

3. 访问对象成员

• 访问属性：对象名.属性（需注意权限，如private属性不可直接访问）。
• 调用方法：对象名.方法名()。

示例：

1
2
3

Circle c1 = new Circle();       // 调用无参构造，radius=1.0
Circle c2 = new Circle(5.0);    // 调用有参构造，radius=5.0
System.out.println(c2.getArea()); // 输出：78.53975（5²×π）

三、关键知识点解析

1. 静态（Static） vs 非静态（Non-static）

示例：静态变量numberOfObjects

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Circle {
    private static int numberOfObjects = 0; // 静态变量，记录创建的对象总数

    public Circle() {
        numberOfObjects++; // 每次创建对象时计数加1
    }

    public static int getNumberOfObjects() { // 静态方法，返回计数
        return numberOfObjects;
    }
}

// 使用方式：
System.out.println(Circle.getNumberOfObjects()); // 直接通过类名调用

2. 访问修饰符（Visibility Modifiers）

封装最佳实践：

• 将数据字段设为private，通过访问器（getter）和修改器（setter）方法间接操作。

  1 2 3 4 5 6 7 8 9 10 11 12 13

  public class Circle { private double radius; // 访问器（getter） public double getRadius() { return radius; } // 修改器（setter） public void setRadius(double radius) { this.radius = radius; // `this`指代当前对象 } }

3. 基本类型 vs 引用类型

注意：修改引用类型的属性会影响所有指向它的变量！

1
2
3

Circle c1 = new Circle(5);
Circle c2 = c1;          // c2引用c1的对象
c2.setRadius(10);        // c1和c2的radius都会变为10

四、UML类图快速入门

UML类图用于可视化类的结构，常见符号：

1
2
3
4
5
6
7
8
9
10

+-----------------+
|     Circle      |          // 类名
+-----------------+
| - radius: double|          // 私有属性（-）
| + numberOfObjects: static int | // 静态属性（下划线）
+-----------------+
| + Circle()      |          // 构造函数
| + Circle(radius: double) | 
| + getArea(): double       | // 公共方法（+）
+-----------------+

五、实战练习

练习1：定义学生类

需求：

• 定义Student类，包含私有字段name（String）、age（int）、isScienceMajor（boolean）。
• 提供构造函数初始化name和age，isScienceMajor默认false。
• 提供getter和setter方法。
• 在main方法中创建学生对象，设置专业为true，并输出信息。

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Student {
    private String name;
    private int age;
    private boolean isScienceMajor = false; // 默认值false

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // getter和setter
    public String getName() { return name; }
    public int getAge() { return age; }
    public boolean isScienceMajor() { return isScienceMajor; }
    public void setScienceMajor(boolean isScienceMajor) {
        this.isScienceMajor = isScienceMajor;
    }

    public static void main(String[] args) {
        Student stu = new Student("Alice", 20);
        stu.setScienceMajor(true);
        System.out.println(stu.getName() + "是科学专业吗？" + stu.isScienceMajor()); // 输出：Alice是科学专业吗？true
    }
}

练习2：静态方法应用

需求：在Circle类中添加静态方法calculateArea(double radius)，无需创建对象即可计算面积。

参考答案：

1
2
3
4
5
6
7
8
9
10
11

public class Circle {
    // ...原有代码...

    // 静态方法：直接通过类名调用，计算任意半径的面积
    public static double calculateArea(double radius) {
        return radius * radius * 3.14159;
    }

    // 使用示例：
    double area = Circle.calculateArea(5); // 直接调用，无需创建对象
}

六、常见问题解答

1. 为什么构造函数没有返回类型？
   构造函数的作用是初始化对象，不是“返回”对象，因此无需声明返回类型（包括void）。

2. 静态变量什么时候初始化？
   静态变量在类加载时初始化，早于对象创建，且仅初始化一次。

3. this关键字的作用是什么？
   this指代当前对象，用于区分方法参数与类的字段（如this.radius = radius;）。

Lecture 2.1 - Thinking in Objects

第一部分：核心概念

1. 不可变对象与类（Immutable Objects and Classes）

定义：对象一旦创建，内容不可修改，其类称为不可变类。
条件（缺一不可）：

1. 所有数据字段为 private
2. 无 set 方法（mutator）
3. 不返回可变对象的引用（如数组、自定义对象）

示例：不可变的 Circle 类

1
2
3
4
5

public class Circle {
    private double radius;
    public Circle(double radius) { this.radius = radius; }
    public double getRadius() { return radius; } // 仅有 getter，无 setter
}

反例：可变的 Student 类

1
2
3
4
5
6
7
8
9
10
11

public class Student {
    private int id;
    private BirthDate birthDate; // BirthDate 是可变类
    public BirthDate getBirthDate() { 
        return birthDate; // 返回可变对象引用，外部可通过该引用修改内部状态
    }
}
public class BirthDate {
    private int year;
    public void setYear(int newYear) { year = newYear; } // 有 setter，可变
}

为什么可变？

1
2

Student student = new Student(...);
student.getBirthDate().setYear(2050); // 通过引用修改内部对象状态，导致 Student 实际可变

练习题1：
判断以下类是否为不可变类？为什么？

1
2
3
4
5
6
7
8
9
10
11
12

public class Book {
    private String title;
    private Author author; // Author 类有 public 的 name 字段
    public Book(String title, Author author) {
        this.title = title;
        this.author = author;
    }
    public Author getAuthor() { return author; }
}
public class Author {
    public String name; // 字段非 private
}

2. 变量作用域（Scope of Variables）

示例：

1
2
3
4
5
6
7
8
9
10

public class ScopeDemo {
    int instanceVar; // 实例变量，默认值 0
    static int staticVar; // 静态变量，默认值 0
    
    public void method() {
        int localVar; // 局部变量，未初始化不能使用！
        // System.out.println(localVar); // 编译错误！
        localVar = 10; // 必须先赋值
    }
}

练习题2：
指出以下代码的错误：

1
2
3
4
5
6
7

public class Test {
    public void printSum() {
        int a = 10;
        int b;
        System.out.println(a + b); // 错误？为什么？
    }
}

3. this 关键字（The this Keyword）

作用：

1. 引用当前对象的成员：当局部变量与成员变量同名时，用 this 区分。

   1 2 3 4 5 6

   public class Person { private String name; public Person(String name) { this.name = name; // this.name 指成员变量，name 指参数 } }

2. 在构造方法中调用重载的构造方法：必须作为构造方法的第一条语句。

   1 2 3 4 5

   public class Circle { private double radius; public Circle() { this(1.0); } // 调用 Circle(double radius) public Circle(double radius) { this.radius = radius; } }

注意：静态方法中不能使用 this（静态方法属于类，不属于对象）。

4. 类的抽象与封装（Class Abstraction and Encapsulation）

核心思想：

• 抽象：对外暴露功能（API），隐藏实现细节（如方法内部逻辑、数据存储方式）。
• 封装：通过 private 修饰符隐藏数据字段，仅通过公共方法（getter/setter）访问。

示例：Loan 类的封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Loan {
    private double annualInterestRate;
    private int numberOfYears;
    
    // 构造方法与公共方法（API）
    public Loan(double rate, int years) {
        this.annualInterestRate = rate;
        this.numberOfYears = years;
    }
    public double getMonthlyPayment() { 
        // 隐藏计算逻辑，仅暴露结果
        double monthlyRate = annualInterestRate / 1200;
        return ...; 
    }
}

优点：

• 数据安全（防止非法修改）
• 易维护（修改内部实现不影响外部调用）

第二部分：具体类设计实践

1. 设计 Loan 类

需求：计算贷款的月还款额和总还款额。
属性：年利率、贷款年限、贷款金额、创建日期
方法：计算月还款（getMonthlyPayment）、总还款（getTotalPayment）

关键代码：

1
2
3
4
5
6

public double getMonthlyPayment() {
    double monthlyRate = annualInterestRate / 1200;
    double numerator = loanAmount * monthlyRate;
    double denominator = 1 - Math.pow(1 / (1 + monthlyRate), numberOfYears * 12);
    return numerator / denominator;
}

练习题3：
修改 Loan 类，添加一个 getDailyPayment() 方法，计算每日还款额（假设一年 365 天）。

2. 设计 BMI 类

需求：计算身体质量指数（BMI）并判断健康状态。
公式：

1

BMI = 体重（磅） × 0.45359237 / (身高（英寸） × 0.0254)^2

状态判断：

• <16：严重偏瘦
• 16~18：偏瘦
• 18~24：正常
• 24~29：超重
• ≥29：严重超重

关键代码：

1
2
3
4
5

public String getStatus() {
    double bmi = getBMI();
    if (bmi < 16) return "seriously underweight";
    // ... 其他条件
}

练习题4：
修改 BMI 类，增加一个构造方法，允许传入体重（公斤）和身高（米），并重载 getBMI() 方法。

第三部分：常用类详解

1. String 类（不可变性与常用方法）

不可变性：

1
2

String s = "Java";
s = s + " HTML"; // 原 "Java" 对象不变，新建 "Java HTML" 对象

字符串比较：

示例：

1
2
3
4

String s1 = "Hello";
String s2 = new String("Hello");
System.out.println(s1 == s2); // false（引用不同）
System.out.println(s1.equals(s2)); // true（内容相同）

常用方法：

• 截取子串：substring(start, end)（左闭右开）

  1	"HelloWorld".substring(3, 7); // "loWo"

• 查找字符/子串：indexOf("sub")（返回首次出现的索引，未找到返回 -1）
• 替换：replace("old", "new")（返回新字符串，原字符串不变）

2. StringBuilder 与 StringBuffer

区别：

• StringBuilder：非线程安全，效率高（推荐单线程使用）
• StringBuffer：线程安全，效率低（适合多线程环境）

核心操作：

1
2
3
4
5

StringBuilder sb = new StringBuilder("Java");
sb.append(" HTML"); // 追加 → "Java HTML"
sb.insert(4, " and "); // 插入 → "Java and HTML"
sb.delete(0, 4); // 删除前 4 个字符 → " and HTML"
sb.reverse(); // 反转 → "MLTH and "

何时使用？：需要频繁修改字符串时（如循环拼接），用 StringBuilder 代替 String，避免生成大量临时对象。

3. 正则表达式（Regular Expressions）

作用：用于字符串匹配、验证、替换、分割。
示例：

• 验证邮箱：^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$
• 提取数字：String[] nums = "a1b2c3".split("\\D"); // ["1", "2", "3"]
• 替换特殊字符："a$b#c".replaceAll("[\\$#]", "X"); // "aXbXc"

练习题5：
编写正则表达式，验证手机号（以 1开头，第二位 3-9，共11位数字）。

第四部分：综合练习

设计 Course 类

需求：管理课程的学生列表，支持添加学生、获取学生列表、动态扩容。
属性：课程名、学生数组、学生人数
关键代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Course {
    private String courseName;
    private String[] students = new String[10]; // 初始容量 10
    private int numberOfStudents;
    
    public void addStudent(String student) {
        if (numberOfStudents >= students.length) {
            String[] newStudents = new String[students.length * 2];
            System.arraycopy(students, 0, newStudents, 0, students.length);
            students = newStudents; // 扩容为原来的 2 倍
        }
        students[numberOfStudents++] = student;
    }
}

Lecture 2.2 - Inheritance and Polymorphism

一、继承的基本概念

1. 为什么需要继承？

• 动机：当多个类（如Circle、Rectangle）有共同属性（color、filled）和方法（getArea、getPerimeter）时，通过继承可以避免代码冗余。
  • 父类（超类）：提取公共属性和方法，如GeometricObject。
  • 子类：继承父类，并添加特有的属性和方法，如Circle添加radius和getDiameter。

2. 如何声明子类？

• 语法：使用extends关键字。

  1 2 3 4 5

  public class Circle extends GeometricObject { private double radius; // 子类特有的属性 // 子类特有的方法 public double getDiameter() { return 2 * radius; } }

• 子类继承父类的哪些成员？
  • 继承：非private的属性和方法（如color是private，需通过getColor()访问）。
  • 不继承：构造方法（需显式或隐式调用父类构造方法）。

二、构造函数与super关键字

1. 构造函数链（Constructor Chaining）

• 规则：子类构造函数必须先调用父类构造函数（通过super()或this()），默认调用父类无参构造函数。

  1 2 3 4 5 6 7 8 9 10 11 12

  public class Rectangle extends GeometricObject { public Rectangle(double width, double height) { super(); // 隐式调用父类无参构造函数（可省略） this.width = width; this.height = height; } public Rectangle(double width, double height, String color, boolean filled) { super(color, filled); // 显式调用父类有参构造函数 this.width = width; this.height = height; } }

• 示例分析：

  1 2 3 4

  class Person { public Person() { System.out.println("Person"); } } class Employee extends Person { public Employee() { super(); System.out.println("Employee"); } } class Faculty extends Employee { public Faculty() { super(); System.out.println("Faculty"); } } // 执行 new Faculty() 时输出：Person → Employee → Faculty

2. super关键字的作用

• 调用父类构造函数：必须作为子类构造函数的第一行。
• 调用父类被重写的方法：

  1 2 3 4 5 6

  public class Circle { @Override public String toString() { return "Circle radius: " + radius + ", " + super.toString(); // 调用父类的toString() } }

三、方法重写（Override）与重载（Overload）

1. 方法重写（Override）

• 定义：子类重新实现父类的非private、非static、非final方法，方法签名必须完全一致。

  1 2 3 4 5 6 7

  public class GeometricObject { public abstract double getArea(); // 抽象方法，子类必须重写 } public class Circle { @Override // 注解确保正确重写 public double getArea() { return Math.PI * radius * radius; } }

• 应用场景：多态的基础（后文会讲）。

2. 方法重载（Overload）

• 定义：同一类中，方法名相同但参数列表不同（类型、数量、顺序），与返回值无关。

  1 2 3 4

  public class Calculator { public int add(int a, int b) { return a + b; } // 重载1 public double add(double a, double b) { return a + b; } // 重载2 }

3. 对比表格

练习1：判断以下代码是重写还是重载？

1
2
3

class A { public void m(int x) { } }
class B extends A { public void m(double x) { } } // 重载（参数类型不同）
class C extends A { public void m(int x) { } } // 重写（方法签名相同）

四、多态（Polymorphism）与动态绑定（Dynamic Binding）

1. 多态的本质

• 定义：父类引用可以指向子类对象，运行时根据实际对象类型调用方法。

  1 2	GeometricObject obj1 = new Circle(5); // 父类引用指向子类对象 GeometricObject obj2 = new Rectangle(5, 3);

• 优势：代码通用性强，如displayGeometricObject方法可接收任何GeometricObject子类对象。

  1 2 3

  public static void displayGeometricObject(GeometricObject obj) { System.out.println(obj.getArea()); // 动态绑定：根据obj实际类型调用Circle或Rectangle的getArea() }

2. 动态绑定机制

• 过程：JVM在运行时根据对象的实际类型（而非引用类型）确定调用哪个方法。
  • 若对象是Circle，调用Circle的getArea()；若是Rectangle，调用Rectangle的getArea()。
• 示例：

  1 2 3 4 5 6

  class Person { public String toString() { return "Person"; } } class Student extends Person { @Override public String toString() { return "Student"; } } public static void main(String[] args) { Person p = new Student(); // 父类引用指向子类对象 System.out.println(p.toString()); // 输出：Student（动态绑定） }

五、类型转换与instanceof操作符

1. 向上转型（Upcasting）

• 自动转换：子类对象 → 父类引用（安全，因为子类是父类的一种）。

  1 2	Circle circle = new Circle(5); GeometricObject geo = circle; // 向上转型（自动）

2. 向下转型（Downcasting）

• 强制转换：父类引用 → 子类对象（需确保引用实际指向子类对象，否则抛出ClassCastException）。

  1 2	GeometricObject geo = new Circle(5); Circle circle = (Circle) geo; // 向下转型（安全，因为实际是Circle对象）

3. instanceof操作符

• 作用：在向下转型前检查对象类型，避免异常。

  1 2 3 4

  if (geo instanceof Circle) { // 先判断是否是Circle类型 Circle circle = (Circle) geo; System.out.println(circle.getRadius()); }

六、Object类的常用方法

1. toString()方法

• 默认实现：返回类名@哈希码（如Circle@123456），无实际意义。
• 重写建议：返回对象属性的字符串表示。

  1 2 3 4

  @Override public String toString() { return "Circle[radius=" + radius + ", color=" + getColor() + "]"; }

2. equals()方法

• 默认实现：比较对象引用地址（this == obj），而非内容。
• 重写逻辑：
  1. 判断是否为同一对象（this == obj）。
  2. 判断obj是否为null或类型是否匹配（用instanceof）。
  3. 比较关键属性是否相等。

     1 2 3 4 5 6 7

     @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null || getClass() != obj.getClass()) return false; Circle other = (Circle) obj; return Double.compare(other.radius, radius) == 0; }

七、容器类：ArrayList与自定义栈（MyStack）

1. ArrayList的优势

• 动态扩容：无需指定初始大小，自动扩展。
• 泛型支持：避免类型转换警告，如ArrayList<Circle>只能存储Circle对象。

  1 2 3

  ArrayList<Circle> circles = new ArrayList<>(); circles.add(new Circle(2)); Circle c = circles.get(0); // 无需强制转换

2. 自定义栈（MyStack）

• 底层实现：用ArrayList存储元素，实现栈的push（入栈）、pop（出栈）等操作。

  1 2 3 4 5

  public class MyStack { private ArrayList<Object> list = new ArrayList<>(); public void push(Object o) { list.add(o); } // 入栈：添加到末尾 public Object pop() { return list.remove(list.size() - 1); } // 出栈：移除末尾元素 }

八、访问修饰符：protected与final

1. protected修饰符

• 作用：允许同一包内的类和子类（即使不同包）访问。
• 对比表格：

2. final修饰符

• final变量：常量，不可修改（如final static double PI = 3.14;）。
• final方法：不可被重写（防止子类修改核心逻辑）。
• final类：不可被继承（如String类）。

九、课堂测验与巩固

测验1：继承与构造函数

1
2
3

class A { public A() { System.out.print("A"); } public A(int x) { System.out.print("B"); } }
class B extends A { public B() { super(1); } }
new B(); // 输出？

答案：B（子类构造函数调用super(1)，执行父类A(int x)构造函数）。

测验2：重写与多态

1
2
3
4
5
6

class Animal { public void speak() { System.out.println("Animal"); } }
class Dog extends Animal { @Override public void speak() { System.out.println("Woof"); } }
public static void main(String[] args) {
    Animal a = new Dog();
    a.speak(); // 输出？
}

答案：Woof（动态绑定，调用Dog的speak()）。

Lecture 3 - Abstract Classes and Interfaces

一、核心知识点总结

1. 抽象类（Abstract Classes）

• 定义：用 abstract 修饰的类，包含抽象方法（abstract 方法，无方法体）和具体方法。
  • 例：GeometricObject 是抽象类，包含 getArea()、getPerimeter() 抽象方法。
• 特点：
  • 不能直接实例化（不能用 new 创建对象），但可作为父类被继承。
  • 非抽象子类必须实现父类的所有抽象方法。
  • 抽象类可包含构造方法，供子类通过 super() 调用。
• 用途：定义通用模板，强制子类实现特定方法（如几何图形的面积计算）。

2. 接口（Interfaces）

• 定义：用 interface 声明，仅包含 抽象方法 和 常量（默认 public static final）。
  • 例：Edible 接口定义 howToEat() 方法，Comparable 接口定义 compareTo() 方法。
• 特点：
  • 类通过 implements 实现接口，需重写所有接口方法（默认 public abstract）。
  • 支持多继承（一个类可实现多个接口），弥补Java单继承限制。
  • 接口可继承其他接口（interface A extends B, C）。
• 用途：定义行为规范（如“可比较”“可克隆”），解耦实现与接口。

3. 关键接口示例

• Comparable 接口：
  • 用于对象排序（如 Arrays.sort()），需实现 compareTo(Object o) 方法。
  • 例：自定义 ComparableRectangle 类，通过面积比较大小。
• Cloneable 接口：
  • 标记接口（无方法），允许对象通过 clone() 方法克隆。
  • 注意：Object.clone() 是浅拷贝，深拷贝需手动重写 clone()。

4. 抽象类 vs. 接口

5. 包装类（Wrapper Classes）

• 作用：将基本数据类型（如 int、double）封装为对象，便于集合类使用。
• 常见类：Integer、Double、Boolean 等，均继承自 Number 类。
• 特性：
  • 不可变（对象创建后值不可改）。
  • 支持自动装箱/拆箱（JDK 1.5+）：

    1 2	Integer num = 10; // 自动装箱（int → Integer） int n = num; // 自动拆箱（Integer → int）

• 常用方法：
  • 转换：parseInt(String s)、doubleValue()。
  • 比较：compareTo()（实现 Comparable 接口）。

6. 大数类（BigInteger & BigDecimal）

• 用途：处理超出基本类型范围的大整数（BigInteger）或高精度小数（BigDecimal）。
• 特点：
  • 不可变，方法返回新对象（如 add()、multiply()）。
  • BigDecimal 需指定精度和舍入模式：

    1	BigDecimal result = a.divide(b, 20, BigDecimal.ROUND_HALF_UP);

7. 案例：Rational类（有理数）

• 功能：实现有理数的加减乘除、比较和类型转换（继承 Number 接口）。
• 关键点：
  • 重写 compareTo() 实现比较逻辑。
  • 使用 gcd() 方法约分，确保分母为正。

二、常见问题与解答

1. Q：抽象类可以没有抽象方法吗？
   A：可以。抽象类的存在意义是禁止实例化，即使没有抽象方法，也可作为基类强制子类继承。
2. Q：接口能继承类吗？
   A：不能。接口只能继承其他接口（interface A extends B），类通过 implements 实现接口。
3. Q：为什么包装类是不可变的？
   A：为保证线程安全和哈希值稳定（如作为 HashMap 键时），包装类的内部状态不可修改。
4. Q：深拷贝和浅拷贝的实现区别？
   A：浅拷贝直接复制引用（super.clone()），深拷贝需手动创建新对象并复制引用字段（如 h.whenBuilt = (Date)whenBuilt.clone();）。

Lecture 4 - Generics

一、泛型基础：为何需要泛型？

核心作用

泛型能够将类型检查的阶段提前到编译期，避免在运行时出现类型错误，同时还能实现代码的复用。下面通过一个示例来对比说明：

• 无泛型（存在风险）

  1 2 3

  ArrayList list = new ArrayList(); list.add("1"); // 向列表中添加字符串 Integer i = (Integer) list.get(0); // 运行时会抛出 ClassCastException 异常

  存在的问题：在运行时才能发现类型不匹配的问题。
• 有泛型（更安全）

  1 2 3 4

  ArrayList<Integer> list = new ArrayList<>(); // JDK 1.7 及之后版本支持钻石语法 list.add("1"); // 编译时就会报错，提示类型不匹配 list.add(1); // 正确操作，自动装箱 Integer i = list.get(0); // 无需进行强制类型转换

  优势体现：在编译阶段就能捕获错误，代码的可读性也更强。

关键概念

泛型的本质是对类型进行参数化。就像定义一个“模板”，在使用的时候再指定具体的类型。例如：

• 泛型类模板：class GenericStack<E>
  • E是类型参数（也被称为类型变量），在创建实例时，需要用具体的类型（如Integer、String）来替换它。
• 实例化方式：GenericStack<String> stack = new GenericStack<>();

二、动手实践：定义泛型类与接口

案例：自定义泛型栈（GenericStack）

1
2
3
4
5
6
7

public class GenericStack<E> {
    private ArrayList<E> list = new ArrayList<>(); // 使用 E 作为元素类型

    public void push(E o) { list.add(o); } // 只能添加 E 类型的元素
    public E pop() { return list.remove(list.size() - 1); } // 返回 E 类型的元素
    // 其他方法如 peek()、isEmpty() 等的返回类型或参数类型均为 E
}

使用方式：

1
2
3
4

GenericStack<Integer> intStack = new GenericStack<>();
intStack.push(10); // 自动装箱为 Integer
intStack.push(20);
System.out.println(intStack.pop()); // 输出：20（类型为 Integer）

练习 1

尝试定义一个泛型队列GenericQueue<E>，要求包含enqueue(E element)（入队）和dequeue()（出队）方法。

三、深入探究：泛型方法与有界类型

1. 泛型方法

泛型方法可以独立于类而存在，在方法名前使用<T>来声明类型参数。

1
2
3
4
5
6
7
8

public static <E> void printArray(E[] array) { // 适用于任何类型的数组
    for (E element : array) {
        System.out.print(element + " ");
    }
}
// 使用示例
Integer[] intArray = {1, 2, 3};
printArray(intArray); // 输出：1 2 3

2. 有界类型参数（Bounded Type Parameters）

通过extends关键字来限制类型参数的范围，例如<E extends Comparable<E>>表示E必须实现Comparable接口。
案例：排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static <E extends Comparable<E>> void sort(E[] array) {
    // 使用 compareTo() 方法进行比较排序
    for (int i = 0; i < array.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j].compareTo(array[minIndex]) < 0) {
                minIndex = j;
            }
        }
        // 交换元素
        E temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}
// 适用类型：Integer、String（因为它们都实现了 Comparable 接口）

练习 2

定义一个泛型方法max(E a, E b)，用于返回两个可比较对象中的最大值，要求使用有界类型参数。

四、通配符（Wildcards）：解决类型兼容性问题

通配符用于处理泛型类型之间的继承关系，常见的有以下三种：

案例：计算栈中数字的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13

public static double max(GenericStack<? extends Number> stack) { // 接受 Number 及其子类（如 Integer、Double）
    double max = stack.pop().doubleValue();
    while (!stack.isEmpty()) {
        double value = stack.pop().doubleValue();
        if (value > max) max = value;
    }
    return max;
}
// 使用示例
GenericStack<Integer> intStack = new GenericStack<>();
intStack.push(10);
intStack.push(20);
System.out.println(max(intStack)); // 输出：20.0

注意事项

• 父子类型关系：GenericStack<Integer>不是GenericStack<Number>的子类，但GenericStack<Integer>是GenericStack<? extends Number>的子类。
• 写入限制：使用? extends T时，无法向集合中写入元素（除了null），因为类型不确定；使用? super T时，允许写入T及其子类元素。

练习 3

思考以下代码是否能编译通过，并解释原因：

1
2
3

GenericStack<? extends Number> stack = new GenericStack<Integer>();
stack.push(new Integer(1)); // 能否编译通过？NO
stack.push(new Number(1) {}); // 能否编译通过？NO

五、类型擦除（Type Erasure）：Java 泛型的实现原理

核心机制

• 编译器会在编译阶段移除泛型类型信息，将其替换为原始类型（如E替换为Object）。
• 因此，泛型类型在运行时并不存在，例如：

  1	System.out.println(new GenericStack<Integer>().getClass() == new GenericStack<String>().getClass()); // 输出：true

  这是因为擦除后两者的类型都是GenericStack（原始类型）。

限制条件

由于类型擦除的存在，泛型有以下限制：

1. 不能实例化泛型类型：new E()是不允许的，因为运行时E会被擦除为Object，无法确定具体类型。
2. 静态成员不能使用类型参数：静态变量或方法属于类级别，而类型参数是实例级别的。
3. 数组操作受限：不能创建泛型数组，如E[] array = new E[10];，但可以使用ArrayList<E>。

六、实战应用：设计泛型矩阵类

文档中提供了GenericMatrix<E>的示例，它是一个抽象类，通过泛型实现了矩阵的加法和乘法运算，具体的元素操作由子类（如IntegerMatrix、RationalMatrix）来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 抽象泛型矩阵类
public abstract class GenericMatrix<E extends Number> {
    protected abstract E add(E a, E b); // 元素加法
    protected abstract E multiply(E a, E b); // 元素乘法
    protected abstract E zero(); // 返回零值

    public E[][] addMatrix(E[][] m1, E[][] m2) {
        // 实现矩阵加法，调用 add() 方法
    }
}

// 整数矩阵子类
public class IntegerMatrix extends GenericMatrix<Integer> {
    @Override
    protected Integer add(Integer a, Integer b) { return a + b; }
    @Override
    protected Integer multiply(Integer a, Integer b) { return a * b; }
    @Override
    protected Integer zero() { return 0; }
}

练习 4

尝试为GenericMatrix添加一个RationalMatrix子类，用于处理有理数矩阵的运算（有理数类Rational已在文档中定义）。

七、常见问题与最佳实践

1. 原始类型（Raw Types）：为了兼容旧代码，可以使用原始类型（如ArrayList），但这会失去泛型的类型安全保障，不建议在新代码中使用。
2. 优先使用泛型集合：避免使用ArrayList，而应使用ArrayList<String>等参数化类型。
3. 合理使用通配符：在需要处理类型层次结构时，使用通配符来提高代码的灵活性。

总结：知识图谱

1
2
3
4
5
6
7

泛型
├─ 核心优势：编译时类型检查、代码复用
├─ 基础语法：泛型类/接口（GenericStack<E>）、泛型方法（<T> void print(T[] arr)）
├─ 类型参数：无界类型（E）、有界类型（E extends Comparable<E>）
├─ 通配符：?、? extends T、? super T
├─ 实现原理：类型擦除、原始类型
└─ 实战：自定义泛型数据结构、泛型算法（排序、矩阵运算）

Lecture 5 - Lists, Stacks, Queues, and Priority Queues

第一部分：Java集合框架概述

1. 集合框架的核心结构

Java集合框架（Java Collections Framework, JCF）是一组用于存储和操作数据的API，包含接口、抽象类和具体类。

• 接口：定义操作规范（如Collection、List、Queue）。
• 抽象类：提供部分实现（如AbstractCollection、AbstractList）。
• 具体类：实现具体数据结构（如ArrayList、LinkedList、PriorityQueue）。

2. 核心接口分类

• 单元素集合（Collection）：存储独立元素，分为：
  • 有序列表（List）：允许重复，有序（如ArrayList、LinkedList）。
  • 集合（Set）：不允许重复（如HashSet、TreeSet）。
  • 队列（Queue）：先进先出（FIFO）或优先级排序（如PriorityQueue）。
• 键值对集合（Map）：存储键值对（如HashMap、TreeMap）。

第二部分：列表（List）

1. List接口特点

• 有序性：元素按插入顺序存储，可通过索引访问。
• 允许重复：可存储相同元素。
• 核心方法：
  • add(index, element)：在指定位置插入元素。
  • get(index)：获取指定索引的元素。
  • remove(index)：删除指定索引的元素。
  • size()：获取元素个数。

2. 实现类：ArrayList vs. LinkedList

3. 示例代码：List基本操作

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

import java.util.ArrayList;
import java.util.List;

public class ListDemo {
    public static void main(String[] args) {
        // 创建ArrayList
        List<String> list = new ArrayList<>();
        
        // 添加元素
        list.add("Apple");
        list.add("Banana");
        list.add(1, "Cherry"); // 在索引1处插入元素
        
        // 遍历列表
        System.out.println("遍历列表（for-each）:");
        for (String item : list) {
            System.out.print(item + " "); // 输出：Apple Cherry Banana
        }
        
        // 删除元素
        list.remove("Banana");
        System.out.println("\n删除后的列表: " + list); // 输出：[Apple, Cherry]
        
        // 获取元素
        String firstItem = list.get(0);
        System.out.println("第一个元素: " + firstItem); // 输出：Apple
    }
}

第三部分：栈（Stack）

1. 栈的特点

• 后进先出（LIFO）：最后插入的元素最先取出。
• 核心方法：
  • push(element)：压入元素（栈顶）。
  • pop()：弹出栈顶元素（并删除）。
  • peek()：查看栈顶元素（不删除）。
  • empty()：判断栈是否为空。

2. 示例代码：栈的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        
        // 压入元素
        stack.push("Java");
        stack.push("Python");
        stack.push("C++");
        
        // 弹出元素
        System.out.println("弹出元素: " + stack.pop()); // 输出：C++
        System.out.println("栈顶元素: " + stack.peek()); // 输出：Python
        
        // 判断栈是否为空
        System.out.println("栈是否为空: " + stack.empty()); // 输出：false
    }
}

第四部分：队列（Queue）和优先队列（PriorityQueue）

1. 队列（Queue）

• 先进先出（FIFO）：元素从队尾插入，队头取出。
• 核心方法：
  • offer(element)：添加元素到队尾（推荐用此方法，避免异常）。
  • poll()：取出队头元素（队列为空时返回null）。
  • peek()：查看队头元素（队列为空时返回null）。

2. 优先队列（PriorityQueue）

• 按优先级排序：元素按自然顺序（Comparable）或自定义顺序（Comparator）排列，优先级高的元素先取出。
• 示例代码：优先队列排序

  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

  import java.util.PriorityQueue; public class PriorityQueueDemo { public static void main(String[] args) { // 默认按自然顺序（字符串字典序） PriorityQueue<String> queue = new PriorityQueue<>(); queue.offer("Oklahoma"); queue.offer("Indiana"); queue.offer("Georgia"); System.out.println("默认排序（字典序）:"); while (!queue.isEmpty()) { System.out.print(queue.poll() + " "); // 输出：Georgia Indiana Oklahoma } // 自定义排序（逆序） PriorityQueue<String> reverseQueue = new PriorityQueue<>( (a, b) -> b.compareTo(a) // 匿名内部类实现Comparator ); reverseQueue.offer("Oklahoma"); reverseQueue.offer("Indiana"); reverseQueue.offer("Georgia"); System.out.println("\n逆序排序:"); while (!reverseQueue.isEmpty()) { System.out.print(reverseQueue.poll() + " "); // 输出：Oklahoma Indiana Georgia } } }

第五部分：集合工具类（Collections）

Collections类提供大量静态方法，用于操作集合：

• 排序：sort(list)（自然顺序）、sort(list, comparator)（自定义顺序）。
• 搜索：binarySearch(list, key)（需先排序）。
• 其他：reverse(list)（反转列表）、shuffle(list)（打乱顺序）、frequency(collection, element)（统计元素出现次数）。

示例代码：排序与搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9));
        
        // 排序（自然顺序）
        Collections.sort(list);
        System.out.println("排序后: " + list); // 输出：[1, 1, 3, 4, 5, 9]
        
        // 搜索元素
        int index = Collections.binarySearch(list, 4);
        System.out.println("元素4的索引: " + index); // 输出：3
        
        // 反转列表
        Collections.reverse(list);
        System.out.println("反转后: " + list); // 输出：[9, 5, 4, 3, 1, 1]
    }
}

第六部分：练习与思考

练习1：List性能对比

编写代码对比ArrayList和LinkedList在中间插入元素的性能差异，思考为什么会有这样的结果。

练习2：栈的应用

使用Stack实现一个简单的计算器，计算后缀表达式（如"3 4 + 5 *"）。
![[Pasted image 20250604174439.png]]
等价于中缀表达式：(3 + 4) * 5 = 35

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

import java.util.Stack;

public class PostfixCalculator {

    public static int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = expression.split(" ");

        for (String token : tokens) {
            if (isOperator(token)) {
                int b = stack.pop(); // 注意：先出栈的是右操作数
                int a = stack.pop();
                int result = applyOperator(a, b, token);
                stack.push(result);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }

    private static boolean isOperator(String token) {
        return "+-*/".contains(token);
    }

    private static int applyOperator(int a, int b, String operator) {
        switch (operator) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b; // 假设输入合法，b ≠ 0
            default: throw new IllegalArgumentException("未知操作符: " + operator);
        }
    }

    public static void main(String[] args) {
        String expr = "3 4 + 5 *";
        int result = evaluatePostfix(expr);
        System.out.println("结果: " + result); // 输出: 35
    }
}

练习3：优先队列自定义排序

定义一个Student类（包含姓名和成绩），使用PriorityQueue按成绩从高到低排序学生。

Lecture 6 - Sets and Maps

第一部分：Set（集合）

1. Set 基础概念

• 定义：Set 是一种不允许存储重复元素的集合，继承自 Collection 接口。
• 核心特性：
  • 无序性：元素存储顺序不确定（除了 LinkedHashSet 和 TreeSet）。
  • 唯一性：通过 equals() 方法判断元素是否重复，确保无重复元素。
• 实现类：
  • **HashSet**：基于哈希表实现，无序，查询速度快。
  • **LinkedHashSet**：继承自 HashSet，通过链表维护插入顺序，遍历时按插入顺序输出。
  • **TreeSet**：基于红黑树实现，元素有序（自然排序或自定义排序）。

2. HashSet 详解

2.1 创建 HashSet

1
2
3
4
5
6
7
8
9

// 空 HashSet
Set<String> set1 = new HashSet<>();

// 从现有集合创建（如 List）
List<String> list = Arrays.asList("Apple", "Banana");
Set<String> set2 = new HashSet<>(list);

// 指定初始容量和负载因子（默认容量16，负载因子0.75）
Set<Integer> set3 = new HashSet<>(20, 0.8f);

2.2 添加元素（add()）

• 唯一性验证：通过 hashCode() 和 equals() 判断重复。
  • 示例：向 HashSet 中添加重复元素（字符串会自动去重）。

    1 2 3 4 5 6

    Set<String> cities = new HashSet<>(); cities.add("London"); cities.add("Paris"); cities.add("New York"); cities.add("New York"); // 重复，不会被添加 System.out.println(cities); // 输出：[London, Paris, New York]（顺序不确定）

2.3 遍历 HashSet

• 增强 for 循环：

  1 2 3

  for (String city : cities) { System.out.print(city + " "); }

• forEach() 方法（Lambda 表达式）：

  1	cities.forEach(city -> System.out.print(city.toLowerCase() + " "));

2.4 常用方法

3. LinkedHashSet 详解

• 特点：保持元素的插入顺序，遍历时按插入顺序输出。
• 示例：

  1 2 3 4 5

  Set<String> linkedSet = new LinkedHashSet<>(); linkedSet.add("A"); linkedSet.add("B"); linkedSet.add("C"); System.out.println(linkedSet); // 输出：[A, B, C]（顺序与插入一致）

4. TreeSet 详解

• 特点：元素自动排序，支持自然排序（Comparable）或自定义排序（Comparator）。
• 示例：自然排序（字符串按字母顺序）

  1 2 3 4 5

  Set<String> treeSet = new TreeSet<>(); treeSet.add("Z"); treeSet.add("A"); treeSet.add("B"); System.out.println(treeSet); // 输出：[A, B, Z]（升序排列）

• 自定义排序（Comparator）：

  1 2 3 4 5 6

  // 按字符串长度降序排列 Set<String> treeSet = new TreeSet<>(Comparator.comparingInt(String::length).reversed()); treeSet.add("Apple"); // 5字母 treeSet.add("Banana"); // 6字母 treeSet.add("Cat"); // 3字母 System.out.println(treeSet); // 输出：[Banana, Apple, Cat]

5. Set vs List 性能对比

• 场景总结：
  • Set：适合存储唯一元素，查询效率高（尤其是 HashSet）。
  • List：适合需要索引访问的场景（如 ArrayList、LinkedList）。
• 性能测试示例（判断元素是否存在）：

  1 2 3 4 5 6

  // HashSet 耗时约 10-50ms long time = System.currentTimeMillis(); for (int i = 0; i < 100000; i++) { set.contains(i); } System.out.println("HashSet耗时：" + (System.currentTimeMillis() - time) + "ms");

第二部分：Map（映射）

1. Map 基础概念

• 定义：存储键值对（key-value）的集合，通过 key 快速查找 value。
• 核心特性：
  • 键唯一性：key 不能重复（通过 equals() 判断）。
  • 值可重复：value 可以重复。
• 实现类：
  • **HashMap**：无序，基于哈希表，查询速度快。
  • **LinkedHashMap**：保持插入顺序或访问顺序。
  • **TreeMap**：按键排序（自然排序或自定义排序）。

2. HashMap 详解

2.1 创建 HashMap

1
2
3
4
5
6
7
8
9
10
11

// 空 HashMap
Map<String, Integer> map1 = new HashMap<>();

// 初始化键值对
Map<String, Integer> map2 = new HashMap<>() {{
    put("Apple", 10);
    put("Banana", 20);
}};

// 从现有 Map 创建
Map<String, Integer> map3 = new HashMap<>(map2);

2.2 操作方法

• 添加/更新键值对：put(key, value)（若 key 已存在，覆盖原有 value）。

  1 2	map1.put("Orange", 30); // 添加 map1.put("Apple", 15); // 更新 Apple 的值为 15

• 获取值：get(key)（若 key 不存在，返回 null）。

  1	int value = map1.get("Apple"); // value = 15

• 遍历键值对：

  1 2 3 4 5 6 7 8 9 10 11 12

  // 遍历所有键 for (String key : map1.keySet()) { System.out.println("Key: " + key + ", Value: " + map1.get(key)); } // 遍历所有键值对（推荐） for (Map.Entry<String, Integer> entry : map1.entrySet()) { System.out.println(entry.getKey() + " -> " + entry.getValue()); } // 使用 forEach() map1.forEach((key, value) -> System.out.println(key + ": " + value));

2.3 常用方法

3. LinkedHashMap 详解

• 特点：
  • 插入顺序：默认按插入顺序存储和遍历。
  • 访问顺序：设置 accessOrder = true 时，按最后访问顺序排序（最近最少访问 → 最近最多访问）。
• 示例：访问顺序

  1 2 3 4 5

  Map<String, Integer> linkedMap = new LinkedHashMap<>(16, 0.75f, true); linkedMap.put("A", 1); linkedMap.put("B", 2); linkedMap.get("A"); // 访问键 "A" System.out.println(linkedMap); // 输出：[B, A]（"A" 被移动到最后）

4. TreeMap 详解

• 特点：按键的自然排序或自定义排序（Comparator）排列。
• 示例：自然排序（字符串按字母顺序）

  1 2 3 4 5

  Map<String, Integer> treeMap = new TreeMap<>(); treeMap.put("Z", 26); treeMap.put("A", 1); treeMap.put("B", 2); System.out.println(treeMap); // 输出：{A=1, B=2, Z=26}（键升序）

• 自定义排序（按值降序）：

  1 2 3 4 5

  Map<String, Integer> treeMap = new TreeMap<>(Comparator.comparingInt(Map.Entry::getValue).reversed()); treeMap.put("Apple", 15); treeMap.put("Banana", 20); treeMap.put("Cherry", 10); System.out.println(treeMap); // 输出：{Banana=20, Apple=15, Cherry=10}（值降序）

第三部分：关键练习与注意事项

1. 练习建议

1. Set 练习：
   • 创建一个 HashSet，存储自定义对象 Person（包含姓名和年龄），观察去重效果。若去重失败，重写 equals() 和 hashCode() 方法。
   • 使用 TreeSet 对整数列表进行排序，尝试自定义排序规则（如降序）。
2. Map 练习：
   • 创建一个 HashMap，统计字符串中每个字符的出现次数（例如：”abracadabra” → a:5, b:2, r:2, c:1, d:1）。
   • 使用 LinkedHashMap 实现一个简单的LRU缓存（最近最少使用），设置 accessOrder = true，当容量超过限制时删除最旧的元素。

2. 注意事项

• Set 去重：自定义对象必须重写 equals() 和 hashCode()，否则 HashSet 无法正确去重。
• Map 键的选择：建议使用不可变对象（如 String、Integer）作为键，避免键值改变导致哈希冲突。
• 性能优化：
  • HashSet/HashMap 适合高频查询和插入。
  • TreeSet/TreeMap 适合需要排序的场景，但性能略低于哈希结构。

总结：核心知识点速查表

Lecture 8 - Developing Efficient Algorithms

第一讲：算法效率与大O表示法

1. 为什么需要分析算法效率？

• 问题：同一任务可能有不同算法（如线性搜索 vs 二分搜索），如何比较它们的效率？
• 解决方案：用大O表示法（Big O Notation）衡量算法的时间复杂度，关注输入规模增长时的性能变化趋势。

2. 大O表示法的核心思想

• 忽略常数和低阶项：例如，$100n$和$n/2$的时间复杂度均为$O(n)$。
• 关注最坏情况：分析算法在最坏输入下的表现（因为平均情况通常与最坏情况同阶）。

3. 常见时间复杂度排序

$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n)$

• 示例：
  • 常数时间$O(1)$：数组索引访问。
  • 线性时间$O(n)$：线性搜索。
  • 对数时间$O(\log n)$：二分搜索。
  • 平方时间$O(n^2)$：选择排序、插入排序。

第二讲：常见算法的时间复杂度分析

1. 线性搜索 vs 二分搜索

• 线性搜索：

  • 代码：

    1 2 3 4 5 6

    public static int linearSearch(int[] list, int key) { for (int i = 0; i < list.length; i++) { if (list[i] == key) return i; } return -1; }

  • 复杂度：$O(n)$（最坏情况需遍历所有元素）。

• 二分搜索：

  • 条件：数组必须有序。
  • 代码：

    1 2 3 4 5 6 7 8 9 10

    public static int binarySearch(int[] list, int key) { int low = 0, high = list.length - 1; while (low <= high) { int mid = (low + high) / 2; if (key < list[mid]) high = mid - 1; else if (key == list[mid]) return mid; else low = mid + 1; } return -1; }

  • 复杂度：$O(\log n)$（每次将问题规模减半）。

2. 选择排序

• 思想：每次从未排序部分选择最小元素，与未排序部分的第一个元素交换。
• 代码：

  1 2 3 4 5 6 7 8 9 10 11

  public static void selectionSort(double[] list) { for (int i = 0; i < list.length; i++) { int minIndex = i; for (int j = i + 1; j < list.length; j++) { if (list[j] < list[minIndex]) minIndex = j; } double temp = list[i]; list[i] = list[minIndex]; list[minIndex] = temp; } }

• 复杂度：$O(n^2)$（双重循环）。

3. 插入排序

• 思想：将未排序元素逐个插入已排序部分的正确位置。
• 代码：

  1 2 3 4 5 6 7 8 9 10 11

  public static void insertionSort(int[] list) { for (int i = 1; i < list.length; i++) { int current = list[i]; int j = i - 1; while (j >= 0 && list[j] > current) { list[j + 1] = list[j]; j--; } list[j + 1] = current; } }

• 复杂度：$O(n^2)$（最坏情况下需移动所有元素）。

第三讲：递归与动态规划

1. 斐波那契数列的递归实现

• 递归公式：$fib(n) = fib(n-1) + fib(n-2)$。
• 代码：

  1 2 3 4

  public static int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }

• 复杂度：$O(2^n)$（重复计算大量子问题）。

2. 动态规划优化斐波那契数列

• 思想：用数组存储已计算的子问题结果，避免重复计算。
• 代码：

  1 2 3 4 5 6 7 8 9 10

  public static int fib(int n) { if (n <= 1) return n; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }

• 复杂度：$O(n)$（线性时间）。

第四讲：分治法与回溯法

1. 最近点对问题（分治法）

• 步骤：
  1. 将点按x坐标排序。
  2. 递归求解左右两半的最近点对。
  3. 合并时检查中间带内的点对。
• 复杂度：$O(n \log n)$（排序和递归合并）。

2. 八皇后问题（回溯法）

• 思想：逐行放置皇后，若当前位置冲突则回溯到上一行。
• 代码关键逻辑：

  1 2 3 4 5 6 7 8

  private boolean isValid(int row, int col) { for (int i = 0; i < row; i++) { if (queens[i] == col || Math.abs(row - i) == Math.abs(col - queens[i])) { return false; } } return true; }

• 复杂度：$O(n!)$（理论上最坏情况，但通过剪枝优化后实际效率更高）。

第五讲：其他高效算法

1. 欧几里得算法（求GCD）

• 思想：利用$gcd(m, n) = gcd(n, m % n)$。
• 代码：

  1 2 3 4

  public static int gcd(int m, int n) { if (n == 0) return m; return gcd(n, m % n); }

• 复杂度：$O(\log n)$。

2. 筛法求素数（Sieve of Eratosthenes）

• 思想：标记非素数，从2开始筛去所有倍数。
• 代码：

  1 2 3 4 5 6 7 8 9 10 11 12 13

  public static boolean[] sieve(int n) { boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } return isPrime; }

• 复杂度：$O(n \log \log n)$。

总结与练习

1. 大O表示法：分析算法复杂度的核心工具，关注主导项。
2. 排序算法：选择排序和插入排序均为$O(n^2)$，适合小规模数据。
3. 递归与动态规划：动态规划通过存储子问题结果优化递归的指数复杂度。
4. 分治与回溯：分治法将问题分解为独立子问题，回溯法通过剪枝避免无效搜索。

练习题：

1. 分析以下代码的时间复杂度：

   1 2 3 4 5 6 7

   public static void printPairs(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { System.out.println(arr[i] + ", " + arr[j]); } } }

答案：

这段代码的时间复杂度为$O(n^2)$（$n$为数组长度）。

• 分析过程：
  代码的核心是两层嵌套循环，用于打印数组中所有不重复的元素对（即每个元素对$(arr[i], arr[j])$满足$i < j$）。

1. 外层循环的迭代次数

外层循环的变量$i$从$0$遍历到$arr.length - 1$（共$n$次迭代，$n = arr.length$）。

2. 内层循环的迭代次数

对于外层循环的每一次迭代$i$，内层循环的变量$j$从$i + 1$遍历到$arr.length - 1$。因此：

• 当$i = 0$时，内层循环执行$n - 1$次（$j = 1, 2, …, n-1$）；
• 当$i = 1$时，内层循环执行$n - 2$次（$j = 2, 3, …, n-1$）；
• …
• 当$i = n - 2$时，内层循环执行$1$次（$j = n - 1$）；
• 当$i = n - 1$时，内层循环不执行（$j = n$超出数组范围）。

3. 总操作次数

总操作次数为内层循环所有迭代次数的和：
$\text{总次数} = (n-1) + (n-2) + … + 2 + 1 + 0 = \frac{n(n-1)}{2}$

4. 时间复杂度结论

根据大$O$表示法的规则（忽略低阶项和常数系数），$\frac{n(n-1)}{2}$可简化为$O(n^2)$。
结论：该代码的时间复杂度为$O(n^2)$（平方阶）。

2. 用动态规划实现斐波那契数列，尝试优化空间复杂度。

答案：

动态规划实现斐波那契数列（空间优化版）
斐波那契数列的定义为：
$F(0) = 0,\ F(1) = 1,\ F(n) = F(n-1) + F(n-2)$（$n \geq 2$）
传统动态规划方法需要使用数组存储中间结果（空间复杂度$O(n)$），但通过观察可以发现，计算$F(n)$仅需前两项$F(n-1)$和$F(n-2)$，因此可以用两个变量代替数组，将空间复杂度优化至$O(1)$。

实现代码（Java）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Fibonacci {
    // 动态规划实现，空间复杂度优化为 O(1)
    public static long fibonacci(int n) {
        if (n == 0) return 0;    // 边界条件：F(0) = 0
        if (n == 1) return 1;    // 边界条件：F(1) = 1
        
        long prev1 = 0;  // 保存 F(n-2) 的值（初始为 F(0)）
        long prev2 = 1;  // 保存 F(n-1) 的值（初始为 F(1)）
        
        for (int i = 2; i <= n; i++) {
            long current = prev1 + prev2;  // 计算 F(i) = F(i-1) + F(i-2)
            prev1 = prev2;                 // 迭代更新 F(n-2) 为原 F(n-1)
            prev2 = current;               // 迭代更新 F(n-1) 为当前 F(i)
        }
        return prev2;  // 最终 prev2 即为 F(n)
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.printf("F(%d) = %d%n", i, fibonacci(i));
        }
    }
}

代码说明

1. 边界条件处理：
   当$n = 0$或$n = 1$时，直接返回$0$或$1$，无需计算。
2. 变量初始化：
   • prev1 初始化为$F(0) = 0$（对应$F(n-2)$）；
   • prev2 初始化为$F(1) = 1$（对应$F(n-1)$）。
3. 迭代计算：
   从$i = 2$开始循环至$n$，每次计算当前项$F(i) = prev1 + prev2$，然后更新 prev1 和 prev2 为下一次迭代的前驱值。
4. 空间优化：
   仅用两个变量保存前驱状态，避免了数组存储，空间复杂度从$O(n)$优化至$O(1)$。

复杂度分析

• 时间复杂度：$O(n)$（仅需一次循环遍历到$n$）。
• 空间复杂度：$O(1)$（仅用两个变量保存前驱状态）。

测试结果

运行 main 方法输出前10项斐波那契数：

1
2
3
4
5
6
7
8
9
10
11

F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

Lecture 9 - Sorting

第一部分：排序算法基础

1. 什么是排序算法？

排序算法是将一组数据按特定顺序（如升序、降序）排列的方法。评价标准包括：

• 时间复杂度：算法运行所需时间（如 O(n²)、O(n log n)）。
• 空间复杂度：算法占用的额外内存空间（如原地排序 O(1)）。
• 稳定性：相同元素的相对顺序在排序后是否保持不变。

2. 常见排序算法分类

第二部分：冒泡排序（Bubble Sort）

1. 核心思想

通过反复比较相邻元素，将较大的元素逐步“冒泡”到数组末尾。

• 示例：排序 [4, 3, 2, 1]
  • 第1轮：比较 4↔3、4↔2、4↔1，最大元素4到位，数组变为 [3, 2, 1, 4]。
  • 第2轮：比较 3↔2、3↔1，次大元素3到位，数组变为 [2, 1, 3, 4]。
  • 第3轮：比较 2↔1，数组有序 [1, 2, 3, 4]。