好好学习基础，不积跬步无以至千里

数据结构

数据结构包括：线性结构和非线性结构

线性结构：
- 最常用的数据结构
  
  特点是数据元素之间存在一对一的线性关系
- 又能分为两种不同的存储结构，顺序存储结构和链式存储结构。
  
  顺序存储的线性表为顺序表，顺序表中的存储元素是连续的。
  
  链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
- 常见的数据结构：数组，队列，链表和栈
非线性结构：
- 包括：二维数组，多维数组，广义表，树结构，图结构

1.稀疏（sparsearray）数组

概念：当一个数组的大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏素组的处理方法：
- 记录数组一共有几行几列，有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

以五子棋程序为例，有存盘退出和续上盘的功能。

分析问题：二位数组的很多值默认是0，因此记录了很多没意义的数据=>稀疏数组

例如：

一个11行11列的棋盘，在1行2列有个黑旗，2行3列有个白旗，其转换的稀疏数组为

	row	column	val
0	11	11	2
1	1	2	1
2	2	2	2

二维数组转稀疏数组的思路：

遍历原始的二维数组，得到有效数据的个数
根据sum就可以创建稀疏数组sparseArr in[sum+1][3]
将二维数组的有效数据存入到稀疏数组

稀疏数组转二维数组的思路：

先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的chessArr2=int[11][11]
再读取稀疏数组后几行的数据，并赋给原始的二维数组即可

生成数组：以4行3列为例

```
b = [[0]*3 for i in range(4)]
b = numpy.array(b)

1
2

numpy.zeros(shape(4,3),dtype = int)


## 2.队列（queue）

### 2.1队列的数组实现

队列特性：先进先出

与数组的对应关系，数组的0即队列的1，容量maxSize对应数组的最后一位参数为[maxSize-1]

- 关键是三个参数，队列容量maxSize，头指针front，尾指针rear

  头指针：初始front = -1，队列每出一个数头指针后移一位，仍然指向当前队列头部的前一个位置，也就是指向我移除的数的位置

  尾指针：初始rear=-1，队列每进一个数尾指针后移一位，仍然指向队列尾部的那一个位置，也就是我这次要加入的数

- 判断队列是否为空和是否已满

  为空：front == rear，此时禁止从队列获取

  已满：rear == maxSize - 1，此时禁止向队列添加

- 问题：

  此时实现的队列只能一次性使用，把队列填满，把数取完就不能用了

### 2.2环形队列的数组实现

通过指针的环形变化，可以解决队列的一次性使用问题

如何变化？

类似数电的进制转换，可以将环形队列视为模为maxSize的表盘，front和rear作为两个顺时针旋转（均执行+1操作，也就是单向旋转）的指针。

front到rear的顺时针距离也就对应当前队列的数据个数

- 初始均指向0

  front指向队列头部的那个数的位置，也就是下一个代取的数

  rear指向队列尾部的后面一个位置，也就是下一个要填入的数

  然后front和rear再都后移一位。

- 判断队列书否为空或已满：
  为空：front == rear

  已满：（rear+1）%maxSize == front

  rear+1对模取余也就对应rear+1在表盘上的位置，表示rear和front顺时针距离为1时未满

  这也是为了避免和为空的判断重叠，牺牲了一个空间，也就是这个队列先入先出，但是有一个位置是一直空在最末端，程序使用者自然也不会发现。

[java及python的实现代码](https://gitee.com/biongd/Data_sructure-and-Algorithm)

## 3.链表

### 3.1特点

- 链表是以节点的方式来存储
- 每个节点包含data域，next域：指向下一个节点
- 链表的各节点不一定是连续存储
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

### 3.2单链表创建

- 在链表末尾添加新节点

  1. 先创建一个head头节点，作用就是表示单链表的头（空）

  2. 每添加一个节点，就直接加入到链表的最后遍历

  3. 通过一个辅助变量（节点对象），帮助遍历整个链表

  总结：两个类：节点类和链表类

  节点类包含节点对象的data和next，链表类包含链表应该执行的创建功能（即添加新节点）

  就是通过一个链子将一个个零散的节点串起来，而next就是这个链子。

  每一次添加节点其实就是让原本链表的最后一个节点的next=新节点，也就是每一个新建节点其实都是前一个节点的next属性。

  temp作为一个辅助的临时指针，在每次需要添加的时候开始从头遍历链表

- 按照序号插入新节点

  在上一基础上增加两个判断就可以实现，定义一个布尔变量flag，默认为false，链表中节点已存在则为true。

  1. 遍历过程中判断temp.next是否为null，为null则跳出循环，
  2. 遍历过程中判断新节点的编号是否小于temp.next的编号，出现则跳出循环
  3. 遍历过程中判断新节点的编号是否等于temp.next的编号，出现则将flag= true，跳出循环

  判断1：说明没找到比新节点no大的节点，将新节点排在末尾（temp.next）

  判断2：说明新节点的编号比temp的编号大，比temp.next的编号小，应该插入两者中间。

  现将新节点的next绑上temp.next      heronode.next = temp.next

  再给temp的next绑上新节点：temp.next = heronode

  这两条对新节点排在末尾（判断1）也适用

  判断3：判断2的例外情况就是temp.next和新节点的编号相同，也就是同1节点，这时候就终止循环，弹出提示就好

  除这3种情况外，也就是新节点编号比temp.next大，这时候就执行循环，将temp后移就

#### 3.2.1单链表面试题

1. 求单链表中的节点个数

   - temp = head.next（注意：此方法传入参数除链表对象外，还要传入链表的head对象）

   - 如果temp == None,节点数为0

   - 定义一个计数器count=0

     遍历条件：temp ！= None

     每次执行循环count++

     temp = temp.next

2. 查看链表的倒数第k个节点

   - 在上一基础上，得到链表的总结点数size，倒数第k个节点就是正数第size-k+1个节点

   - 定义temp = head.next

     此时temp移动到size-k+1个节点的位置需要移动size-k个

   - 通过一个for循环实现：
     for（i=0 ; i<size-k ; i++）{

     	temp = temp.next

     }
   
3. 单链表进行反转

   - 定义一个新的头节点reversehead
   - 对原链表进行遍历，每一次temp移动，都将其添加到reversehead的后面

   ```python
   temp = head.next
   while(temp != None):
   	next = temp.next            #next指针，指向老链表的下一个结点
       temp.next = reversehead.next   #新链表插入temp
       reversehead.next = temp
       temp = next            #老链表向后移动一位

