《自学主义》

今天学习的人

是未来之星
是国家「栋」梁
是自然界的丛林之王
是俗语里的下凡仙子
是粤语里的巴鸠撚闭
是成语里面的学富五车
是武侠小说里的人中龙
是都市小说里的城市之光
是吾日三省吾身的自律者
是相亲节目里面的心动嘉宾
是世间所有丑与恶的唾弃者
是世间所有美与好的创造者

Chapter-1 Algorithm

前述 刷题经验 C++调试模版 常见报错
数据结构 🧾例题清单
- 概述 基本概念 算法评价
- 线性表 顺序存储(数组) 环状数组 链式存储(链表) 哨兵 多画 舍得变量 双指针 环状链表 Medium
- 栈 顺序、链式存储 单调栈 表达式求值 递归 移除问题 Medium
- 队列 顺序、链式、双端 单调队列 层遍历 Medium
- 字符串「未完工」 顺序、堆分配、块链存储 KMP算法
- 树 & 二叉树 树的种类 二叉树遍历(前序、中序、后序、层) 二叉树构造「未完工」 线索二叉树 Easy
  - 排序树 & 平衡树 & 搜索树「未完工」 AVL树 红黑树 查找、插入、删除 O(logn)
  - B树 & B+树「未完工」
  - 并查集 连通 连通分量 连通性判断 添加、连通、查找O(logn) Medium
  - 树状数组 & 线段树 维护区间信息 单点更新O(logn) 区间查询O(logn) Hard+
  - 字典树 前缀树 字符串/字符前缀是否存在 dfs Hard
  - 哈夫曼树「未完工」
- 散列表 哈希表 本质-数组 核心-散列函数 哈希冲突 扩容 查找
- 堆 优先队列 大/小根堆 TopK 多路归并 中位数 插入O(logn) 查找O(1) 删除O(logn) Hard
- 设计数据结构 哈希集合/表 队列<->栈 LRU LFU
算法基础 🧾例题清单
- 排序 选择O(n^2) 冒泡O(n^2) 插入O(n^2) 计数O(n) 桶O(n) 快速O(nlogn)「未完工」 归并O(nlogn) 外部排序「未完工」 Hard
- 二分法 不可套模版 二段性 寻找一个数 lower_bound upper_bound O(logn) 三分 Hard+
- 双指针 快慢双指针 左右双指针 前后双指针 指向各自集合的双指针 Floyd判圈算法 时O(n) 空O(1) Medium
- 滑动窗口 单调性 窗口数据结构 右边届入窗 左边届收缩 延时删除 采集答案 步长 起始位置 Medium
- 前缀和 相减 哈希表 二维前缀和 前缀和**
- 差分 两端操作 操作区间从O(k)降至O(1) 二维差分
- 贪心 排序预处理 区间调度问题 跳跃问题 环形贪心 堆 单调栈 Hard
- 位运算 >>i逐位考察 异或 奇偶 除2 乘2 2的n次方 求中值 平均数 交换值 加法 1个数 滚动数组 状态压缩
- 分治 分解 -> 解决 -> 合并
- 模拟
动态规划 🧾例题清单
- 动态规划基础 三要素(重复子问题、最优子结构、动态转移方程) 斐波那契数列 凑零钱问题
- 记忆化搜索 具备最优子结构 具备重叠子问题 memo记录子问题 子问题构成
- 线性 DP 以i结尾的方案数 [0,1]范围内的最优解 打家劫舍 路径问题
- 背包 DP 01背包 完全背包 多重背包 混合背包 分组背包 多维背包 树形背包
- 序列 DP 无后效性 最长上升子序列(LIS) 最长公共子序列(LCS) 最大子数组和 LCS和LIS相互转化
- 区间 DP f(l,r)=max(f(l,k), f(k+1,r))+cost k in [l,r] 遍历方法 初始化(dp[i][i]=1) 返回(dp[0][i]) 回文问题 时O(n^2)
- 树形 DP「hold on」 后序遍历 打家劫舍III
- 状态压缩 DP 位运算 state = (1 << num) | state ((state >> num) & 1) == 0 n<15
- 数位 DP「hold on」
- 股票问题 状态机DP
图论「未完工」 🧾例题清单
- 基本知识
- 图的存储 邻接表 邻接矩阵 类边 一维数组
- 图的种类 二分图
- DFS 回溯 记忆化dfs
- BFS 逐个遍历 逐层遍历 最短路径 双向bfs 多源bfs
- 拓扑排序 有向无环图 学完a课才能学b课
- 最短路径 Dijkstra、非负权、O(nlogn) Floyd、多源、O(n^3) Bellman-Ford、负环、O(n^2)
- 欧拉图 一笔画完整个图
数学「未完工」 🧾例题清单 倍增 快速幂 求余
- 计算机算法 num->arr（短除法） arr->num bin_to_dec dec_to_bin 向上取整
- 数学算法 高斯求和 蓄水池抽样算法 洗牌算法
- 余数相关性质 同余定理 加 减 乘 乘方
系列题目 🧾例题清单 括号问题 接雨水问题

Chapter-2 Course

MIT 6.S081: Operating Systems Engineering
- syscall page table trap page fault interrupt lock Thread switching sleep&wakeup file system inode log Monolithic/Micro kernel Virtual Machine HLL kernel Networking Meltdown RCU
MIT 6.824: Distributed System「未完工」
NJU 操作系统: 设计与实现「未完工」
CMU 15-445: Database Systems「未完工」

Chapter-3 Skill

