今天学习的人

今天学习的人

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

Contents

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
• 算法基础
  • 排序 选择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
  • 位运算 异或 奇偶 除2 求中值 平均数 交换值 加法 1个数
  • 分治 分解 -> 解决 -> 合并
• 动态规划
  • 动态规划基础 三要素(重复子问题、最优子结构、动态转移方程) 斐波那契数列 凑零钱问题
  • 记忆化搜索 具备最优子结构 具备重叠子问题 memo记录子问题 子问题构成
  • 线性 DP「未完工」
  • 背包 DP「未完工」
  • 序列 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)
• 图论「未完工」
  • 基本知识
  • 图的存储 邻接表 邻接矩阵 类边 一维数组
  • 图的种类 二分图
  • DFS 回溯 记忆化dfs
  • 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 Skill

• C++
  • 基础知识 GCC 数据类型 条件 循环 运算符 函数 char string 数组 指针 shared_ptr 引用 struct namespace 头文件 链接库 异常处理 输入输出流 文件操作 多文件编程
  • 面向对象 类和对象 继承和派生 多态与虚函数 运算符重载 模版和范型
  • 标准模版库 vector deque multimap multiset unordered_map unordered_set queue priority_queue algorithm
  • C语言内存 虚拟内存 内存对齐 内存分页 MMU 内存模型 内核模式 用户模式 栈 堆 动态内存分配 内存池 野指针 内存泄漏
• Golang
  • 基础知识 string slice map struct 指针 interface
  • Go语言并发 go chan WaitGroup 如何实现 sync.Mutex sync.RWMutex atomic 死锁
  • go tool「未完工」
  • 进阶知识 常见GC算法 Go GC 观察GC 内存泄漏 GC调优
  • 实用函数 计时器
• Python str list set tuple dict defaultdict deque bisect heapq SortedList __lt__ CPython架构
• Linux
  • filesystem overlayfs shared-subrees
• 开发软件 开发 创作 效率 文献 vscode git vim
• 常用 CLI docker CLI k8s CLI ceph CLI
• Markdown
• LaTeX
  • 数学符号 运算符 关系符 定界符 箭头 希腊字母 常用符号 重音符
  • 公式格式 求和 分数 大括号 等号对齐
• Mermaid 流程图 时序图 甘特图 类图 状态图 饼图 用户体验旅程图

Chapter-3 Knowledge

A systematic understanding of a subject is more conducive to generating interest and fostering creativity

• 计算机组成
  • 序 大纲 程序是如何在计算机里跑起来的
  • 计算机系统概述 软硬件分类及发展 冯•诺依曼结构 工作过程 性能指标
  • 数据的表示和运算 数制 定点数 浮点数 算术逻辑单元
  • 存储系统 分类 性能指标 层次化结构 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 期望(项目设计、分布式协作、影响力) 操作指南(阅读源码、静态检查、项目管理)
• 设计模式 多态和多态性 工厂模式

Chapter-4 Math

Manuscript written in 2016, opened again in 2022

• 微积分 微分->趋势->时间 积分->面积(概率)->空间
  • 极限
  • 一元函数微积分
  • 多元函数微分学
  • 二重积分
  • 微分方程
• 线性代数
  • 行列式
  • 矩阵
  • 向量组与方程组
  • 特征与二次型

Chapter-5 Interview

• 找工作经验
• 面经

Chapter-6 Competition

Getting a little insight is more important than getting an answer

Usage

Generate SUMMARY.md for gitbook:

book sm

Statement

Learning can only rely on your own accumulation and summary

All other materials and solutions are just for reference

This repository is only used as its own summary

Publish Gitbook

License CC-BY-SA-4.0 License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Reference oi-wiki | leetcode | luogu | c-biancheng | geeksforgeeks | draveness

Thanks Your Star