再领head.next = reversehead.next

从尾到头打印单链表

思路一：先反转后打印，但是看上面的步骤，原有单链表的结构就被改变了

思路二：将遍历的结点push到栈中，打印时再put出来

3.2.2leetcode刷题的总结

链表题目的解题关键：

灵活使用递归
指针：考虑需要几个指针，指针如何移动，指针间的关系问题。

在刷题过程中领悟到的一个问题：

赋值语句只是对目标进行了浅拷贝，指向的是同一片内存空间，相同的内容。

所以当我给链表中的节点添加指针的时候，指针的操作实际上也就是对应节点的操作。

3.3双向链表

单链表的缺陷：
- 单向链表查找的方向只能是一个方向，双向链表可以向前或向后查找
- 单向链表不能自我删除，要靠辅助接点，而双向链表则可以自我删除。
双链表的建立：

在单链表的基础上添加一个pre指针，指向上一个节点
- 末尾添加节点：遍历到最后一个节点（temp.next = None/Null）
  
  temp.next = newheronode();
  
  newheronode.pre = temp
- 中间插入节点：和单链表相同
  
  temp.no == newheronode.no;
  
  temp.next.pre = newheronode;
  
  newheronode.next = temp.next
  
  newheronode.pre = temp
  
  temp.next = newheronode
- 修改也和单链表一样
- 删除（可以直接删除）
  
  原本单链表是找到temp.next
  
  temp.next.no == no
  
  temp.next = temp.next.next
  
  双链表直接找到temp就行了
  
  temp.no == no
  
  temp.pre.next = temp.next
  
  temp.next.pre = temp.pre

