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

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

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

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

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

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

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

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

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

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

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

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

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

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（原始数组被修改）
}

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; // 返回新数组
}

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
}

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; // 未找到
}

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;
    }
}

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

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

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

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;
    }
}

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

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

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

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

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

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

public class Circle {
  private double radius;

  // 访问器（getter）
  public double getRadius() {
      return radius;
  }

  // 修改器（setter）
  public void setRadius(double radius) {
      this.radius = radius; // `this`指代当前对象
  }
}

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

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

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
    }
}

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

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

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

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

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，可变
}

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

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
}

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

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

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

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

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 ...; 
    }
}

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

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

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

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

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

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

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 "

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;
    }
}

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

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;
    }
}

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

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

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

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
}

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) { } } // 重写（方法签名相同）

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

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

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（动态绑定）
}

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

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

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

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

@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&lt;Circle&gt; circles = new ArrayList<>();
circles.add(new Circle(2));
Circle c = circles.get(0); // 无需强制转换

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

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(); // 输出？

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(); // 输出？
}

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

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

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

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

public class GenericStack<E> {
    private ArrayList&lt;E&gt; 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
}

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

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

public static &lt;E extends Comparable<E&gt;> 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 接口）

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&lt;Integer&gt; intStack = new GenericStack<>();
intStack.push(10);
intStack.push(20);
System.out.println(max(intStack)); // 输出：20.0

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

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

// 抽象泛型矩阵类
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; }
}

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

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

public class ListDemo {
    public static void main(String[] args) {
        // 创建ArrayList
        List&lt;String&gt; 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
    }
}

import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {
        Stack&lt;String&gt; 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
    }
}

public static void main(String[] args) {
    // 默认按自然顺序（字符串字典序）
    PriorityQueue&lt;String&gt; 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&lt;String&gt; 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)`（统计元素出现次数）。  

#### **示例代码：排序与搜索**

public static void main(String[] args) {
    List&lt;Integer&gt; 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 *"`）。
![](/pictures/Pasted image 20250604174439.png)
等价于中缀表达式：(3 + 4) * 5 = 35

