Estom的博客

1 mysql 命令与操作2 数据库索引的形式 B+树索引 前缀索引Tire索引字典树索引？ 3 数据库的完整性 实体完整性 参照完整性 自定义完整性 4 数据库规范化 1NF 2NF 3NF 4NF 5 并发控制 事务（ACID automatic consistency isolation durability） 并发一致性的问题。脏读、不可重复读、丢失修改 兵法一致性的方案。读写锁：互斥锁、共享锁。三级封锁协议。 6 性能优化 数据库设计优化： 选择合适的存储引擎 设计合理的表结构(符合3NF) 添加适当索引(index) [四种: 普通索引、主键索引、唯一索引unique、全文索引] 查询语句优化： 通过show status命令了解各种SQL的执行频率。 定位执行效率较低的SQL语句-（重点select，记录慢查询） 通过explain分析低效率的SQL 查询过程优化 从内存中读取数据 减少磁盘写入操作(更大的写缓存) 提高磁盘读取速度

1. 对网络模型的理解 五层网络模型、七层网络模型。各层的主要作用。各层的数据结构。各层运行的协议。 2. TCP可靠数据传输的实现机制 停止等待、回退N步、选择重传。 校验和 序号机制 确认机制和超时重传。 滑动窗口和流水线技术 累计确认机制 选择重传机制 3. TCP的三次握手四次挥手 报文段类型SYN、FIN。状态迁移。序号变化。 4. TCP的流量控制和拥塞控制 慢启动 拥塞避免 快重传 快回复 5 路由算法 链路状态路由算法 距离向量路由算法 层次路由算法OSPF、BGP 6 为什么会出现粘包主要原因就是tcp数据传递模式是流模式，在保持长连接的时候可以进行多次的收和发。“粘包”可发生在发送端也可发生在接收端： 由Nagle算法造成的发送端的粘包：Nagle算法是一种改善网络传输效率的算法。简单来说就是当我们提交一段数据给TCP发送时，TCP并不立刻发送此段数据，而是等待一小段时间看看在等待期间是否还有要发送的数据，若有则会一次把这两段数据发送出去。 接收端接收不及时造成的接收端粘包：TCP会把接收到的数据存在自己的缓冲区中，然后通知应用层取数据。当应用...

并查集 参考文献 https://zhuanlan.zhihu.com/p/93647900/ https://blog.csdn.net/qq_41754350/article/details/81271567 1 概念定义并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作： 合并（Union）：把两个不相交的集合合并为一个集合。 查询（Find）：查询两个元素是否在同一个集合中。 2 并查集原理初始化 初始化所有的节点的根节点是自己。 假如有编号为1, 2, 3, …, n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。 查询 我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。 合并 合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的...

背包问题1 01 背包问题问题描述有N个物品，它们有各自的体积和价值，现有给定容量的背包c，如何让背包里装入的物品具有最大的价值总和？ N=4i 1,2,3,4w 2,3,4,5v 3,4,5,6c=8 问题分析策略选择算法设计有两种动态规划的思路，本质上是一致的。背包的容量增长作为第一维，或者物品的数量增长作为第一维。 当背包的容量作为第一维的时候。背包容量为行，物品增长为列。 问题分解划分阶段。背包容量容量为i,物品选择为j 确定状态dp[i][j]表示背包容量为i的情况下，第j个物品放入或者不放入的最大价值。 确定状态转移方程。分两种情况讨论。当背包容量为i时，第j个物品放入和第j个物品不放入。 $$dp[i][j]=max(dp[i][j-1],dp[i-w[i]][j-1])$$ 当物品的增长作为第一维的时候。物品增长为行，背包容量为列 问题分解划分阶段：2个规模增长方向。背包的容量和物品。物品选择i。背包的容量表示为j。第一个阶段表示是否添加物品。第二个阶段是背包容量的增长。 确定状态dp[i][j]表示第i个物品，在背包容量j...

