舜桀的算法笔记

这里主要记录我学习算法的历程~

主要参考资料为labuladong的算法笔记

下面开始学习算法吧！

数据结构基础

Java基础

Java标准库数据结构的基本用法

1.数组

int m = 5, n = 10;

// 初始化一个大小为 10 的 int 数组
// 其中的值默认初始化为 0
int[] nums = new int[n];
    
// 初始化一个 m * n 的二维布尔数组
// 其中的元素默认初始化为 false
boolean[][] visited = new boolean[m][n];

2.字符串String

Java 字符串不支持用 [] 直接访问其中的字符，且不能直接修改，需要转化为 char[] 类型才能修改。

String s1 = "hello world";
// 获取 s1[2] 的那个字符
char c = s1.charAt(2);

char[] chars = s1.toCharArray();
chars[1] = 'a';
String s2 = new String(chars);
// 输出：hallo world
System.out.println(s2);

// 注意，一定要使用 equals 方法判断字符串是否相同
if(s1.equals(s2)){
    // s1 和 s2 相同
}else{
    // s1 和 s2 不相同
}

// 字符串可以用加号进行拼接
String s3 = s1 + "!";
// 输出：hello world!
System.out.println(s3);

Java 的字符串不能直接修改，要用 toCharArray 转化成 char[] 的数组进行修改，然后再转换成 String 类型。

另外，虽然字符串支持用 + 进行拼接，但是效率并不高，并不建议在for循环中使用。

如果要进行频繁的字符串拼接，推荐使用 StringBuilder/StringBuffer：

StringBuilder sb = new StringBuilder();

for(char c = 'a'; c <= 'f'; c++){
    sb.append(c);
}

// append 方法支持拼接字符、字符串、数字等类型
sb.append('g').append("hij").append0(123);

String res = sb.toString();
// 输出：abcdefghij123
System.out.println(res);

一定要用字符串的 equals 方法比较两个字符是否相同，不要用 == 比较。

3.动态数组 ArrayList

ArrayList 相当于把Java内置的数组类型做了包装，初始化方法：

// 初始化一个存储 String 类型的动态数组
ArrayList<String> strings = new ArrayList<>();

// 初始化一个存储 int 类型的动态数组
ArrayList<Integer> nums = new ArrayList<>();

常用方法如下：（ E 代表元素类型）：

// 判断数组是否为空
boolean isEmpty()

// 返回数组的元素个数
int size()

// 返回索引 index 的元素
E get(int index)
    
// 在数组尾部添加元素 e
boolean add(E e)

4.双链表 LinkedList

ArrayList 列表底层是数组实现的，而 LinkedList 底层是双链表实现的，初始化方法也是类似的。

// 初始化一个存储 int 类型的双链表
LinkedList<Integer> nums = new LinkedList<>();

// 初始化一个存储 String 类型的双链表
LinkedList<String> strings = new LinkedList<>();

双链表常用方法

// 判断链表是否为空
boolean isEmpty()
    
// 返回链表的元素个数
int size()
    
// 判断链表中是否存在元素 o
boolean contains(Object o)
    
// 在链表尾部添加元素 e
boolean add(E e)
    
// 在链表尾部添加元素 e
void addLast(E e)
    
// 在链表头部添加元素 e
void addFirst(E e)
    
// 删除链表头部第一个元素
E removeFirst()
    
// 删除链表尾部最后一个元素
E removeLast()

和 ArrayList 不同，在 LinkedList 中更多地使用了对于头部和尾部元素地操作，因为底层数据结构为链表，直接操作头尾地元素效率较高。

其中只有 contains 方法的时间复杂度是 O(n)， 因为必须遍历整个链表才能判断元素是否存在。

5.哈希表 HashMap

哈希表是常用的数据结构，用于存储键值对映射，初始化方法如下：

// 整数映射到字符串的哈希表
HashMap<Integer, String> map = new HashMap<>();

// 字符串映射到数组的哈希表
HashMap<String, int[]> map = new HashMap<>();

常用方法如下：（ K 代表键的类型， V 代表值得类型）

// 判断哈希表中是否存在键 Key
boolean containsKey(Object key)
    
// 获得键 Key 对应得值，若 Key 不存在，则返回 null
V get(Object key)
    
// 将 key， value 键值对存入哈希表
V put(K key, V value)

// 如果 key 存在，则删除 key 并返回对应的值
V remove(Object key)

6.哈希集合 HashSet

初始化方法：

// 新建一个存储 String 的哈希集合
Set<String> set = new HashSet<>();

可能使用的方法：