3.4单向环形链表-约瑟夫问题

约瑟夫问题：

4.栈（stack）

4.1 栈的概念

先入后出（FILO）的有序列表

栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表，允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底

4.2栈的应用场景

子程序的调用，在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈
表达式的转换（中缀表达式转后缀表达式）与求值（实际解决）
二叉树的遍历
图形的深度优先（depth-first）搜索法

4.3 数组模拟栈的实现

栈类的参数：

栈的大小maxsize（传入）
栈顶指针top
初始化一个空数组，容量为maxsize

应具备的函数：

判断栈空，栈满
栈push和栈pop
展示栈内数据

4.4 实例：表达式的计算

栈完成四则运算表达式的思路：

通过一个index索引值，遍历表达式
如果index指向的是一个数字，压入数栈；如果index指向一个符号，压入符号栈
每次在将符号入栈之前应该先进行优先级比较，如果当前符号优先级小于栈内符号优先级（因为每次都这么比，保证符号栈最上面的符号一定是优先级最高的），则先将栈内的符号（优先级高的）pop出来，再将栈内的两个数拿出来进行运算。运算结果压入栈。最后再把符号压入栈中。

5. 树

根（树的最初节点）、度（节点拥有的子树数）、叶节点/终端节点（度为0的节点）、深度/高度（从根到叶的最大层次）、有序和无序（树中节点的各子树能否互换位置）

5.1 二叉树的概念

特点：
- 每个节点最多有两颗子树，不存在度大于2的节点
- 左子树和右子树是有顺序的，不能颠倒
- 即使树中的某节点只有一颗树，也要区分左子树还是右子树
5中基本形态：
- 空二叉树
- 只有一个根节点
- 根节点只有左子树
- 根节点只有右子树
- 根节点既有左子树又有右子树
特殊二叉树
- 斜树：只有左子树或只有右子树，线性表结构可以理解为树的一种极其特殊的表现形式。
- 满二叉树：应有尽有
- 完全二叉树：不满，但是存在的节点顺序都是按照满二叉树的顺序来的。
性质
- 在二叉树的第i层上至多有$2^{i-1}$个节点
- 深度为k的二叉树至多$2^k-1$个节点
- 对任何一颗二叉树T，如果终端节点数为$n_0$，度为2的节点数为$n_2$，则$n_0=n_2+1$
- 具有n个节点的完全二叉树的深度为$[log_2n]+1$([X]表示不大于X的最大整数)
- 如果一颗有n个节点的完全二叉树（深度为$[log_2n]+1$）的节点按从上到下，从左到右的层序编号，对任意i号节点：
  
  i>1：其双亲是节点[i/2]
  
  2i>n：要么节点i无左孩子（节点i为叶子节点）；否则其左孩子是节点2i
  
  2i+1>n：要么节点i无左孩子（节点i为叶子节点）；否则其左孩子是节点2i+1

5.2 顺序二叉树

1.从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，反向亦可。

树的结点可以保存到数组中
数组中的元素可以前序中序和后序遍历

2.顺序二叉树的特点：

顺序二叉树通常只考虑完全二叉树
第n个元素的左子节点为2*n+1
第n个元素的右子结点为2*n+2
第n个元素的父结点为（n-1）/2

n表示二叉树中的第几个元素（从0开始编号）

3.前中后序遍历

前序遍历：先输出父节点，再遍历左子树和右子树
中序遍历：先遍历左子树，再输出父节点，再遍历右子树
后序遍历：先遍历左子树，再遍历右子树，最后输出父节点树均为二叉搜索树

6. 图

6.1 概念

区别于线性表的一个前驱和一个后继，以及树的一个直接前驱（父节点），表示数据间的多对多关系

常用概念：顶点，边，路径，无向图，有向图，带权图（边带权，也叫网）

图的表示方式：

二维数组表示（邻接矩阵）

表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵的row和col表示1。。。n个点

因为不存在的边也表示在矩阵中，所以会造成一定程度的空间浪费。
链表表示（邻接表）

只关心存在的边，不关心不存在的边，因此没有空间浪费，邻接表由数组+链表组成。

