Eachone

Algorithm

下面是数据结构的知识基础，基础知识以王道数据结构为基础，但是有所简略，又有所拓展：

什么是数据

数据：数据是信息的载体，是描述客观事物属性的数，字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料

数据元素、数据项：

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。

数据结构这个学科着重关注的是数据元素之间的关系，和对这些数据元素的操作，而不关心具体的数据项内容。

逻辑结构

逻辑机构：数据元素之间的逻辑关系是什么？

集合：各个元素同属一个集合，别无其它关系。

线性结构：所有的数据元素之间都是一对一的关系。除了第一个元素，所有的元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。

树形结构：数据元素之间是一对多的关系。

图结构：数据元素之间是多对多的关系。

数据的运算

数据的运算：针对于某种逻辑结构，结合实际需求，定义基本运算。

线性结构的基本运算：

  1. 查找第i个数据元素
  2. 在第i个位置插入新的数据元素
  3. 删除第i个位置的数据元素
  4. 改变第i个位置的数据元素
数据的物理结构

如何用计算机表示数据元素的逻辑关系？

顺序存储：把逻辑上相邻的元素储存在物理位置也相邻的存储单元中，元素之间的关系有存储单元的领接关系来体现。

链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助知识元素存储地址的指针来表示元素之间的逻辑关系。

索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引表，索引表中的每项称为索引项，索引项的一般形式是关键字，地址。

散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（hash）存储。

数据结构的三要素：
  1. 若采用顺序存储，则各个元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。
  2. 数据的存储结构会影响存储空间分配的方便程度
  3. 数据的存储结构会影响对数据运算的速度。

运算的定义是针对逻辑结构的，指出运算的功能。

运算的实现是针对存储结构的，指出运算的具体操作步骤。

数据类型和抽象数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。-有点像群论

1）原子类型。其值不可在分的数据类型。（int，boolean）

2）结构类型。其值可以再分解为若干成分（分量）的数据类型（class）。

抽象数据类型：是抽象数据组织及与之相关的操作。

抽象数据类型其实就是对数据结构的逻辑结构和运算的描述。

程序 = 数据结构 + 算法

算法

定义：是对特定问题求解步骤的一种描述，它是指令的优先序列，其中的每条指令表示一个或多个操作。

特性

有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。（算法可以是有穷的，程序是无穷的）

确定性：算法中的每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。

输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

“好算法”的特质

1）正确性

2）可读性

3）健壮性

4）高效率与低存储量需求

算法时间开销的评估

我们只需要保留，在复杂度表达式当中的，最高阶的项即可。

加法规则就是挑出阶的项

乘法规则是挑出乘出来阶数最大的项。下面是复杂度的一些直观比较。

算法时间开销的评估

空间复杂度的计算和时间复杂度类似，只需要关注和规模有关的变量的最高阶即可（n）。用对应的字节数乘以在内存中用到的数据就可以了。

需要注意递归带来的内存开销，每次调用函数的时候都需要在内存中放入对应的变量。其中，空间复杂度=递归调用的深度。然后如果里面的变量也跟n有关的话，那么就另分情况讨论。

线性表的定义

线性表是具有相同数据类型的n（n>0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。

基本操作如下：

顺序表的定义：

本笔记中的代码都会用c++来实现，下面是静态分配情况下，init函数的简单实现，其中最大的顺序表的最大长度为10。

#include <iostream>
#define MaxSize 10
using namespace std;

typedef struct{
	int data[MaxSize];
	int length;
}SqList;

void InitList(SqList &L){
	for(int i = 0; i < MaxSize; i++){
		L.data[i] = 0;
	}
	L.length = 0;
}

int main()
{
   SqList L;
   InitList(L);
   //.....Other operation
}

c++当中，如果随意访问自动初始化的内存空间的话，可能会访问到之前存储的脏数据（一些毫无意义的数据）。

下面是动态分配内存的顺序表的实现。

上面是这段代码的图解。*p代表着指向某一内存的指针，可以有很多个。

#include <iostream>
#include <stdlib.h>
#define InitSize 10
using namespace std;

typedef struct{
    int *data;
    int length;
    int MaxSize;
}SqList;

