EkkoSonya's Blog

图论基础

简单介绍

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

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

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

想起了本科跟着老师搞复杂网络，就是在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 ，则应该 逐出 最久未使用的关键字。

杂

Cookie 和 Session

Session 是基于Cookie 实现的另一种记录服务端和客户端会话状态的机制。

Session 是存储在服务端，而 SessionId 会被存储在客户端的 Cookie 中。

Session 的认证过程：

1. 客户端第一次发送请求到服务端，服务端根据信息创建对应的 Session，并在响应头返回 SessionID
2. 客户端接收到服务端返回的 SessionID 后，会将此信息存储在 Cookie 上，同时会记录这个 SessionID 属于哪个域名
3. 当客户端再次访问服务端时，请求会自动判断该域名下是否存在 Cookie 信息，如果有则发送给服务端，服务端会从 Cookie 中拿到 SessionID，再根据 SessionID 找到对应的 Session，如果有对应的 Session 则通过，继续执行请求，否则就中断

基础

OSI 与 TCP/IP 网络模型

OSI 七层模型

物联网书会使用 (物数网传会表应)

物理层，数据链路层，网络层，传输层，会话层，表示层，用户层

OSI 七层模型 是国际标准化组织提出一个网络分层模型，其大体结构以及每一层提供的功能如下图所示

每一层都专注做一件事情，并且每一层都需要使用下一层提供的功能

比如传输层需要使用网络层提供的路由和寻址功能，这样传输层才知道把数据传输到哪里去