6.2 深度优先遍历

策略：

从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点，访问它的第一个邻接节点，可以这样理解：每次都在访问完当前节点后首先访问当前节点的第一个邻接节点。

访问策略总结：优先往纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问。显然，这是一个递归的过程。
算法步骤：
- 访问初始节点v，并标记节点v为已访问
- 查找节点v的第一个邻接节点w
- 如果w存在，则继续执行下一步，如果不存在，则返回第一步，从v的下一个节点继续
- 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）
- 查找节点v的w邻接节点的下一个邻接节点，转到步骤3

算法

1. 排序

1.1 冒泡排序O($n^2$)

规则：

进行数组size-1次大的循环
每趟排序的次数逐渐减小
某趟排序中顺序并没有发生变化，说明顺序正常，可以提前结束循环

1.2 归并排序O($nlogn$)

将两个或两个以上的有序表合并成一个新的有序表

通过递归实现链表归并排序，有以下两个环节：

分割 cut 环节：找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）
- 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
- 找到中点 slow 后，执行 slow.next = None 将链表切断。
- 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
- cut 递归终止条件：当head.next == None时，说明只有一个节点了，直接返回此节点。
合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。
- 双指针法合并，建立辅助ListNode h 作为头部。
- 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
- 返回辅助ListNode h 作为头部的下个节点 h.next。
- 时间复杂度 O(l + r)，l, r 分别代表两个链表长度

注意：奇数的情况比较难想，但是和偶数的情况差别不大，递的过程最终都是cut为单个节点，然后怎么cut的，归的过程中也就怎么merge，不过奇数的那一半顺序表的二叉树比另一半要多一层。

2. 查找

2.0 顺序查找

直接循环遍历，时间复杂度：O(n)

2.1 二分查找

时间复杂度：O(logn)

$mid = \frac{1}{2}(left+right) = left+\frac{1}{2}(right-left)$

2.2 插值查找

时间复杂度：O(logn)

$mid = left+\alpha(right-left)$

$\alpha = \frac{tar-arr[left]}{right-left}$

插值查找算法和二分查找算法的区别主要就在于中间位置mid的确定，它们在终止条件和判断条件上都是相同。

可以看到二分查找的中值确定为区间的中点位置，插值查找的中点位置由1/2变成了α。而α的值和目标的位置有关，tar越靠近区间最左侧的值arr[left]，α越小，反之越大。

这里也可以看出该方法更适用于数值分布比较均匀的情况，此时的α要明显优于直接取中间值的简单粗暴。

2.3 斐波那契查找

时间复杂度：O(logn)

同样类似于于二分查找，区别任然是中值mid的选取：$mid = left+F(k-1)-1$

原理：

将数组的长度对应于第k个位置的斐波那契数列的值-1：$arr.length = f(k)-1$
利用斐波那契数列的黄金分割特性：$arr.length = f(k)-1 = f(k-1)-1+”mid占的一个位置”+f(k-2)-1$这里数组就被分为了左右两边。
由于数组长度n不一定刚好为$f(k)-1$，所以需要将$f(k)-1$设置为刚好大于或等于n的值，用arr[right]将数组填充到$f(k)-1$的长度。while(n>f(k)-1) k++;

3. 贪心算法

目的：解决最优解问题

当一个问题的最优解包含其子问题的最优解时，它可能是动态规划问题或者是贪心算法问题。（最优子结构性质）。若整体最优解可以通过一系列局部最优的选择来达到，则为贪心算法问题。（贪心选择性质）

graph LR

A[最优子结构] --> B(贪心选择)

B --> C(贪心算法问题)

A --> D(非贪心选择)
D --> E(动态规划问题)

条件：由局部最优可以实现整体最优；无后效性；

多数贪心问题可由DP求解，但不能说全部

贪心算法求解步骤

将问题分解为若干个子问题
找出合适的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

刷题记录

