EkkoSonya's Blog

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 ，则应该 逐出 最久未使用的关键字。

DFS

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

核心思想

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

特点

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

杂

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

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

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

传输层

Socket

即套接字，是应用层 与 TCP/IP 协议族通信的中间软件抽象层，表现为一个封装了 TCP / IP协议族 的编程接口（API）

Socket是一个编程接口，让你不用关心TCP/IP协议细节，直接调用函数就能收发数据

网络层

网络层的主要作用是：实现主机与主机之间的通信，也叫点对点（end to end）通信

网络层与数据链路层有什么关系

IP（网络层） 和 MAC （数据链路层）之间的区别和关系

IP 的作用是主机之间通信用的，而 MAC 的作用则是实现「直连」的两个设备之间通信，而 IP 则负责在「没有直连」的两个网络之间进行通信传输

在区间内移动相当于数据链路层，充当区间内两个节点传输的功能，区间内的出发点好比源 MAC 地址，目标地点好比目的 MAC 地址。

整个旅游行程表就相当于网络层，充当远程定位的功能，行程的开始好比源 IP，行程的终点好比目的 IP 地址

网络层

IP 地址与路由控制

IP地址的网络地址这一部分是用于进行路由控制。

路由控制表中记录着网络地址与下一步应该发送至路由器的地址。在主机和路由器上都会有各自的路由器控制表。

在发送 IP 包时，首先要确定 IP 包首部中的目标地址，再从路由控制表中找到与该地址具有相同网络地址的记录，根据该记录将 IP 包转发给相应的下一个路由器。如果路由控制表中存在多条相同网络地址的记录，就选择相同位数最多的网络地址，也就是最长匹配。

下面以下图的网络链路作为例子说明：