动态规划——序列动态规划 本质上也是矩阵动态规划，是特殊的矩阵动态规划，出现的频率比较高。包含两个规模增长方向，并且相互独立增长。不懂点在于题目是以序列的形式给出的。而不是矩阵形式给出的。 子序列(subsequence)： 一个特定序列的子序列就是将给定序列中零个或多个元素去掉后得到的结果(不改变元素间相对次序)。例如序列<A,B,C,B,D,A,B>的子序列有：<A,B>、<B,C,A>、<A,B,C,D,A>等。 公共子序列(common subsequence)： 给定序列X和Y，序列Z是X的子序列，也是Y的子序列，则Z是X和Y的公共子序列。例如X=[A,B,C,B,D,A,B]，Y=[B,D,C,A,B,A[，那么序列Z=[B,C,A]为X和Y的公共子序列，其长度为3。但Z不是X和Y的最长公共子序列，而序列[B,C,B,A]和[B,D,A,B]也均为X和Y的最长公共子序列，长度为4，而X和Y不存在长度大于等于5的公共子序列。对于序列[A,B,C]和序列[E,F,G]的公共子序列只有空序列[...

1 三角形数组最小路径和问题描述给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如，给定三角形： 1234567[ [2], [3,4], [6,5,7], [4,1,8,3]]自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 说明：如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。 问题分析策略选择算法设计 问题分解划分阶段：规模增长方向，从下到上（不用判断边界）。阶段n=n,n-1,…,1 确定状态变量：k阶段的状态变量是数组X[n]内的前k项，组成的状态变量集合。 状态转移方程。k阶段的状态变量X_k[n],分两种情况讨论。X_k[j]可能有两种情况，利用了上一阶段X_k-1[j]的长度。或者领了X_k-1[j+1]的长度。$$X_{k}[j]=min{X_{k-1}[j-1]+triangle[j],X_{k-1}[j+1]+triangle[j]}$$ 确定边界实现过程。初始值为0。从最后一层开始。 算法实现12345...

动态规划——矩阵动态规划 矩阵可以看作是图的一种，怎么说？你可以把整个矩阵当成一个图，矩阵里面的每个位置上的元素当成是图上的节点，然后每个节点的邻居就是其相邻的上下左右的位置 矩阵类动态规划的两个规模增长方向可能存在两种情况：等价独立和非等价独立。例如不同路径和最大矩形中的规模增长方向，是等价独立的，两个规模增长的含义是一样的，比较好判断。但是在背包问题等其他子问题中。规模增长的方向是不等价，一个是背包容量的增长，另一个是物品数量的增长，通常比较难发现。 在矩阵动态规划中，两个维度的增长方向是可以相互交换的。只要设计好即可。但有可能存在一个简单一个复杂的情况。 不同路径 最大矩形 1 不同路径问题描述一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？例如，上图是一个7 x 3 的网格。有多少可能的路径？说明： m 和 n 的值均不超过 100。 示例 1: 12345678输入: m = 3, n = 2输出:...

棋盘覆盖问题问题描述棋盘覆盖问题。有一个$2^k∗2^k$的方格棋盘，恰有一个方格是黑色的，其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖，且任意一个白色方格不能同时被两个或更多牌覆盖。如图所示为L型牌的4种旋转方式。 求解棋盘覆盖的方法。 问题分析 问题分类： 策略选择 数据结构：线性数据结构 算法思想：分治法 算法设计分治三步骤 划分问题：将$2^k∗2^k$的棋盘划分为 $2^{k−1}∗2^{k−1}$这样的子棋盘4块。 递归求解：递归填充各个格子，填充分为四个情况，在下面会有解释，递归出口为 k=0k=0也就是子棋盘方格数为1。 合并问题：不需要合并子问题。 分治方法：将棋盘等分为四块。然后分为以下两种情况。 额外的方格在某一块中，不需要处理该区块。 额外的方格不在某一块中。则添加一个L型牌覆盖三个没有额外方格的块。 重复以上步骤直到能完全覆盖。 算法分析算法实现12345678910111213141516171819202122232425262728293031323334353637383940...