图
图中顶点的度:与该顶点相连的边的数量。
在无向图中,一个顶点的度数就是和该顶点相连的边的数量。
在有向图中,一个顶点的度数等于该顶点的入度和出度的和。(入度是指指向该顶点的边的数量,出度是从该顶点出发的边的数量。)
二叉树公式推导(等比数列求和):
f(k)=20+21+22+...+2(k−1)2∗f(k)=21+22+23+...+2k2∗f(k)−f(k)=2k−20\begin{aligned} f(k) = 2^0 + 2^1 + 2^2 +...+2^{(k-1)} \\ 2*f(k) = 2^1 + 2^2 + 2^3 +...+2^k\\ 2*f(k)-f(k)= 2^k -2^0 \end{aligned}f(k)=20+21+22+...+2(k−1)2∗f(k)=21+22+23+...+2k2∗f(k)−f(k)=2k−20
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2叉树公式:f(k)=2k−20a叉树公式:f(a)=(ak−1)/(a−1);注意:节点不一定是个值\begin{aligned} 2叉树公式:f(k) = 2^k -2^0 \\ a叉树公式:f(a)=(a^k-1)/(a-1);\\ 注意:节点不一定是个值 \\ \end{aligned}2叉树公式:f(k)=2k−20a叉树公式:f(a)=(ak−1)/(a−1);注意:节点不一定是个值
二叉树的性质
3. 性质3:对任意一个二叉树,如果其叶子结点的数量为n0n_0n0 ,度为2的结点数为n2n_2n2 ,则一定满足n0=n2+1n_0=n_2+1n0 =n2 +1.
4. 具有n(n>=0)个结点的完全二叉树的深度为⌊log2n+1⌋\large具有n(n>=0)个结点的完全二叉树的深度为\lfloor log_2n+1\rfloor具有n(n>=0)个结点的完全二叉树的深度为⌊log2 n+1⌋
5. 如将一棵有n个节点的完全二叉树自顶向下,同一层自左向右连续给结点编号1,2,……,n\color{red}{1,2,……,n}1,2,……,n;
1. 若i=1,则结点i为根,无父结点
2. 若i>1,则i的父节点编号为⌊i/2⌋\color{green}{ \lfloor i/2 \rfloor}⌊i/2⌋
3. 若2*i>n,则i无左孩子,否则其左孩子编号为2∗i2*i2∗i.
4. 若2*i+1>n,则i无右孩子,负责其有孩子编号为2×i+12 \times i+12×i+1.
存储方法
带权图
map[x][y]表示结点x到结点y边的权值。在边不存在的情况下,会适当地取较大的常数,与普通权值进行区分。
无向图+不带权值图示
无向图+带权值表示
有向图+不带权值表示
有向图+带权值表示
树
先序队(根左右)
* 先序队列也叫前序队列、先根队列、可记作根左右(二叉树父结点向下先左后右)
中序遍历(左根右)
后序遍历(左右根)
二叉树重建
|A\B|前序队列|中序队列|后序队列|
|:--:|:--:|:--:|
|前序队列|0|1|0|
|中序队列|1|0|1|
|后序队列|0|1|0|
故重构必有中序对列
动态规划(DP)(DP)(DP)
* 是一种思想
* 不存在一种万能的思想
1.划分阶段
* 数列每一项:iii
2.确定状态
* 状态:f[i]f[i]f[i]
3.确定决策并写出状态转移方程式
* 例如:f[i]=f[i−1]+1f[i]=f[i-1]+1f[i]=f[i−1]+1
*
【例题】 最大子段和
题目描述
给出一个长度为 nnn 的序列 aaa,选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数,表示序列的长度 nnn。
第二行有 nnn 个整数,第 iii 个整数表示序列的第 iii 个数字 aia_iai 。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
样例输出 #1
提示
样例 1 解释
选取 [3,5][3, 5][3,5] 子段 {3,−1,2}\{3, -1, 2\}{3,−1,2},其和为 444。
数据规模与约定
* 对于 40%40\%40% 的数据,保证 n≤2×103n \leq 2 \times 10^3n≤2×103。
* 对于 100%100\%100% 的数据,保证 1≤n≤2×1051 \leq n \leq 2 \times 10^51≤n≤2×105,−104≤ai≤104-10^4 \leq a_i \leq 10^4−104≤ai ≤104。
【参考代码】
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 最优化原理:(最优子结构):
* 如果问题的最优解所包含的子问题的解也是最优的\color{red}{\large\textbf{最优解所包含的子问题的解也是最优的}}最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足该原理。
2. 无后效性:
* 即某阶段状态 一旦确定\color{red}{\large\textbf{ 一旦确定}} 一旦确定,就 不受这个状态以后的影响\color{red}{\large\textbf{ 不受这个状态以后的影响}} 不受这个状态以后的影响.也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关\color{red}{\large\textbf{只与当前状态有关}}只与当前状态有关.
3. 子问题重叠:
* 即 子问题之间是不独立的\color{red}{\large\textbf{子问题之间是不独立的}}子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到\color{red}{\large\textbf{可能被多次使用到}}可能被多次使用到.(该性质并不是动态规划适用的必要条件\color{red}{\large\textbf{并不是动态规划适用的必要条件}}并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势\color{red}{\large\textbf{不具备优势}}不具备优势)