leetcode406：根据身高重建队列

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>(){
            public int compare(int[] people1 , int[] people2){
                if(people1[0] != people2[0]){
                    return people2[0] - people1[0];
                } else{
                    return people1[1]-people2[1];
                }
            }
        });
        List<int[]> peoplePro = new ArrayList<int[]>();
        for(int[] person : people){
            peoplePro.add(person[1], person);
        }
        return peoplePro.toArray(new int[peoplePro.size()][]);
    }
}

贪心目的：两种排序方式：高矮和前方人数

子问题：将每个人都放到队列合适的位置！首先按高矮（person[0]）进行排序，问题变成第 $i$ 个人（$h_{i-1}$ , $k_i$）的位置的最优分配

高矮按升序排序

先看身高不同的：
- 排在i前面的无论在放在队列的什么位置，都不会影响i的ki值
- 排在i后面的，如果想要放在i前面，就一定会使ki的值发生改变
所以i前面一定预留有ki个空位给比他高的人，也就意味着i可以占据第ki+1个空着的位置！

再看看身高相同的情况：
- 和前面一样需要遵循i给后面的人留位置的原则，因此相同身高的人，排在前面的是ki大的，需要给排在后面ki小的留位置，同样满足ki+1的原则！

总结：每个人只需要根据他的ki锁定他要占的空位就好！

4. DFS+回溯算法

4.1 深度优先搜索（DFS）

原理：

求解结果遵循先后顺序，后一个结果多数取决于前一个结果的选取。此时就可以通过一个树模型来模拟结果的求解。

例题：46.全排列树形图可以看做

graph LR
A[1]-->B[2]
A[1]-->C[3]
B-->D[3]
C-->E[2]

求解步骤：dfs()方法怎么写？

大方向就是分层解决，dfs方法其实就是实现对每一层的处理，然后通过递归解决下一层，直到达到截止条件返回结果。

截止条件dfs(index)：一共就3个数，遍历到第三层截止
候选人名单dfs(int p[])：[1,2,3]，每一层都对这三层进行遍历，选出一个之前没选过的，然后执行下一层，下一层执行结束之后再将该层恢复（以求回溯）
筛选条件dfs(bollean pb[])：[false; false; false]，对应候选人名单，选过的就将对应的pb值改为true，后面的层不能再选

class Dfs{
	public void dfs(int[] p, boolean pb[], index, int res[]){
		//截止条件
        if(index == p.length+1)
	}
}

深度优先搜索（DFS）的应用：

以马踏棋盘游戏为例：棋盘为8*8的网格，棋子的行进路线为“日”字，如何让棋子能够走完整张棋盘的每个格子？

1.思路：

下一步：设置一个数组nextStep，存放当前棋子下一次可以移动到的格子的point
已访问：从数组中取出一个点，移动棋子至该点，并将访问到的格子point设置为已访问（可以再定义一个数组visited，将visited[x*X+y]改为true）；
继续1，已访问的跳跳过
在循环while(!nextStep.isEmpty())中递归调用以上3步

2.总而言之：

将现在的位置视为原点，将下一步能走的点都放入队列，从队列头取出一个
走出这一步，再以这一步为原点，将下一步能走的点都放入队列，从队列头取出一个

——深度优先由此而来
。。。。。。直到走到某个点，走到头了，没有下一步了
但是循环没结束呢，然后继续从队列中取点，又开始了上面的步骤

——递归调用时访问队列中的全部点也就是回溯的过程

3.2020-11-02：修正：以上思路存在问题

注意是递归调用，原有想法中的每次把能走的位置全部放入队列，然后每次把队列全部调用出来是错误的。调用next函数只需要考虑本次的可行格子就可以。

递归调用的方法是：“找到下一步的可行格子，判断格子是否走过，取出队列中的第一个格子，跳到这一格”。

在递的过程中执行的深度优先策略
在归的过程中，他会将每一次未执行完的while循环继续执行

4.优化：贪心算法

注意到在“将下一步可行的格子放入数组”这一方法中，可以对格子加以排序，让棋子每次都按照“跳完这一步，下一步能跳的格子很少”

这一局部优化方式执行，这样它往回递归的次数无疑是会降低的。

执行，这样它往回递归的次数无疑是会降低的。