图论基础

简单介绍

想象一下，现在有一个巨大的社交网络，其中每个人都与若干个人有联系 如果是你，你会怎么表示它的数学模型呢（或者说，你会怎样把它抽象出来，使它易于表示、观看）；

一个很显然的做法是：将人抽象成点，将人与人的关系抽象成线，两个点有连线，当且仅当这两个点代表的两个人有联系； 也就是说，两个人有联系时，我们就把他们连起来；

图就是将复杂的关系简单化的一种数据结构，能够轻而易举地看出复杂关系，并加以研究

想起了本科跟着老师搞复杂网络，就是在matlab搞图

DFS

深度优先搜索（Depth-First Search） 是一种用于遍历或搜索图、树的算法。

核心思想

从起点出发，沿着一条路径尽可能深入，直到无法继续时回溯，再探索其他路径。

特点

• 使用栈（或递归调用栈）实现
• 不保证找到最短路径
• 时间复杂度：O(V + E)，V 为顶点数，E 为边数
• 空间复杂度：O(V)（递归深度最多为顶点数）
• 适合：路径搜索、连通性判断、拓扑排序、回溯问题

概念

Trie（发音 "try"，又称前缀树、字典树）是一种树形数据结构，用于高效存储和检索字符串。

核心思想

利用字符串的公共前缀来减少存储空间和查询时间。

结构图示

存储 ["app", "apple", "apply", "bat"] 的结构：

        (root)
       /      \
      a        b
      |        |
      p        a
      |        |
      p*       t*
    / | \
   l  l  e*
   |  |
   y* e*
      |
      *

最短路径算法

问题定义

给定一个图 $G = (V, E)$，每条边有一个权值 $w(e)$，求从一个点到另一个点的路径，使得路径上所有边的权值之和最小。

ACM 模式(输入输出)

Scanner 类

Scanner 是 Java 中用于解析基本类型和字符串的简单文本扫描器，位于 java.util 包中

Scanner 的核心逻辑是基于分隔符（Delimiter）将输入拆分为标记（Tokens）。

• 默认分隔符：空白符（包括空格、回车 \n、制表符 \t 等）。
• 解析方式：它不仅能读字符串，还能自动尝试将标记转换为 int、double 等基本类型

String 常用 API

1. 长度和判空

String s = "hello";
int n = s.length();        // 5
boolean empty = s.isEmpty(); // false

接口体系

Collection
├── Set（无序、无重复）
│   ├── HashSet          // O(1) 增删查，无序
│   ├── LinkedHashSet    // 保持插入顺序
│   └── TreeSet          // 有序（红黑树），O(log n)
├── List（有序、可重复）
│   ├── ArrayList        // 动态数组，O(1) 查，O(n) 增删
│   ├── LinkedList       // 链表，O(n) 查，O(1) 增删头尾
│   └── Vector           // 线程安全的ArrayList（较少用）
└── Queue（队列）
    ├── LinkedList       // 普通队列
    ├── PriorityQueue    // 优先级队列（小根堆）
    ├── Deque            // 双端队列
    │   └── LinkedList/ArrayDeque
    └── BlockingQueue    // 阻塞队列（多线程）

Map（键值对，无重复键）
├── HashMap              // O(1) 平均，无序
├── LinkedHashMap        // 保持插入顺序
├── TreeMap              // 有序（红黑树），O(log n)
├── Hashtable            // 线程安全（较少用）
└── ConcurrentHashMap    // 线程安全的HashMap

LRU

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。