ASM
- RISC-V riscv asm manual 简介 通用寄存器和指令 扩展寄存器和指令 五级流水线 硬件模块 译码模块 ALU模块(执行计算) branch模块(条件跳转) load/store(访存) CSR读写控制
C「未完工」
- C语言内存 虚拟内存 内存对齐 内存分页 MMU 内存模型 内核模式 用户模式 栈 堆 动态内存分配 内存池 野指针 内存泄漏
C++
- 基础知识 GCC 数据类型 条件 循环 运算符 函数 char string 数组 指针 shared_ptr 引用 struct namespace 头文件 链接库 异常处理 输入输出流 文件操作 多文件编程
- 面向对象 类和对象 继承和派生 多态与虚函数 运算符重载 模版和范型
- 标准模版库 vector deque multimap multiset unordered_map unordered_set queue priority_queue algorithm
Golang
- 基础知识 string slice map struct 指针 interface
- Go语言并发 go chan WaitGroup 如何实现 sync.Mutex sync.RWMutex atomic 死锁
- 进阶知识 常见GC算法 Go GC 观察GC 内存泄漏 GC调优
- 实用函数 计时器
Python str list set tuple dict defaultdict deque bisect heapq SortedList __lt__ CPython架构 python为什么慢
开发软件 工具 网站 vscode git vim gdb gcc tmux
常用 CLI docker k8s ceph
Markdown
LaTeX
- 数学符号 运算符 关系符 定界符 箭头 希腊字母 常用符号 重音符
- 公式格式 求和 分数 大括号 等号对齐
Mermaid 流程图 时序图 甘特图 类图 状态图 饼图 用户体验旅程图

Chapter-4 Knowledge

IC design fabrication package EDA FPGA Verilog
计算机组成
- 序 大纲 程序是如何在计算机里跑起来的
- 计算机系统概述 软硬件分类及发展 冯•诺依曼结构 工作过程 性能指标
- 数据的表示和运算 数制 定点数 浮点数 算术逻辑单元
- 存储系统 分类 性能指标 层次化结构 SRAM(cache) DRAM(内存) ROM(闪存、固态) MM组成和使用 Cache 虚拟存储器
- 指令系统 指令(操作码+地址码) 指令寻址 数据寻址 指令集 CISC RISC
- **处理器 CPU(运算器+控制器) 指令执行 数据通路 硬布线控制器 微程序控制器 指令流水线
- 总线 片内、系统、通信总线 性能指标 总线仲裁 传输和定时 总线标准
- 输入输出系统 外部设备 IO接口 IO方式(查询、中断、DMA)
操作系统
- 计算机系统概述 目的(管理、调度软硬资源、提供接口) 特征(并发、共享、虚拟、异步) 分类 运行环境(内核态、用户态) 中断 系统调用
- 进程管理 进程(程序段、数据段、进程控制块) 目的(并发、共享) 进程通信 线程(ID、计数器、寄存器集合) 目的(减少开销) 实现方式(用户级、内核级) 处理机调度 进程同步 互斥 死锁 饥饿
- 进程 & 线程 & 协程 时间角度 资源角度
- 内存管理 目的(并发) 覆盖与交换 连续分配 非连续分配(分页存储) 分段存储 虚拟内存 局部性原理(时间、空间)
- 文件管理 文件结构 目录结构 共享 保护 文件系统结构 目录实现 文件实现 磁盘(结构、调度、管理)
- 输入输出管理 IO设备 IO控制方式 IO层次 设备分配、回收 Cache(缓存) Buffer(缓冲区)
计算机网络
- 计算机网络体系结构 组成 功能 分类 性能指标 OSI模型(7层) TCP/IP模型(4层) 5层协议体系 报文、包、帧等概念
- 物理层 层一 传输比特流 数字信道(基带信号) 模拟信道(宽带信号) 奈奎斯特定理(码元极限传输速率) 香农定理(数据极限传输速率) 编码与调制PSK 电路、报文、分组交换 数据报、虚电路服务 传输介质 中继器 集线器
- 数据链路层 层二(mac层) 数据逻辑上无差错 链路管理 组帧 差错控制 流量控制(滑窗) 介质访问控制(多路复用、随机访问CSMA) 局域网(以太网) IEEE 802.3/11 网卡(MAC地址) 广域网(交换机+链路) 网桥 以太网交换机
- 网络层 层三(IP层) 功能(异构互联、分组转发、拥塞控制) 路由算法 IPv4 IP数据报 IP地址 子网 IPv6 路由协议 IP组播 移动IP 路由器
- 传输层 功能(进程间通信) 端口 socket(嵌套字) UDP(无连接) TCP(连接) 报文段 TCP建立连接(三次挥手) TCP释放连接(四次握手) 可靠传输 流量控制 拥塞控制
- 应用层 网络应用模型(C/S、P2P) DNS FTP 电子邮件(SMTP、POP3/IMAP) 万维网(HTTP) Cookie
- 5G 网络架构 场景 网络架构 接口 协议栈 核心网 接入网 组网 层二(mac数据面) 层三(mac控制面)
数据 & 存储
- 设计数据密集型应用「未完工」
- 数据库「未完工」 关系型数据库 NoSQL
- 消息队列「未完工」
容器技术
- docker 原理 Namespace(进程、网络、存储) CGgroups UnionFS
- kubernetes 原理 介绍 设计 架构(master、worker) 重要概念(对象、Spec、Status)
- kubernetes 对象详解 pod service volume replicaSet garbage collector deployment statefulSet daemonSet job&cronJob
- kubernetes 定制特性 扩展接口 容器接口(网络插件、存储插件、运行时接口) 设备插件 调度框架
- kubernetes 问题 & 局限性 集群管理(水平扩展性、多集群管理) 应用场景(应用分发、批处理调度、硬多租户)
- kubernetes 集群联邦 & 资源分发 kubefed karmada
- kubernetes 贡献指南 SIG KEP 期望(项目设计、分布式协作、影响力) 操作指南(阅读源码、静态检查、项目管理)