public static int evaluatePostfix(String expression) {
    Stack&lt;Integer&gt; 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**

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

  

##### **2.3 遍历 HashSet**
- **增强 for 循环**：

  

System.out.print(city + " ");

- **`forEach()` 方法（Lambda 表达式）**：

  

##### **2.4 常用方法**
| 方法          | 说明                          |
|---------------|-------------------------------|
| `remove(obj)` | 删除指定元素                  |
| `contains(obj)` | 检查是否包含元素              |
| `size()`      | 获取元素个数                  |
| `clear()`     | 清空集合                      |


#### **3. LinkedHashSet 详解**
- **特点**：保持元素的**插入顺序**，遍历时按插入顺序输出。
- **示例**：

  

#### **4. TreeSet 详解**
- **特点**：元素**自动排序**，支持自然排序（`Comparable`）或自定义排序（`Comparator`）。
- **示例：自然排序（字符串按字母顺序）**

  

- **自定义排序（Comparator）**：

  

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

  

set.contains(i);

### **第二部分：Map（映射）**

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

#### **2. HashMap 详解**

##### **2.1 创建 HashMap**

put("Apple", 10);
put("Banana", 20);

##### **2.2 操作方法**
- **添加/更新键值对**：`put(key, value)`（若 `key` 已存在，覆盖原有 `value`）。

  

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

  

- **遍历键值对**：

  

System.out.println("Key: " + key + ", Value: " + map1.get(key));

System.out.println(entry.getKey() + " -> " + entry.getValue());

##### **2.3 常用方法**
| 方法              | 说明                          |
|-------------------|-------------------------------|
| `remove(key)`     | 删除指定键的键值对            |
| `containsKey(key)` | 检查是否存在指定键            |
| `size()`          | 获取键值对个数                |
| `keySet()`        | 获取所有键的 `Set`            |
| `values()`        | 获取所有值的 `Collection`     |


#### **3. LinkedHashMap 详解**
- **特点**：
  - **插入顺序**：默认按插入顺序存储和遍历。
  - **访问顺序**：设置 `accessOrder = true` 时，按最后访问顺序排序（最近最少访问 → 最近最多访问）。
- **示例：访问顺序**

  

#### **4. TreeMap 详解**
- **特点**：按键的**自然排序**或**自定义排序**（`Comparator`）排列。
- **示例：自然排序（字符串按字母顺序）**

  

- **自定义排序（按值降序）**：

  

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

#### **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` 适合需要排序的场景，但性能略低于哈希结构。

### **总结：核心知识点速查表**
| 类型       | 实现类       | 顺序性         | 去重机制               | 典型场景                  |
|------------|--------------|----------------|------------------------|---------------------------|
| **Set**    | `HashSet`    | 无序           | `hashCode()` + `equals()` | 快速去重、唯一性校验      |
|            | `LinkedHashSet` | 插入顺序       | 同上                   | 需要保持插入顺序的场景    |
|            | `TreeSet`    | 自然/自定义排序 | `compareTo()`/`Comparator` | 排序集合、范围查询        |
| **Map**    | `HashMap`    | 无序           | `hashCode()` + `equals()` | 键值对快速查找            |
|            | `LinkedHashMap` | 插入/访问顺序  | 同上                   | 日志记录、LRU缓存         |
|            | `TreeMap`    | 自然/自定义排序 | `compareTo()`/`Comparator` | 按键排序的统计、范围查询  |


# 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 二分搜索**
- **线性搜索**：
  - **代码**：

    

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

```

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;
}

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;
    }
}

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;
    }
}

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

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];
}

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;
}

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

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;
}

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]);
        }
    }
}

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));
        }
    }
}

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

public static void bubbleSort(int[] list) {
    boolean needNextPass = true; // 优化：提前终止排序
    for (int k = 1; k < list.length && needNextPass; k++) {
        needNextPass = false;
        for (int i = 0; i < list.length - k; i++) {
            if (list[i] > list[i + 1]) {
                // 交换相邻元素
                int temp = list[i];
                list[i] = list[i + 1];
                list[i + 1] = temp;
                needNextPass = true; // 有交换，需继续下一轮
            }
        }
    }
}

private static void merge(int[] left, int[] right, int[] list) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            list[k++] = left[i++]; // 取较小元素放入结果数组
        } else {
            list[k++] = right[j++];
        }
    }
    // 复制剩余元素
    while (i < left.length) list[k++] = left[i++];
    while (j < right.length) list[k++] = right[j++];
}

private static int partition(int[] list, int first, int last) {
    int pivot = list[first]; // 枢轴
    int low = first + 1, high = last;
    while (high > low) {
        // 找左半部分第一个>枢轴的元素
        while (low <= high && list[low] <= pivot) low++;
        // 找右半部分第一个≤枢轴的元素
        while (low <= high && list[high] > pivot) high--;
        // 交换元素
        if (high > low) swap(list, low, high);
    }
    // 将枢轴放到正确位置
    while (high > first && list[high] >= pivot) high--;
    if (pivot > list[high]) swap(list, first, high);
    return high; // 返回枢轴索引
}

public static void heapSort(int[] array) {
    int n = array.length;
    // 建堆：从最后一个非叶子节点开始下沉
    for (int i = n/2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }
    // 排序：删除根节点，重建堆
    for (int i = n-1; i > 0; i--) {
        swap(array, 0, i); // 根节点（最大值）放到末尾
        heapify(array, i, 0); // 对前i个元素重建堆
    }
}

private static void heapify(int[] array, int n, int i) {
    int largest = i;
    int left = 2*i + 1, right = 2*i + 2;
    if (left < n && array[left] > array[largest]) largest = left;
    if (right < n && array[right] > array[largest]) largest = right;
    if (largest != i) {
        swap(array, i, largest);
        heapify(array, n, largest); // 递归下沉
    }
}

// 无权图邻接表
List&lt;List<Integer&gt;> adjList = new ArrayList<>();
adjList.add(Arrays.asList(1, 2)); // 顶点0的相邻顶点
adjList.add(Arrays.asList(0, 2)); // 顶点1的相邻顶点
adjList.add(Arrays.asList(0, 1)); // 顶点2的相邻顶点

// 有权图邻接表，使用自定义边类
class Edge {
    int to; // 目标顶点
    int weight; // 权重
    public Edge(int to, int weight) { this.to = to; this.weight = weight; }
}

List&lt;List<Edge&gt;> adjList = new ArrayList<>();
adjList.add(Arrays.asList(new Edge(1, 5))); // A(0) → B(1)
adjList.add(Arrays.asList(new Edge(2, 3))); // B(1) → C(2)

boolean[] visited; // 标记是否访问过
void dfs(int v) {
    visited[v] = true; // 标记当前顶点
    for (int neighbor : adjList.get(v)) { // 遍历相邻顶点
        if (!visited[neighbor]) {
            dfs(neighbor); // 递归访问
        }
    }
}

boolean[] visited;
void bfs(int start) {
    Queue&lt;Integer&gt; queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int v = queue.poll(); // 取出队首顶点
        for (int neighbor : adjList.get(v)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor); // 相邻顶点入队
            }
        }
    }
}

邻接表：0: [1, 3], 1: [0, 2], 2: [1], 3: [0, 4], 4: [3]

图：0→1（权重2），0→2（权重5），1→3（权重3），2→3（权重1）
最短路径：0→2→3（总权重5+1=6）

class TreeNode<E> {
    E element;
    TreeNode<E> left;
    TreeNode<E> right;
    public TreeNode(E o) { element = o; }
}

public boolean insert(E element) {
    if (root == null) {
        root = new TreeNode<>(element); // 空树时创建根节点
    } else {
        TreeNode&lt;E&gt; current = root, parent = null;
        while (current != null) {
            parent = current;
            if (element.compareTo(current.element) < 0) {
                current = current.left;
            } else if (element.compareTo(current.element) > 0) {
                current = current.right;
            } else {
                return false; // 重复元素，插入失败
            }
        }
        // 插入到parent的左或右子节点
        if (element.compareTo(parent.element) < 0) {
            parent.left = new TreeNode<>(element);
        } else {
            parent.right = new TreeNode<>(element);
        }
    }
    return true;
}

public boolean search(E element) {
    TreeNode<E> current = root;
    while (current != null) {
        if (element.compareTo(current.element) < 0) {
            current = current.left;
        } else if (element.compareTo(current.element) > 0) {
            current = current.right;
        } else {
            return true; // 找到元素
        }
    }
    return false; // 未找到元素
}

public void inorder() {
    inorder(root); // 从根节点开始
}

private void inorder(TreeNode<E> root) {
    if (root == null) return;
    inorder(root.left);   // 左子树
    System.out.print(root.element + " "); // 根节点
    inorder(root.right);  // 右子树
}

原树结构：       删除后结构：
    20            20
   /  \          /  \
 10   40        40
  \    / \             
  16 30 80        

if (current.left == null) {
    if (parent == null) { // 删除根节点
        root = current.right;
    } else if (current == parent.left) { // 当前节点是左子节点
        parent.left = current.right;
    } else { // 当前节点是右子节点
        parent.right = current.right;
    }
}

原树结构：       替换后结构：
    20            16
   /  \          /  \
 10   40        10   40
  \    / \             
  16 30 80        

else { // 当前节点有左子树
    TreeNode<E> parentOfRightMost = current;
    TreeNode<E> rightMost = current.left;
    // 找到左子树的最右节点
    while (rightMost.right != null) {
        parentOfRightMost = rightMost;
        rightMost = rightMost.right;
    }
    // 用rightMost的值替换current的值
    current.element = rightMost.element;
    // 删除rightMost节点（其无右子树，可能有左子树）
    if (parentOfRightMost == current) { // rightMost是current的左子节点
        parentOfRightMost.left = rightMost.left;
    } else {
        parentOfRightMost.right = rightMost.left;
    }
}

public Iterator<E> iterator() {
    return new InorderIterator();
}

private class InorderIterator implements Iterator<E> {
    private ArrayList&lt;E&gt; list = new ArrayList<>();
    private int current = 0;

    public InorderIterator() {
        inorder(root); // 中序遍历填充list
    }

    private void inorder(TreeNode&lt;E&gt; root) {
        if (root == null) return;
        inorder(root.left);
        list.add(root.element);
        inorder(root.right);
    }

    @Override
    public boolean hasNext() {
        return current < list.size();
    }

    @Override
    public E next() {
        return list.get(current++);
    }

    @Override
    public void remove() {
        BST.this.delete(list.get(current)); // 删除元素
        list.clear(); // 清空列表并重新遍历
        inorder(root);
        current = 0;
    }
}

BST&lt;String&gt; tree = new BST<>();
tree.insert("A");
tree.insert("B");
tree.insert("C");
for (String s : tree) { // 自动调用迭代器
    System.out.print(s.toUpperCase() + " "); // 输出: A B C
}

    12（根）
   /  \
 5     7
/ \   / \
M p  s  i (频率：1,2,4,4)

// 构建Huffman树
public static HuffmanTree buildHuffmanTree(int[] frequencies) {
    PriorityQueue&lt;HuffmanTree&gt; queue = new PriorityQueue<>();
    // 初始化单节点树
    for (int i = 0; i < 256; i++) {
        if (frequencies[i] > 0) {
            queue.offer(new HuffmanTree(frequencies[i], (char) i));
        }
    }
    // 合并树
    while (queue.size() > 1) {
        HuffmanTree t1 = queue.poll();
        HuffmanTree t2 = queue.poll();
        HuffmanTree newTree = new HuffmanTree(t1, t2);
        queue.offer(newTree);
    }
    return queue.poll();
}

// 生成编码
public static String[] getHuffmanCodes(HuffmanTree root) {
    String[] codes = new String[256];
    generateCodes(root.root, "", codes);
    return codes;
}

private static void generateCodes(HuffmanNode node, String code, String[] codes) {
    if (node.left == null && node.right == null) { // 叶子节点
        codes[(int) node.element] = code;
        return;
    }
    generateCodes(node.left, code + "0", codes); // 左分支加0
    generateCodes(node.right, code + "1", codes); // 右分支加1
}

    A(-2)            B(0)
   /                /   \
  B(-1)    →       T1    A(0)
 /  \                 /  \
T1  T2               T2  T3

A(+2)            B(0)
 \                /   \
  B(+1)   →      A(0)  T3
 /  \              /  \
T1  T2            T1  T2

  A(-2)            C(0)
 /                 /   \
B(+1)    →       B(0)  A(0)
 \                /  \
  C(0)          T1  T2
 /  \
T1  T2

  A(+2)            C(0)
   \                 /   \
    B(-1)   →      A(0)  B(0)
   /                /  \
  C(0)            T1  T2
 /  \
T1  T2

private void balancePath(E e) {
    ArrayList&lt;TreeNode<E&gt;> path = path(e); // 获取插入路径
    for (int i = path.size() - 1; i >= 0; i--) {
        AVLTreeNode&lt;E&gt; A = (AVLTreeNode&lt;E&gt;) path.get(i);
        updateHeight(A); // 更新高度
        int bf = balanceFactor(A);
        if (bf == -2) { // 左重
            if (balanceFactor((AVLTreeNode&lt;E&gt;) A.left) <= 0) {
                balanceLL(A, parent); // LL旋转
            } else {
                balanceLR(A, parent); // LR旋转
            }
        } else if (bf == +2) { // 右重
            if (balanceFactor((AVLTreeNode&lt;E&gt;) A.right) >= 0) {
                balanceRR(A, parent); // RR旋转
            } else {
                balanceRL(A, parent); // RL旋转
            }
        }
    }
}

private int hash(int hashCode) {
    hashCode = (hashCode >>> 20) ^ (hashCode >>> 12); // 混合高位
    return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4); // 进一步混合
}