// 如果 e 不存在，则添加 e 到哈希集合
boolean add(E e)
    
// 判断元素 o 是否存在于哈希集合中
boolean contains(Object o)
   
// 如果元素 o 存在，再删除元素 o
boolean remove(Object o)

Java类基本用法

泛型编程

泛型是 Java 提供的一种模板，能够将数据结构的实现和数据类型解耦。

比如在使用 LinkedList 双链表时，可以随意设置其中的元素类型。

不过需要注意，在泛型中只能使用类，不能使用原始类型。

// 装整数的双链表
LinkedList<Integer> list1 = new LinkedList<>();
//报错，不能用 int 这种原始类型作为泛型
LinkedList<int> list2 = new LinkedList<>();

// 装字符串的双链表
LinkedList<String> list3 = new LinkedList<>();

在实现自己的数据结构类时，也需要使用泛型，以便实现的数据结构能够装任何类型。

public class MyLinkedList<E>{
    // 在链表尾部添加元素
    public void addLast(E e){
        // ..
    }
}

// 使用方法
MyLinkedList<Integer> list1 = new MyLinkedList<>();
MyLinkedList<String> list2 = new MyLinkedList<>();

需要注意的是，某些特殊的数据结构对存储的数据类型有要求。

比如 TreeMap 这种数据结构，由于底层是用 BST （二叉搜索树）来存储键值对，所以 TreeMap 要求存入其中的键必须是可比较的，即对于任意两个键，必须能够知道它俩谁大谁小。

在 Java 中，可以给泛型变量添加 extends 来指定该泛型的某些特性。

// MyTreeMap 接受两个泛型 K 和 V，其中 K 必须实现 Comparable 接口
// 即必须实现 compareTo 方法，这样才可以比较大小
public class MyTreeMap<K extends Comparable<K>, V>{
    public V put(K key, v val){
        // ..
    }
}

// 使用方法：
MyTreeMap<Integer, Integer> map1 = new MyTreeMap<>();
MyTreeMap<String, Integer> map2 = new MyTreeMap<>();

Comparable 是 Java 标准库提供的一个接口，实现如下：

public interface Comparable<T> {
    public int compareTo(T o);
}

所以 K extends Comparable 的意思是泛型 K 实现了这个接口，即类型 K 有compareTo这个方法，意味着这两个 K 类型的数据可以比较大小。

Java接口

有时候可能看到以下写法：

Queue<String> q = new LinkedList<>();
List<String> list = new LinkedList<>();

实际 new 出来对的是 LinkedList 类型，但为什么使用 Queue 类型和 List 类型接受呢？

因为 Queue 和 List 都是 Java 标准库中的接口类型：

public interface Queue<E> extends Collection<E> {
    boolean offer(E e);
    E poll();
    E peek();
    // 还有若干方法
}

public interface List<E> extends Collection<E> {
    // 若干方法
}

所谓接口，就是一组方法的集合，只要一个类使用 implements 关键词申明自己实现了接口中的所有方法，那么就可以用这个接口的类型来接受这个类的实例化对象。

具体地，标准库提供的 LinkedList 类实现了List 接口中的所有方法。

// Deque 是 Queue 的子接口，包含了 Queue 接口的所有方法，所以实现了 Deque 就等于实现了 Queue 接口
public class LinkedList<E> implements List<E>, Deque<E>{
    // ..
    
    // Queue 接口中声明的若干方法都会被实现
    boolean offer(E e){...}
    E poll(){...}
    E peek(){...}
    // ...
    
    // List 接口的若干方法也会被实现
    // ...
}

所以可以用 List 接口接受 LinkedList 类型，Queue 接口同理。

动态数组

数组（顺序存储）基本原理

数组可以分为静态数组和动态数组。

静态数组就是一块连续的内存空间，可以通过索引来访问这块内存空间中的元素。

动态数组是编程语言为了方便用户使用，在静态数组的基础上增加了一些常用的API，例如 push ， insert ， remove 等方法，通过这些 API 可以更方便地操作数组元素，不需要自己去写代码完成这些操作。

基于动态数组，可以实现更复杂地数据结构如队列、栈、哈希表等。

静态数组

静态数组在创建时就确定数组的元素类型和元素数量。

只有 C++ 、Java 、 Golang 这类语言才提供了创建静态数组的方式，类似 Python 、 JavaScript 等并没有提供静态数组的定义方式。

定义一个静态数组的方法如下：

// 定义一个大小为 10 的静态数组
int[] arr = new int[10];

// 使用索引赋值
arr[0] = 1;
arr[1] = 2;