void InitList(SqList &L){
    L.data = (int *)malloc(InitSize*sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

void IncreaseSize(SqList &L, int len){
    int *p = L.data;
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i = 0; i < L.length; i++){
        L.data[i] = p[i];
    }
    L.MaxSize = L.MaxSize + len;
    free(p);
}

顺序表的特点：

  1. 随机访问，即可以在o（1）时间内找到第i个元素
  2. 存储密度高，每个节点只存储数据元素
  3. 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也会比较高）
  4. 插入，删除操作不方便，需要移动大量元素
顺序表的插入和删除：

插入操作：在表L当中的第i个位置上插入指定元素e。

根据线性表的特性可知，想要插入数据有些困难，我们需要把所有在目标位置后面的数据往后面移动一位，才能实现这个功能。

下面是C++的实现。

bool ListInsert(SqList &L, int i, int e){
    if(i < 1 || i > L.length + 1)
        return false;
    if(L.length >= L.MaxSize)
        return false;
    for(int j = L.length; j >= i; j--){
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

复杂度分析：因为这里面每次需要操作的数据量不一样，所以我们取平均情况作为我们的复杂度依据。O（n） = n/2

删除操作：与插入非常类似，直接展示代码。

bool ListDelete(SqList &L, int i, int &e){
    if(i < 1 || i > L.length)
        return false;
    e = L.data[i - 1];
    for(int j = i; j < L.length; j++){
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

时间复杂度和插入一致。

顺序表的查找

顺序表的按位查找：

int GetElem(SqList &L, int i){
	return L.data[i-1];
}

时间复杂度为：O（1）

按值查找：

int LocateElem(SqList L, int e){
    for(int i = 0; i < L.length; i++){
        if(L.data[i] == e){
            return i + 1;
        }
    }
    return 0;
}
链表

单链表的定义：

下面的代码都会以int作为数据类。

创建一个单链表：

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode, *LinkList

一般我们用带头节点的方法来初始化链表,下面是代码

bool InitList(LinkList &L){
	L = (LNode *) malloc(sizeof(LNode));
	if (L == NULL)
		return false;
	L -> next = NULL;
	return true;
}

按位序插入（带头节点）的代码如下

bool ListInset(LinkList &L, int i, int e){
if(i < 1) 
     return false; LNode *p; int j = 0; p = L; 
while(p != NULL && j < i-1)
{
p = p->next;
j++;
}
if(p == NULL)
     return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}

平均时间复杂度是O(N)

指定节点的后插操作,即在指定节点之后插入数据。

bool InsertNextNode(LNode *p, int e){
    if(p ==NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL)
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

前插操作

bool InsetPriorNode(LNode *p, LNode *s){
	if(p == NULL || s == NULL){
		return false;
	}
	s->next = p->next;
	p->next = s;
	int temp = p->data;
	p->data = s->data;
	s->data =temp;
	return true;

}

按位序删除

bool ListDelete(LinkList &L, int i, int &e){
	if(i<1)
		return false;
	LNode *p;
	int j = 0;
	while(p != NULL && j < i-1){
		p = p->next;
		j++;
	}
	if(p->next == NULL){
		return false;
	}
	LNode *q = p->next;
	e = q -> data;
	p->next = q->next;
	free(q);
	return true;
}

单链表的按序查找代码如下：

LNode* GetElem(LinkList L, int i){
	int j = 1;
	LNode *p = L->next;
	if(i == 0)
		return L;
	if(i < 1)
		return NULL;
	while(p != NULL && j < i){
		p = p -> next;
		j++;
	}
	return p;
}

单链表的按值查找代码如下：

LNode* LocateElem(LinkList L,int e){
		LNode *p = L->next;
		while(p->next != NULL && p->data != e){
			p = p->next;
		}
		return p;
}

求单链表的长度：

int Length(LinkList L){
	if(L == NULL)
		return 0;
	int len = 1;
	LNode *p = L;
	while(p->next != NULL){
		p = p->next;
		len++;
	}
	return len;
}

在列表尾批量插入元素：

LinkList List_TailInsert(LinkList &L){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *r = L;
	scanf("%d",&x);
	while(x != 9999){
		s = (LNode*)malloc(sizeof(LNode));
		s -> data = x;
		r->next=s;
		r=s;
		scanf("%d",&x);
	}
	r->next = NULL;
	return L;
}

通过头插法建立单链表：

LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	scanf("%d",&x);
	while(x != 9999){
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s->next;
		scanf("%d",x);
	}
	return L;

}

上面代码的主要考点就是链表的逆置。

双链表

每个节点当中包含上一个节点的地址值的节点，我们叫做双节点。

定义与初始化代码如下：

#include <iostream>
using namespace std;

typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode, *DLinklist;

bool InitDLinkList(DLinklist &L){
	L = (DNode *) malloc(sizeof(DNode));
	if(L==NULL)
		return false;
	L->prior = NULL;
	L->next = NULL;
	return true;
}

双链表的插入：

bool InsertNextDNode(DNode *p, DNode *s){
	if(p == NULL || s == NULL)
		return false;
	s->next = p->next;
	if(p->next != NULL)
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

双链表的前插可以通过在目标节点的前一个节点的后插来决定。

下面是删除p节点的后继节点的代码，以后删除节点的话，只需要利用这个代码的变种即可。

bool DeleteNextDNode(DNode *p){
	if(p == NULL)	 return false;
	DNode *q = p->next;
	p->next = q.next;
	if(q.next != NULL) q->next->prior = p;
	free(q);
	return true;
}

销毁链表的方法：

void DestoryList(DLinklist &L){
while(L->next != NULL)
DeleteNextDNode(L);
free(L);
L=NULL;
}

其实就是循环调用了删除后继节点的方法。

循环链表
静态链表

栈

栈（stack）是只允许在一端进行插入或删除操作的线性表。

重要术语：栈顶，栈底，空栈。

特点：后进先出（Last In First Out）

下面是线性栈的c语言代码：

#include <iostream>
using namespace std;

// 定义栈的最大容量
#define MAX_SIZE 100

class Stack {
private:
    int top; // 栈顶指针
    int arr[MAX_SIZE]; // 栈数组

public:
    // 构造函数
    Stack() {
        top = -1; // 初始化栈顶指针为-1
    }

    // 入栈操作
    void push(int val) {
        if (top >= MAX_SIZE - 1) { // 栈满
            cout << "栈已满，无法入栈！" << endl;
            return;
        }
        arr[++top] = val; // 将值压入栈顶并更新栈顶指针
        cout << val << " 入栈成功！" << endl;
    }

    // 出栈操作
    int pop() {
        if (top < 0) { // 栈空
            cout << "栈为空，无法出栈！" << endl;
            return -1;
        }
        int val = arr[top--]; // 获取栈顶元素并将栈顶指针向下移动
        cout << val << " 出栈成功！" << endl;
        return val;
    }

    // 返回栈顶元素
    int peek() {
        if (top < 0) { // 栈空
            cout << "栈为空！" << endl;
            return -1;
        }
        return arr[top];
    }

    // 判断栈是否为空
    bool isEmpty() {
        return (top < 0);
    }
};
队列

定义：一种操作受限的线性表，只允许在一端进行插入，在另一段删除的线性表。

特点：先进先出（First In First Out）

下面是队列的相关代码包括增删改差，销毁和创造。

#include <iostream>
using namespace std;

// 定义队列的最大容量
#define MAX_SIZE 100

class Queue {
private:
    int front, rear; // 队列的前端和后端指针
    int arr[MAX_SIZE]; // 队列数组

public:
    // 构造函数
    Queue() {
        front = -1; // 初始化前端指针为-1
        rear = -1; // 初始化后端指针为-1
    }

    // 入队操作
    void enqueue(int val) {
        if (rear == MAX_SIZE - 1) { // 队列满
            cout << "队列已满，无法入队！" << endl;
            return;
        }
        if (front == -1) // 如果队列为空，初始化前端指针
            front = 0;
        arr[++rear] = val; // 将值加入队列末尾并更新后端指针
        cout << val << " 入队成功！" << endl;
    }

    // 出队操作
    int dequeue() {
        if (front == -1 || front > rear) { // 队列空
            cout << "队列为空，无法出队！" << endl;
            return -1;
        }
        int val = arr[front++]; // 获取队列前端元素并更新前端指针
        cout << val << " 出队成功！" << endl;
        return val;
    }

    // 返回队头元素
    int peek() {
        if (front == -1 || front > rear) { // 队列空
            cout << "队列为空！" << endl;
            return -1;
        }
        return arr[front];
    }

    // 判断队列是否为空
    bool isEmpty() {
        return (front == -1 || front > rear);
    }
};

在创造循环队列的时候，如果我们不利用一个辅助变量的话，我们往往要牺牲掉一个储存空间。

双端队列

双端队列：代表只允许从两端插入，两端删除的线性表。

双端队列有下面几种类型：

卡特兰数：指在随意排列的序列当中，栈合法的序列的个数。

栈在计算机表达式当中的应用：

下面是后缀表达式的手撕方法：

由上图可知，后缀表达式的符号排序和中缀表达式当中的运算顺序高度一致。

我们在计算的过程当中一般遵守“左优先”原则，即在相同等级的运算当中，左边的运算符号优先级更大。

下面是如何用计算机的栈来实现后缀表达式的计算：

下面是计算机如何将中缀表达式转换为后缀表达式的。（这一段比较重要）

有了上面计算整个的后缀表达式的铺垫，我们就可以用计算机来计算中缀表达式了。

计算机拿到中缀表达式，首先会执行将中缀表达式变成后缀表达式的操作，然后在运行过程当中将得到的部分后缀表达式压入运算栈当中进行计算。

其中，每当运算符出栈的时候，就说明他就要起作用了，他就会将在操作数栈里面的前两个元素取出，并且进行对应的运算。

栈内存在递归当中的应用。

函数调用的特点，最后被调用的函数最先之行结束（LIFO）

函数调用时，需要用一个栈存储：

  1. 调用返回地址
  2. 实参
  3. 局部变量

适合用“递归算法”来解决的问题：可以把原始问题转换为属性相同，但是规模较小的问题（最典型的就是斐波那契数列）

队列的应用：

广度优先搜索。

在操作系统当中的先来先服务（FCFS）的进程调度算法。

特殊矩阵的压缩存储

一维数组只需要用一个线性表来存储即可。

我们只需要记住起始地址：LOC就可以访问所有的元素。

二维数组有两种存储方法：行优先和列优先。

按行存储的方法：

定义一个二维数组b[m][n](m为行，n为列) LOC为起始地址。

b[i][j]的存储地址 = LOC + (i*N+j) * sizeof(ElemType)

按列存储的方法：

定义一个二维数组b[m][n] LOC为起始地址。

b[i][j]的存储地址 = LOC + (j*M + i) * sizeof(ElemType)

普通矩阵可以用数组来存储，对于一些特殊的矩阵，我们可以通过压缩存储空间来进行存储。

我们可以将一个对称矩阵变成一个一维数组，这个数组的大小是：（1+n）*n/2

其中，每一个元素的下标为：

公式解释：把所有的前面行的元素都统计起来，然后加上列坐标再减去一就是在数组中的索引。

三角矩阵的存储：

操作方法和对称矩阵一摸一样，只是需要存储数组的最后一个元素变成原矩阵的常量c就可以了，所以这里上三角的下标就是n*（n+1）/2

三对角矩阵的压缩存储：

这里面我们0并不需要存储，然后在计算下标的时候要减去每一行i（i>2）的前面的0 也就是i-2，然后上面的式子就解释的通了。

根据下标和矩阵行数的关系，我们可以列出下面不等式：

其中3（i-1）-1 是前i-1行的元素个数，3i-1是第i行的元素个数。

3（i-1）-1 < k+1<=3i-1

然后我们利用k算出来，并且向上取整：

i = （k+2）/ 3

就得到了该元素所在的行数，然后利用最上面算矩阵坐标的公式就可以还原矩阵。

稀疏矩阵的压缩：

稀疏矩阵是指0的数目远大于矩阵元素的矩阵。

我们可以通过只存储矩阵元素来节省空间。

另一种是十字链表法：

即我们可以只存储行列和，然后每个节点都有他对应的行和列，每一个矩阵元素都会被对应的行列元素的节点所指向。

顺序存储适用于稀疏度不是很高的情况，而十字链表法则更适合于稀疏度较高的情况，它们各自有着不同的优势和适用场景。

串

串的定义：串即是字符串（String）是有零个或者多个字符组成的优先序列。一般记为S=“a1a2a3….an”

其中，S是串名，单括号括恰里的字符序列是串的值；ai可以是字母，数字或其他字符，串中自负的个数n称为串的长度。n=0时的串称为空串。（用空集符号来表示）。

串是一种特殊的线性表。串的数据对象限定为字符集。

对于串的增删改操作，一般是以“子串”为对象的。

其中这里面的字符串比较，是通过每一位的字符的ascii码，进行比较的，其次，字符串的长度越长，字符串越大（在前面都相同的情况下）

串的存储顺序：

c语言用的是第三种，王道书里面是第四种。

字符串的链式存储：

下面是subString的c代码实现：

#include <stdio.h>
#include <stdbool.h>

// 假设 SString 是一个包含字符数组和长度的结构体
typedef struct {
    char ch[100]; // 假设最大长度为 100
    int length;
} SString;

bool SubString(SString *Sub, SString *S, int pos, int len) {
    if (pos < 1 || pos + len - 1 > S->length)
        return false;
    
    for (int i = pos - 1, j = 0; j < len; i++, j++) {
        Sub->ch[j] = S->ch[i];
    }
    Sub->ch[len] = '\0'; // 在子串的末尾添加空字符
    Sub->length = len;
    return true;
}

下面是StrCompare的基本实现：

下面是定位操作的实现：

字符串的模式匹配

字符串的模式匹配就是在主串中找到与模式串相同的子串，并返回其所在位置。

朴素模式匹配算法：暴力解。

如果主串长度为n，模式串长度为m，将所有长度为m的子串（最多为n-m+1）一次与模式串进行对比，知道找到一个完全匹配的子串，或所有子串都不匹配为止。

最坏的时间复杂度是O（mn）

KMP算法

kmp算法的核心思想就是next数组，用空间来换时间，next数组是和模式字符串相对应的，也就是说，每一模式字符串对应着一个next数组。next数组表示一个指针在当前位置下这个子串前缀和后缀相同的大小。比如abcabc当j指到[5]的时候，next里面的值就应该是3。原字符串里面的指针i永远不需要回溯，我们在next数组里面存储了可以提供继续运算的后缀（因为和前缀相同），这样就实现了整个的kmp算法。c语言当中的数据结构比较灵活，实现的方法也各不相同。这里我还是用java来实现，更好理解一点：

public int indexOf(String source, String pattern) {
            int i = 0, j = 0;
            char[] src = source.toCharArray();
            char[] ptn = pattern.toCharArray();
            int sLen = src.length;
            int pLen = ptn.length;
            int[] next = getNext(ptn);
            while (i < sLen && j < pLen) {
                // 如果j = -1,或者当前字符匹配成功(src[i] = ptn[j]),都让i++,j++
                if (j == -1 || src[i] == ptn[j]) {
                    i++;
                    j++;
                } else {
                    // 如果j!=-1且当前字符匹配失败,则令i不变,j=next[j],即让pattern模式串右移j-next[j]个单位
                    j = next[j];
                }
            }
            if (j == pLen)
                return i - j;
            return -1;
        }
        public int[] getNext(char[] p) {
            // 已知next[j] = k,利用递归的思想求出next[j+1]的值
            // 如果已知next[j] = k,如何求出next[j+1]呢?具体算法如下:
            // 1. 如果p[j] = p[k], 则next[j+1] = next[k] + 1;
            // 2. 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1,
            // 如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止
            int pLen = p.length;
            int[] next = new int[pLen];
            int k = -1;
            int j = 0;
            next[0] = -1; // next数组中next[0]为-1
            while (j < pLen - 1) {
                if (k == -1 || p[j] == p[k]) {
                    k++;
                    j++;
                    next[j] = k;
                } else {
                    k = next[k];
                }
            }
            return next;
        }
树

树是n（n>=0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一颗非空树中应满足：

  1. 有且仅有一个特定的称为根的节点
  2. 当n > 1时，其余节点可分为m（m>0）个互不相交的有限集合T1，T2，…..，Tm，其中每个集合本身又是一棵树，并且称为根节点的子树。

有序树和无序树：

有序树的定义是：逻辑上看，书中节点的各子树从左至右是有次序的，不可互换。

无序树的定义是：逻辑上看，书中节点的各子树从左至右是无次序的，可以互换。

树性质：

结点的度：节点数=总度数+1

节点的度–节点有几个孩子。

高度为h的m叉树至多有(m^h-1)/m-1个节点。

高度为h的m叉树至少有h个节点。

高度为h，度为m的树至少有h+m-1个节点。

二叉树

二叉树是n（n>=0）个节点的有限集合

  1. 或者为空二叉树，即n=0.
  2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一个二叉树。

几种特殊的二叉树：

满二叉树：

一颗高度为h，且含有2^h-1个结点的二叉树。

特点：

  1. 只有最后一层又叶子结点
  2. 不存在度为1的结点
  3. 按层序从1开始编号，结点i的左孩子为2i，又孩子为2i+1；结点i的父结点为[i/2]

完全二叉树：

当且仅当其每个节点都与高度为h的满二叉树中的编号为1-n的结点一一对应时，称为完全二叉树。（就是从满二叉树的叶子结点当中从大往小去掉一些叶子结点，剩下的结点仍然满足满二叉树的标号规则，则称这棵树为完全二叉树）

特点：

  1. 只有最后两层可能有叶子结点
  2. 最多只有一个度为1的结点
  3. 同左3

二叉排序树：

左子树上的所有结点的关键字均小于跟结点的关键字；

右子树上的所有结点的关键字均大于根结点的关键字；

左子树和右子树又各是一颗二叉搜索树。

同时左子树和右子树分别都是二叉排序树。

平衡二叉树：

树上任一结点的左子树和右子树的深度之差不超过一。

这个树的目的是让树变得更加低矮，粗壮，从而提升查询的效率。

一些比较有意思的定律：

书的结点数=总度数 + 1

然后因为 n = n0 + n1 + n2. n = n1 + 2n2 + 1

所以n0 = n2 + 1

高度为h的二叉树至多有2^h – 1个结点（满二叉树）

二叉树的存储结构：

下面是二叉树顺序存储的c语言代码：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结点
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 创建新结点
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入结点
struct TreeNode* insertNode(struct TreeNode* root, int value) {
    if (root == NULL) {
        root = createNode(value);
    } else {
        if (value < root->data) {
            root->left = insertNode(root->left, value);
        } else {
            root->right = insertNode(root->right, value);
        }
    }
    return root;
}

// 打印二叉树（中序遍历）
void printTree(struct TreeNode* root) {
    if (root != NULL) {
        printTree(root->left);
        printf("%d ", root->data);
        printTree(root->right);
    }
}

// 释放二叉树内存
void freeTree(struct TreeNode* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int main() {
    struct TreeNode* root = NULL;

    // 插入结点
    root = insertNode(root, 10);
    root = insertNode(root, 5);
    root = insertNode(root, 15);
    root = insertNode(root, 7);
    root = insertNode(root, 3);
    root = insertNode(root, 12);

    // 打印二叉树
    printf("Binary Tree: ");
    printTree(root);
    printf("\n");

    // 释放二叉树内存
    freeTree(root);

    return 0;
}
二叉树先/中/后序遍历：

乐扣上面都写过，这里就不再展开。

二叉树的层序遍历：

就是广度优先搜索（bfs）

由遍历序列来构造二叉树

如果只给出一棵二叉树的前中后序遍历中的一种，不能为宜确定一棵二叉树

必须要至少两种遍历序列，并且其中一种必须得是中序遍历才可以确定一个二叉树。

后面的以此类推。

线索二叉树

线索二叉树的目的是为了找前后继更加方便。

这边都只展示中序二叉树。

下面是线索二叉树的代码展示：

这个部分其实并不是特别难，根据前中后序遍历的性质，只需要临场推算一下即可。

树的存储结构

这边是普通的树的存储结构

顺序存储的双亲表示法：

删除叶子结点很简单，但是如果不是叶子结点的话，那么就需要将其所有的子树全部删除。

孩子表示法：

缺点：找双亲不是特别方便。

下面是最重要的一种处理方法

孩子兄弟表示法：

其中，新生成的二叉树的每个节点的右子树代表着原来树中同层次的树也就是兄弟姐妹结点。左子树代表着原树的每个节点对应的子节点。

这里面的思想和上面的很相似，就是把每个根结点看成是兄弟姐妹结点。

对树和森林的遍历：

对树的遍历是和二叉树是基本上一样的，分为先/中/后根遍历，步骤是差不多的。如果要转换成二叉树然后再进行处理的话，结果也不会改变。

对于森林的遍历，其实可以把每个树进行相应的遍历拼起来，或者直接把它变成二叉树然后再遍历。

上面这些序列在结果上才是等价的。

哈夫曼树

上面是一些重要的相关概念‼️

哈夫曼树的定义：在含有n个带权叶结点的二叉树当中，其中带权路径（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。

下面是哈夫曼树的构建方法：

构建哈夫曼树的过程有很多可能，但是结果都一样。

哈夫曼树的应用场景：哈夫曼编码

为了避免编码的歧义，我们不能让任何一个编码变成另一个编码的前缀。

并查集

逻辑结构–“集合”

将各个元素划分称为若干个互不相交的子集

“查”

“并”：

双亲表示法更加适合并查集，因为可以很容易的实现并和查的操作。

本质上就是树的双亲表示法。

下面是运作流程：

为了一定的查询效率，我们需要

  1. 用根结点的绝对值表示树的结点数
  2. Union操作，让小树合并到大树

优化之后的查询最坏的时间复杂度是O（logn）

Find操作的优化（压缩路径）：

核心思想就是把已经搜索过的结点直接挂到根结点下面，下次查找的时候就很方便了。

图：

有相图和无向图

简单图和多重图：

因为一条边肯定会向一个顶点提供出度，并向另一个顶点提供出度。

无向图当中极大联通子图称为联通分量。（子图必须联通，且饱含尽可能多的顶点和边）

有向图中的极大强联通子图称为有向图的强联通分量。（这里的强联通是指必须要有回路）

生成树和生成森林的应用场景是修路。

边的权，带权图/网

无向完全图–无向图中任意两个顶点之间都存在边。

若无向图的顶点数为n，则|E| 在[0，n(n-1)/2]的范围内。

有向完全图–有向图中任意两个顶点之间都存在方向相反的两条弧。

若有向图的顶点数为n，则|E|在[0，n(n-1)]的范围内。

边很少的图称为稀疏图，反之则叫做稠密图，没有绝对的界限，一般来说

|E|<|V|log|V|时，可以将G视为稀疏图。

树—不存在回路，且连通的无向图，n个顶点的树，必有n-1条边，如果边大于n-1，则一定有回路

有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。

邻接矩阵表示法
临接表

有向图是类似的。

因为无向图会记录两次边。

十字链表存储有向图：

弧其实就是一条边，弧头相同其实就是，边的目的地相同。弧尾相同，其实就是边的出发点相同。

空间复杂度为：O(|V|+|E|)

十字链表法只能够存储有向图。

领接多重表：

空间复杂度为：O(|V|+|E|)，删除边和结点很方便。

图的增删改查都比较简单，针对数组和链表分情况讨论即可。

图的广度优先遍历：

下面是c语言的代码实现：

领接表和领接矩阵遍历的情况可能会不同，引文领接表上面的数据肯定是按照局部增序排列的，而领接矩阵不一样，可能全部随机。

上面的代码就可以解决非联通图的问题，只需要再遍历一次数组，发现是false的结点继续来一遍bfs即可。

对于无向图来说：调用bfs函数的次数=连通分量数

连通分量上面提到过，可以近似的理解为：一个彼此相连的最大局部图。

广度优先生成树：

通过广度优先的顺序来生成的树状数据结构。

这个用不同的存储方式的到的树并不是唯一的。因为领接表有着不唯一性。

广度优先生成森林：

就是将一个图，按照广度优先生成不同的树，就成了广度优先生成森林。

图的深度优先遍历：

有点类似图的先序遍历。

空间复杂度：O（|V|）

时间复杂度：O (|V^2| )

生成树的概念与广度优先搜索类似，这里就不做展开。

最小生成树（最小代价树）

对于一个带权联通无向图G=(V,E)，生成树不同，每棵树的权（即书中所有边上的权值之和）也可能不同，设R为G的所有生成树的集合，若T为R中边饿权值之和最小的生成树，则T称为G的最小生成树（Minimun-Spanning-Tree，MST）

  1. 最小生成树可能有多个，但边的权值之和总是唯一且最小的。
  2. 最小生成树的边树 = 顶点数 – 1. 砍掉一条则不联通，增加一条边则会出现回路。
  3. 如果一个联通图本生就是一棵树，则其最小生成树就是它本身。
  4. 只有联通图才有生成树，非联通图只有生成森林。

下面提到的两种算法都是用来求最小生成树的算法：

Prim算法（普里姆）

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

每次加入了之后就把整体看成一棵树，注意不要出现回路。

Kruskal算法（克鲁斯卡尔）

每次选择一条权值最小的边，使这条边的两头联通（原本已经联通的就不选）

直到左右的节点都连通

下面是实现细节：

每次更新的时候都会改变lowCost和isJoin里面的数值，从而来达到状态转移的目的。

总时间复杂度是O（n^2）

上面的实现用到了并查集。被选择的边的两个顶点会进行并查集的判定，如果不联通就选择该边，然后把两个顶点放到一个集合里面去。

最短路径问题/

单源最短路径问题：一个港口需要向各个城市运送物资，怎么运送最近？

各顶点间最短路径问题：各个城市之间也需要互相往来，相互之间怎么走距离最近？

bfs求最短路径：

是用来解决单源最短路径问题的

这样我们就拿到了源点到每个顶点的最小路径和最小路径的长度。

这个方法只能用于不带权的图。

Dijkstra算法

最短路径问题

这其实和普里姆算法很类似，只是解决的问题不一样，Dijkstra算法的目的是为了获得单源节点到其他节点路径最短的路径树。而普里姆算法是为了获得该图上的最小生成树，也就是想获得联通的树而且各个边的权重加起来最小。前者是一种统筹的视角，后者是一条具体的路径。

复杂度为O（n^2）

Dijkstra算法不适合有负权值的带权图。

Floyd算法

可以用来求得各个顶点之间的最短路径问题。

下面是代码实现：

时间复杂度为：O(N^3)

空间复杂度为：O(N^2)

Floyd算法其实已经考虑了多个节点中介问题，第一个for循环就是拿来解决这个问题的，因为每次的遍历都是在上一个中介节点的最优情况下进行的，只要覆盖掉上一次的答案，就能解决多个中介节点的问题。完整路径的话，应该就是用一次bfs来搜索，相对应的权重即可。

Floyd算法可以解决带负权值的图。

但是带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径。

有向无环图

定义：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）

环路就是指一个图中的某个顶点可不可以通过边回到自身。

拓扑排序：

AOV网（Activity On Vertex NetWork，用顶点表示活动的网）

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
① 每个顶点出现且只出现一次。
② 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
或定义为：拓扑排序是对有向无环图的顶
点的一种排序，它使得若存在一条从顶点A
到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个
拓扑排序序列。

当然，用人话来说就是下面的过程：

要注意的是：如果原图有回路，则不存在拓扑排序序列。

下面是代码实现：

下面是逆拓扑排序的定义：

领接矩阵实现逆拓扑排序更加方便。

AOE网的两个性质：

  1. 只有在某顶点所代表的事件发生后，从该顶点出发的个有向边所代表的活动才能开始；
  2. 你又在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。

在AOE网中仅有一个入度为0的顶点，称为开始顶点（原点），他表示整个工程的开始，也仅有一个出度为0的顶点，称为结束顶点，他表示整个工程的结束。

关键路径：

AOE图当中可能有多个关键路径。指提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

这里是算法刷题页面！！我会同步的更新我每天的刷题进程～

二分查找

二分查找也称折半查找，是在一组有序(升序/降序)的数据中查找一个元素，它是一种效率较高的查找方法。 时间复杂度是O（logN）。（在算法当中log默认以2为底，lg为10，ln为e）。

要求：

1.必须是有序的数组才可以实现二分查找。

2.数据元素通常是数值型，可以比较大小。
3.将目标元素和查找范围的中间值做比较（如果目标元素=中间值，查找结束），将目标元素分到较大/或者较小的一组。通过分组，可以将查找范围缩小一半。
4.重复第三步，直到目标元素=新的范围的中间值，查找结束。

数组的奇偶并不会直接影响到写法，因为在计算机当中，会舍弃掉余数。二分查找最重要的一点就是边界条件问题，即区间的取舍，或左闭右开，或左开右闭。几种方法在时间复杂度上面没有区别，下面展示我写的最顺手的一种方法。


Java:

public static int binaryBasic(int[] arr, int target) {
        int i = 0, j = arr.length - 1;

        while (i <= j) {
            int m = (j + i)>>>1; //一半取整
            if (arr[m] < target) {//目标在右边
                i = m + 1;
            }else if (target < arr[m]) {//目标在左边
                j = m - 1;
            }else {//找到结果
                return m;
            }
        }
    	//找不到，则返回-1
        return -1;
    }

下面是一道例题(Leetcode35)

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:输入: nums = [1,3,5,6], target = 5 输出: 2

示例 2:输入: nums = [1,3,5,6], target = 2 输出: 1

示例 3:输入: nums = [1,3,5,6], target = 7 输出: 4

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0,r = nums.length - 1,ans = nums.length;
        while(l < r){
            int mid = (r - l) / 2 + l;
            if(nums[mid] < target){
               l = mid + 1;
            }else if(nums[mid] > target){
                r = mid - 1;
            }else if (nums[mid] == target){
                return mid;
            }
        }
        if(target > nums[l]){
            return l + 1;
        }
        return l;
    }
}

这里将原式进行了简单变换，使其能够判断插入的位置。这里的while()里面的判断是l < r的原因是可能存在找不到的情况，而且这里面的数据并不重复。

另一道题目则进行了变种。

Leetcode34:

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

示例 2：输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

示例 3：输入：nums = [], target = 0 输出：[-1,-1]

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        int[] res = new int[2];
        
        while(l <= r){
            int mid = (l + r) >> 1;
            if(nums[mid] > target ){
                r = mid - 1;
            }else if (nums[mid] < target){
                l = mid + 1;
            }else{
                // 找到目标值后更新 res
                res[0] = mid;
                res[1] = mid;

                // 向左扩展范围
                while (mid > 0 && nums[mid - 1] == target) {
                    res[0] = --mid;
                }

                // 向右扩展范围
                while (mid < nums.length - 1 && nums[mid + 1] == target) {
                    res[1] = ++mid;
                }

                return res;
            }

        }
        res[0] = -1;
        res[1] = -1;
        return res;
    }
}

这里则需要加上等号，因为我们需要在相等的条件下进行操作，并且数组当中含有重复的数据。总之，二分查找需要我们根据题目的内容灵活的去改变不同的格式，但是思想都有着很大部分的相似。

回溯算法

回溯是递归的副产品，只要有递归就会有回溯。

在学习动态规划（Dynamic programming）之前必须要对递归和回溯算法有着基本的认识。回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。递归非常重要，但是也在中档题目当中主要考察的是细心程度，并不需要对于递归的思维难度言过其实。

下面是我比较喜欢的一些例题，里面含有灵神的一些高级的表达，十分之优美❤️。

LC。2684

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

  • 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。

返回你在矩阵中能够移动的最大次数。

下面是代码：

class Solution {
    private int ans;
    public int maxMoves(int[][] grid) {
        for(int i = 0; i < grid.length; i++){
            dfs(i, 0, grid);
        }
        return ans;
    }
    public void dfs(int i, int j, int[][] grid){
        ans = Math.max(ans,j);
        if(ans == grid[0].length - 1){
            return;
        }
        for(int k = Math.max(i - 1,0); k < Math.min(grid.length, i + 2); k++){
            if (grid[k][j + 1] > grid[i][j]){
                dfs(k, j+1, grid);
            }
          
        }
        grid[i][j] = 0;

    }
}

需要注意这里的上下界的选定，不要将Math的max和min的顺序搞错。大体的思路就是对一个个的情况进行枚举，然后不断的更新ans值。其中这里面涉及到一个”减枝“操作，也就是这一行grid[i][j] = 0; 这一句代码的作用是可以标记所有被搜索过的节点，从而达到减少重复搜索的目的。原理就是有一些路径比较短，然后又和一些路径重合，这样他在所有方法出栈的时候，会将已经访问过的节点标成0，然后因为这里面所有的节点值都是证书，所以被标记的节点便不会再被后来的方法访问。

前缀和

前缀和算法是一种用于高效计算数组前缀和的算法。前缀和是指从数组的起始位置到某一位置的所有元素的和。如果题目给出的是一维数组的话，那么前缀和算法的主要用途就是计算区域内的元素之和。下面是前缀和的一种简单的实现方法，形式无所谓，能够实现即可。

class NumArray {
    int[] sums;

    public NumArray(int[] nums) {
        int n = nums.length;
        sums = new int[n + 1];
        for(int i = 0; i < n; i++){
            sums[i + 1] = sums[i] + nums[i];
        }
    }
}

摘自lc303。

这里前缀和数组sums的长度是n + 1，其目的是避免边界条件的判断，从而来减少代码难度。对于新的nums说，第i个元素就是原数组当中0到i-1的前缀和，索引0就是0，第n + 1 个元素就是数组的总和。创建的时候时间复杂度是O(n)，但在之后的查询过程当中，时间复杂度是O(1)。

差分数组的思想和前缀和数组很相似，差分数组是用来记录当前元素和前一个元素 的差值的数组，主要解决的问题是，当数组存储的数据量很大的时候，该如何来高效地对一整块数据进行简单的加减处理。再其次，差分数组的前缀和即是原数组。

int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
 diff[i] = nums[i] - nums[i - 1];
}


int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
 res[i] = res[i - 1] + diff[i];
}

下面是构造差分数组的代码模版：

// 差分数组⼯具类
class Difference {
 	// 差分数组
 	private int[] diff;
 
 	/* 输⼊⼀个初始数组，区间操作将在这个数组上进⾏ */
 	public Difference(int[] nums) {
 		assert nums.length > 0;//若是空数组则抛异常
 		diff = new int[nums.length];
 		// 根据初始数组构造差分数组
 		diff[0] = nums[0];
 		for (int i = 1; i < nums.length; i++) {
 			diff[i] = nums[i] - nums[i - 1];
 		}
 	}
 	/* 给闭区间 [i,j] 增加 val（可以是负数）*/
 	public void increment(int i, int j, int val) {
 		diff[i] += val;
 		if (j + 1 < diff.length) {
 			diff[j + 1] -= val;
 		}
	}
	/* 返回结果数组 */
 	public int[] result() {
 		int[] res = new int[diff.length];
 		// 根据差分数组构造结果数组
 		res[0] = diff[0];
 		for (int i = 1; i < diff.length; i++) {
 			res[i] = res[i - 1] + diff[i];
 		}
 		return res;
 	}
}
//第三天打卡

快速幂算法

在指数是整数的的情况下，高效的处理浮点数的幂。题目如下：

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例 1：输入：x = 2.00000, n = 10 输出：1024.00000

示例 2：输入：x = 2.10000, n = 3 输出：9.26100

示例 3：输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25

代码解：

class Solution {
    public double myPow(double x, int n) {
        return Math.pow(x,n);
    }
}//大雾= =

咳咳～当然在工程当中我们肯定要避免重复造轮子，但是作为软件工程师，我们也一定要知道底层是什么样子的。

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}

上面就是快速幂的简单实现。原理就是我们通过2这个除数来将算法简化。从原来的底数乘以n次，简化为n/2次。这里面运用到了分治的思想，即将复杂的问题拆分成较小的问题进行求解。还有一个细节就是，对于指数是奇数还是偶数的判断，决定了我们在最后一次乘法的时候要不要多乘一个x。如果从左往右边推的话，很困难。但是如果我们从右边往左边推，就会简单很多，因为如果指数是奇数的话，在栈内存当中前面的计算步骤都和偶数一样，但是最后一次的时候，N是奇数，会多乘以一个x，至此我们就完成了整个的算法实现。

// 第四天打卡

找零问题

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：输入：coins = [1, 2, 5], amount = 11输出：3解释：11 = 5 + 5 + 1

示例 2：输入：coins = [2], amount = 3输出：-1

示例 3：输入：coins = [1], amount = 0 输出：0

这不是一个简单的贪心可以解决的问题，因为他这里面给出的coins是很不规则的，没有任何的规律可言。所以我们几乎要遍历完所有的情况才可能得出正确的答案，但是暴力的递归会导致时间复杂度陡然增加。所以我们一般会考虑记忆化搜索，和动态规划，下面是三者的区别：

递归、记忆化搜索和动态规划是解决计算问题的三种不同方法，各自有其特点和应用场景。以下是对这三种方法的具体分析：

  1. 递归：递归是一种编程技术，它允许函数直接或间接地调用自身来解决问题。递归的优点是代码简洁，逻辑清晰，但缺点是可能会导致大量的函数调用开销，以及在没有优化的情况下可能会重复计算相同的子问题。
  2. 记忆化搜索：记忆化搜索是递归的一种优化方式，它通过存储已经计算过的子问题的结果来避免重复计算，这种存储通常使用一个数组或哈希表（map）来实现。记忆化搜索可以减少计算量，因为它跳过了重复的子问题。但是，它仍然保留了递归的函数调用开销，而且由于使用了额外的存储空间，实际的空间复杂度可能比自顶向上的动态规划要大。
  3. 动态规划：动态规划是一种算法设计策略，它通过将复杂问题分解为更小的子问题，并存储这些子问题的解，从而避免重复计算。动态规划通常是自底向上的过程，从边界条件开始逐步构建出最终解。这种方法可以有效避免重叠子问题，并且可以通过精心设计的递推顺序来减少不必要的计算。动态规划需要严格的计算顺序和对状态之间依赖关系的深入理解。