// 使用索引取值
int a = arr[0];

以 C++ 为例， int arr[10] 这段代码主要完成以下功能：

1. 在内存中开辟出一段连续的内存空间，大小为 10 * sizeof(int) 字节。一个 int 在计算机内存中占 4 字节，也就是总共 40 字节。
2. 定义一个名为 arr 的数组指针，指向这段内存空间的首地址。

arr[1] = 2 这段代码做了以下事情：

1. 计算 arr 的首地址加上 1 * sizeof(int) 字节（ 4 字节）的偏移量，找到内存空间中的第二个元素的地址。
2. 从这个地址开始的 4 个字节的内存空间中写入整数 2 。

静态数组本质上是一块连续的内存空间，可以随机访问，即：只要给定任何一个数组索引，我们可以在 O(1) 的时间内直接获取到对应元素的值。

增删改查

增

给静态数组增加元素，分为以下情况：

情况一，数组末尾追加（append）元素

// 大小为 10 的数组已经装了 4 个元素
int arr[10];
for(int i = 0; i < 4; i++){
    arr[i] = i;
}

// 现在想在数组末尾追加一个元素 4
arr[4] = 4;

// 再在数组末尾追加一个元素 5
arr[5] = 5;

可以看到，由于只是对索引赋值，所以在数组末尾追加元素的时间复杂度为 O(1)

情况二，数组中间插入（insert）元素

例如，有一个大小为 10 的数组 arr ，前四个索引装了元素，现在想在第 3 个位置（arr[2]）插入一个新元素。

这部分操作涉及数据搬移，给新元素腾出空位，然后才能插入新元素。基本代码逻辑如下：

// 大小为 10 的数组已经装了 4 个元素
int arr[10];
for(int i = 0; i < 4; i++){
    arr[i] = i;
}

// 在第 3 个位置插入元素 666
// 需要把第 3 个位置及之后的元素都往后移动一位
// 注意要倒着遍历数组中已有元素避免覆盖
for(int i = 4; i > 2; i--){
    arr[i] = arr[i - 1];
}

// 现在第 3 个位置空出，可以插入新元素
arr[2] = 666;

综上，在数组中间插入元素的时间复杂度为 O(N) ，因为涉及到数据搬移，需要给新元素腾出地方。

情况三，数组空间已满

由于静态数组在创建时就需要确定大小，所以会存在插入数据时数组空间已满的情况。

由于连续内存必须一次性分配，分配完了就不能随意增减，所以只能重新申请一块更大的内存空间，把原来的数据复制过去，再插入新的元素，也就是数组的扩容操作。

// 大小为 10 的数组已经装满
int[] arr = new int[10];
for(int i = 0; i < 10; i++){
    arr[i] = i;
} 

// 现在想在数组末尾追加一个元素 10
// 需要先扩容数组
int[] newArr = new int[20];
// 把原来的 10 个元素复制过去
for(int i = 0; i < 10; i++){
    newArr[i] = arr[i];
}

// 释放旧数组的内存空间
// ...

// 在新的数组中追加新元素
newArr[10] = 10;

综上，数组的扩容操作会涉及到数组的开辟和数据的复制，时间复杂度为 O(N) 。

删

情况一，删除末尾元素

简单的方法，直接把末尾元素标记为一个特殊值代表已删除即可，例如使用 -1 作为特殊值代表已删除。

删除数组尾部元素本质就是进行一次随机访问，时间复杂度为 O(1) 。

// 大小为 10 的数组已经装了 5 个元素
int arr[10];
for(int i = 0; i < 5; i++){
    arr[i] = i;
}

// 删除末尾元素，暂时用 -1 代表元素已删除
arr[4] = -1;

情况二，删除中间元素

删除中间元素涉及到数据搬移，把被删元素后面的元素都往前移动一位，保持数组元素的连续性。

// 大小为 10 的数组已经装了 5 个元素
int arr[10];
for(int i = 0; i < 5; i++){
    arr[i] = i;
}

动态数组

动态数组代码实现

单/双链表

链表（链式存储）基本原理

链表代码实现

队列/栈

队列/栈基本原理

用链表实现队列/栈

环形数组技巧

用数组实现队列/栈

双端队列（Deque）原理及实现

哈希表

哈希表基本原理

用拉链法实现哈希表

线性探查法的两个难点

线性探查法的两种代码实现

哈希集合

哈希集合的原理

哈希集合的代码实现

二叉树结构

二叉树基础及常见类型

二叉堆

二叉堆的基本原理

二叉堆的代码实现