总的来说，递归是最基础的实现方式，记忆化搜索是递归的优化版，而动态规划则是一种更为高级的算法设计策略，它们三者各有优势和适用场景。在实际应用中，选择哪种方法取决于具体问题的特点和求解的效率需求。

代码参考：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0; //注意这里面的初始化条件。
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

//第五天打卡

元素和最小的山形三元组

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

  • i < j < k
  • nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

这道题用暴力的方法也可以通过，但是一旦卡时间复杂度的话，就不能实现了，所以，O（n^ 3）有点夸张了，这道题目可以使用O（n）复杂度的算法。我们可以用前后缀数组来找到前j项的最小值是多少，或者是后j项的最小值是多少。由于这是一个山峰结构的数据，我们首先可以贪心的找到左右两边最小的元素，然后遍历中间的区域，从而找到最小的峰值，就可以找到整体的最小

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        int[] suf =new int[n];
        suf[n - 1] = nums[n -1];
        for(int i = n-2; i > 1; i--){
            suf[i] = Math.min(suf[i + 1], nums[i]);
        }
        int ans = Integer.MAX_VALUE;
        int pre = nums[0];
        for(int j = 1; j < n - 1; j++){
            if(pre < nums[j] && nums[j] > suf[j+1]){
                ans = Math.min(ans, pre+nums[j]+suf[j+1]);
            }
            pre = Math.min(pre, nums[j]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

suf就是后缀的最小值，代表一个区域内的最小值。这道题目是美丽塔问题的翻版，其题目描述如下：

放暑假咯～回来继续刷题

下面的刷题顺序会跟b站up主代码随想录的顺序一致。