# 线性表

# 顺序表

# 定义

	// 线性表的最大长度
	#define MAXSIZE 10
	typedef struct Stu {
	int score;
	} DataType;

	typedef struct SqList {
	int length;
	DataType data[MAXSIZE];
	} SqList;

# 初始化

	// 初始化
	void init(SqList* sqList) {
	sqList->length = 0;
	}

# 插入

	// 位置 i 插入
	bool insert(SqList* l, int i, int n, DataType data) {
	if (n == MAXSIZE \|\| i < 0 \|\| i > n) {
	return false;
	}
	// 第 i 个元素及以后后移
	for (int j = n - 1; j >= i; j--) {
	l->data[j + 1] = l->data[j];
	}
	// 第 i 个位置插入元素
	*(l + i)->data = data;

	// 长度 + 1
	return l->length++;
	}

# 删除

	// 位置 i 删除
	bool del(SqList& l, int i) {
	int n = l.length;
	if (i < 0 \|\| i > n \|\| n == 0) {
	return 0;
	}
	//i 个元素以后前移
	for (int j = i + 1; i < n; i++) {
	l.data[j - 1] = l.data[j];
	}
	return l.length--;
	}

# 测试

	#include <stdio.h>
	#include <stdlib.h> //malloc 函数的头文件
	#include <iostream>


	void print(SqList* l, int n) {
	for (int i = 0; i < n; i++) {
	printf("%d ", (l->data)[i].score);
	}
	printf("\n");
	}

	int main() {
	SqList* sqList = (SqList*)malloc(sizeof(SqList));
	init(sqList);

	int n = sqList->length;
	print(sqList, n);

	// 插入
	insert(sqList, 0, n, {1});
	n = sqList->length;
	insert(sqList, 0, n, {2});

	n = sqList->length;
	print(sqList, n);

	// 删除
	del(*sqList, 0);

	n = sqList->length;
	print(sqList, n);

	system("pause");
	}

# 链表（双向链表）

# 前提：匿名结构体

下面是两种定义方式的示例：

匿名结构体的定义：
typedef struct {
  int size;
  Node *head, *tail;
} MyLinkedList;
使用方式：
MyLinkedList list;
list.size = 0;
// 其他操作
具有名称的结构体的定义：
typedef struct MyLinkedList{
  int size;
  Node *head, *tail;
} MyLinkedList;
使用方式：
struct MyLinkedList list;
list.size = 0;
// 其他操作
在第一种方式中， MyLinkedList 是作为结构体的别名，你可以直接定义变量并使用它，而不需要再加上 struct 关键字。而在第二种方式中，你需要在定义变量时加上 struct 关键字。

# 定义

	typedef struct Node {
	int v;
	struct Node prev, next;
	} Node;
	typedef struct {
	int size;
	Node head, tail;
	} MyLinkedList;

# 初始化

	Node* nodeCreate(int val) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->next = NULL;
	node->prev = NULL;
	node->v = val;
	return node;
	}

	MyLinkedList* myLinkedListCreate() {
	MyLinkedList* linkedList = (MyLinkedList*)malloc(sizeof(MyLinkedList));
	linkedList->head = nodeCreate(-1);
	linkedList->tail = nodeCreate(-1);
	linkedList->head->next = linkedList->tail;
	linkedList->tail->prev = linkedList->head;
	linkedList->size = 0;
	return linkedList;
	}

# 获取下标为 index 的节点

	// 获取下标 index 的节点
	int myLinkedListGet(MyLinkedList* obj, int index) {
	if (index < 0 \|\| index >= obj->size) {
	return -1;
	}
	// 从右往左
	if (index > obj->size / 2) {
	Node* tail = obj->tail->prev;
	int n = obj->size - 1;
	while (n > index) {
	tail = tail->prev;
	n--;
	}
	return tail->v;
	} else {
	// 从左往右
	Node* head = obj->head->next;
	int n = 0;
	while (n < index) {
	head = head->next;
	n++;
	}
	return head->v;
	}
	}

# 头插法

	// 头插法
	void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
	Node* node = nodeCreate(val);
	node->next = obj->head->next;
	node->next->prev = node;
	node->prev = obj->head;
	obj->head->next = node;
	obj->size++;
	}

# 尾插法

	// 尾插法
	void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
	Node* node = nodeCreate(val);
	node->prev = obj->tail->prev;
	node->prev->next = node;
	obj->tail->prev = node;
	node->next = obj->tail;
	obj->size++;
	}

# 第 index 个位置插入

	// 在第 index 个位置插入
	void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
	if (index < 0 \|\| index > obj->size) {
	return;
	}
	Node* node = nodeCreate(val);
	Node* cur = NULL;
	// 从右往左
	if (index > obj->size / 2) {
	// 可能 index 为 size，说明插入在尾部
	cur = obj->tail;
	int n = obj->size;
	while (n > index) {
	cur = cur->prev;
	n--;
	}
	} else {
	// 从左往右
	cur = obj->head->next;
	int n = 0;
	while (n < index) {
	cur = cur->next;
	n++;
	}
	}
	// 获取 cur 的前驱插入
	node->prev = cur->prev;
	node->prev->next = node;
	node->next = cur;
	cur->prev = node;
	obj->size++;
	}

# 第 index 个位置删除

	// 在第 index 个位置删除
	void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
	if (index < 0 \|\| index >= obj->size) {
	return;
	}
	Node* cur = NULL;
	// 从右往左
	if (index > obj->size / 2) {
	cur = obj->tail->prev;
	int n = obj->size - 1;
	while (n > index) {
	cur = cur->prev;
	n--;
	}
	} else {
	// 从左往右
	cur = obj->head->next;
	int n = 0;
	while (n < index) {
	cur = cur->next;
	n++;
	}
	}
	// 删除 cur
	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	free(cur);
	obj->size--;
	}

# 释放链表

	// 释放链表
	void myLinkedListFree(MyLinkedList* obj) {
	// 首先释放里面的全部元素
	Node* head = obj->head;
	while (head->next) {
	Node* del = head;
	head = head->next;
	free(del);
	}
	free(obj);
	}

# 栈！

# 顺序栈

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

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

	typedef struct {
	int data[MAX_SIZE]; // 存储栈元素的数组
	int top; // 栈顶指针
	} SeqStack;

	// 初始化栈
	void initStack(SeqStack *s) {
	s->top = -1; // 将栈顶指针初始化为 - 1，表示栈为空
	}

	// 判断栈是否满
	int isFull(SeqStack *s) {
	return s->top == MAX_SIZE - 1; // 栈满时，栈顶指针等于栈的最大容量减 1
	}

	// 判断栈是否为空
	int isEmpty(SeqStack *s) {
	return s->top == -1; // 栈空时，栈顶指针为 - 1
	}

	// 入栈
	void push(SeqStack *s, int value) {
	if (isFull(s)) {
	printf("Stack is full, cannot push.\n"); // 栈满时无法入栈
	return;
	}
	s->top++; // 栈顶指针加 1
	s->data[s->top] = value; // 将元素存入栈顶位置
	}

	// 出栈
	int pop(SeqStack *s) {
	if (isEmpty(s)) {
	printf("Stack is empty, cannot pop.\n"); // 栈空时无法出栈
	exit(1); // 异常退出程序
	}
	int value = s->data[s->top]; // 获取栈顶元素的值
	s->top--; // 栈顶指针减 1
	return value; // 返回出栈的元素值
	}

	// 显示栈内元素
	void display(SeqStack *s) {
	if (isEmpty(s)) {
	printf("Stack is empty.\n"); // 栈空时无元素可显示
	return;
	}
	printf("Elements in the stack: ");
	for (int i = s->top; i >= 0; i--) {
	printf("%d ", s->data[i]); // 从栈顶开始逐个打印元素
	}
	printf("\n");
	}

	int main() {
	SeqStack stack;
	initStack(&stack); // 初始化栈

	push(&stack, 1); // 入栈元素 1
	push(&stack, 2); // 入栈元素 2
	push(&stack, 3); // 入栈元素 3
	display(&stack); // 显示栈内元素

	int elem = pop(&stack); // 出栈并获取出栈元素的值
	printf("Popped element: %d\n", elem); // 打印出栈元素的值
	display(&stack); // 显示栈内元素

	return 0;
	}

# 链栈

# 前提

	typedef struct LinkedStack {
	struct LinkedStack* next;
	int data;
	}* LS;

	typedef struct LinkedStack * LS;

	typedef struct LinkedStack {
	struct LinkedStack* next;
	int data;
	} LS;
	// 等价于
	typedef struct LinkedStack LS;

# 方式一（结构体指针）

	typedef struct LinkedStack {
	struct LinkedStack* next;
	int data;
	}* LS;

	bool push(LS* S, int data) {
	LS newS = (LS)malloc(sizeof(struct LinkedStack));
	newS->data = data;
	newS->next = *S;
	*S = newS;
	return true;
	}
	int main(int argc, char const* argv[]) {
	LS s1 = NULL;
	push(&s1, 1);
	printf("%d", s1->data);
	return 0;
	}

# 方式二

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

	typedef struct LinkedStack {
	struct LinkedStack* next;
	int data;
	} LS;

	bool push(LS** S, int data) {
	LS* newS = (LS*)malloc(sizeof(LS));
	newS->data = data;
	newS->next = *S;
	*S = newS;
	return true;
	}

	int main(int argc, char const* argv[]) {
	LS* s1 = NULL;
	push(&s1, 1);
	printf("%d", s1->data);
	return 0;
	}

# 错误方式

	typedef struct LinkedStack {
	LinkedStack* next;
	int data;
	} LS;

	bool push(LS* S, int data) {
	LS* newS = (LS*)malloc(sizeof(LS));
	newS->data = data;
	newS->next = S;
	S = newS;
	return true;
	}
	int main(int argc, char const* argv[]) {
	LS s1 = {};
	push(&s1, 1);
	printf("%d", s1.data);
	}

对于 push 函数的实现存在一个问题。在函数中对 S 的赋值实际上只是将局部变量 S 指向了新的节点，但这不会影响 main 函数中 s1 的值，因为这里传递的是指针的拷贝。为了使修改生效，你需要将 S 作为指针的指针传递进来，或者让 push 函数返回新的指针。

# 队列

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

	#define MAX_SIZE 100

	typedef struct {
	int data[MAX_SIZE];
	int front;
	int rear;
	} Queue;

	// 初始化队列
	void initQueue(Queue* queue) {
	queue->front = -1;
	queue->rear = -1;
	}

	// 检查队列是否为空
	int isEmpty(Queue* queue) {
	return queue->front == -1;
	}

	// 检查队列是否已满
	int isFull(Queue* queue) {
	return (queue->rear + 1) % MAX_SIZE == queue->front;
	}

	// 入队
	void enqueue(Queue* queue, int value) {
	if (isFull(queue)) {
	printf("队列已满，无法入队\n");
	return;
	}
	if (isEmpty(queue)) {
	queue->front = 0;
	}
	queue->rear = (queue->rear + 1) % MAX_SIZE;
	queue->data[queue->rear] = value;
	}

	// 出队
	int dequeue(Queue* queue) {
	if (isEmpty(queue)) {
	printf("队列为空，无法出队\n");
	return -1;
	}
	int value = queue->data[queue->front];
	if (queue->front == queue->rear) {
	queue->front = -1;
	queue->rear = -1;
	} else {
	queue->front = (queue->front + 1) % MAX_SIZE;
	}
	return value;
	}

	// 获取队头元素
	int getFront(Queue* queue) {
	if (isEmpty(queue)) {
	printf("队列为空\n");
	return -1;
	}
	return queue->data[queue->front];
	}

	// 测试队列操作
	int main() {
	Queue queue;
	initQueue(&queue);

	enqueue(&queue, 10);
	enqueue(&queue, 20);
	enqueue(&queue, 30);

	printf("队头元素：%d\n", getFront(&queue));

	int value = dequeue(&queue);
	printf("出队元素：%d\n", value);

	printf("队头元素：%d\n", getFront(&queue));

	return 0;
	}

# 二叉树

# 二叉搜索树变为平衡

# 有序数组转换为 BST

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode() {}
	* TreeNode(int val) { this.val = val; }
	* TreeNode(int val, TreeNode left, TreeNode right) {
	* this.val = val;
	* this.left = left;
	* this.right = right;
	* }
	* }
	*/
	class Solution {
	// 可以中序遍历把二叉树转变为有序数组，
	// 然后在根据有序数组构造平衡二叉搜索树。
	public TreeNode balanceBST(TreeNode root) {
	dfs(root);
	return buildBST(0, list.size() - 1);
	}

	public TreeNode buildBST(int left, int right){
	if (left > right) {
	return null;
	}
	int mid = left + (right - left) / 2;
	TreeNode root = new TreeNode(list.get(mid));
	root.left = buildBST(left, mid - 1);
	root.right = buildBST(mid + 1, right);
	return root;
	}

	List<Integer> list = new ArrayList<>();
	public void dfs(TreeNode root){
	if (root == null) {
	return;
	}
	dfs(root.left);
	list.add(root.val);
	dfs(root.right);
	}
	}

# 手撕 AVL

对当前节点右旋，就是让当前节点的左子树的高度 - 1，右子树的高度 + 1，类似于往右边旋转

什么是平衡二叉树（AVL） - 知乎 (zhihu.com)

	class Solution {
	public TreeNode balanceBST(TreeNode root) {
	// 存放树的高度
	Map<TreeNode, Integer> nodeHeight = new HashMap<>();
	TreeNode newNode = null;
	Deque<TreeNode> stack = new LinkedList<>();
	// 先序遍历
	while (!stack.isEmpty() \|\| root != null) {
	while (root != null) {
	newNode = insert(newNode, root.val, nodeHeight);
	stack.offerLast(root);
	root = root.left;
	}
	root = stack.pollLast();
	root = root.right;
	}
	return newNode;
	}

	// 插入新节点
	public TreeNode insert(TreeNode root, int val, Map<TreeNode, Integer> nodeHeight){
	if (root == null) {
	root = new TreeNode(val);
	nodeHeight.put(root, 1); // 高度为 1
	return root;
	}
	int diff = val - root.val;
	if (diff > 0) {// 往右子树插入
	// 插入后的新节点
	root.right = insert(root.right, val, nodeHeight);
	// 计算 root 的左右孩子的高度差 (从缓存中获取)
	int diffHeight = nodeHeight.getOrDefault(root.right, 0) - nodeHeight.getOrDefault(root.left, 0);
	if (diffHeight > 1) { // 说明不平衡
	//RL 先对 root.right 右旋，然后再对 root 左旋
	if (val < root.right.val) {
	root.right = rotateRight(root.right, nodeHeight);
	}
	//RR 直接对 root 左旋
	root = rotateLeft(root, nodeHeight);
	}else {
	// 可能插入后是平衡的，不需要调整
	// 获取当前节点新高度
	int height = getCurNodeNewHeight(root,nodeHeight);
	// 更新当前节点高度
	nodeHeight.put(root,height);
	}
	}else if(diff < 0) {// 往左子树插入
	// 插入后的新节点
	root.left = insert(root.left, val, nodeHeight);
	// 计算 root 的左右孩子的高度差 (从缓存中获取)
	int diffHeight = nodeHeight.getOrDefault(root.left, 0) - nodeHeight.getOrDefault(root.right, 0);
	if (diffHeight > 1) { // 说明不平衡
	//LR 先对 root.left 左旋，然后再对 root 右旋
	if (val > root.left.val) {
	root.left = rotateLeft(root.left, nodeHeight);
	}
	//LL 直接对 root 右旋
	root = rotateRight(root, nodeHeight);
	}else{
	// 可能插入后是平衡的，不需要调整
	// 获取当前节点新高度
	int height = getCurNodeNewHeight(root,nodeHeight);
	// 更新当前节点高度
	nodeHeight.put(root,height);
	}
	}else{// 不操作
	return root;
	}
	return root;
	}

	// 左旋
	public TreeNode rotateLeft(TreeNode node, Map<TreeNode, Integer> nodeHeight){
	// 指针调整
	TreeNode right = node.right;
	node.right = right.left;
	right.left = node;
	// 更新 node 和 right 的高度
	int nodeNewHeight = getCurNodeNewHeight(node, nodeHeight);
	nodeHeight.put(node, nodeNewHeight);
	// 新的根节点为作为左孩子的 node 和作为右孩子的 right.right 的最大高度 + 1
	int rightNewHegiht = Math.max(nodeHeight.getOrDefault(right.right, 0), nodeNewHeight) + 1;
	nodeHeight.put(right, rightNewHegiht);
	return right;
	}


	// 右旋
	public TreeNode rotateRight(TreeNode node, Map<TreeNode, Integer> nodeHeight){
	// 指针调整
	TreeNode left = node.left;
	node.left = left.right;
	left.right = node;
	// 更新 node 和 left 的高度
	int nodeNewHeight = getCurNodeNewHeight(node, nodeHeight);
	nodeHeight.put(node, nodeNewHeight);
	// 新的根节点为作为左孩子的 node 和作为右孩子的 right.right 的最大高度 + 1 int leftNewHegiht = Math.max (nodeHeight.getOrDefault (left.left, 0), nodeNewHeight) + 1;
	nodeHeight.put(left, leftNewHegiht);
	return left;
	}

	// 获取当前的高度
	public int getCurNodeNewHeight(TreeNode node, Map<TreeNode, Integer> nodeHeight){
	return Math.max(nodeHeight.getOrDefault(node.left,0),nodeHeight.getOrDefault(node.right,0)) + 1;
	}
	}

	class Solution {
	public TreeNode balanceBST(TreeNode root) {
	if (root == null){
	return null;
	}
	//node 节点的高度缓存
	Map<TreeNode,Integer> nodeHeight = new HashMap<>();
	TreeNode newRoot = null;
	Deque<TreeNode> stack = new LinkedList<>();
	TreeNode node = root;
	// 先序遍历插入（其实用哪个遍历都行）
	while(node != null \|\| !stack.isEmpty()){
	if (node != null){
	// 新树插入
	newRoot = insert(newRoot,node.val,nodeHeight);
	stack.push(node);
	node = node.left;
	}else {
	node = stack.pop();
	node = node.right;
	}
	}
	return newRoot;
	}

	/**
	* 新节点插入
	* @param root root
	* @param val 新加入的值
	* @param nodeHeight 节点高度缓存
	* @return 新的 root 节点
	*/
	private TreeNode insert(TreeNode root,int val,Map<TreeNode,Integer> nodeHeight){
	if (root == null){
	root = new TreeNode(val);
	nodeHeight.put(root,1);// 新节点的高度
	return root;
	}
	TreeNode node = root;
	int cmp = val - node.val;
	if (cmp < 0){
	// 左子树插入
	node.left = insert(root.left,val,nodeHeight);
	// 如果左右子树高度差超过 1，进行旋转调整
	if (nodeHeight.getOrDefault(node.left,0) - nodeHeight.getOrDefault(node.right,0) > 1){
	if (val > node.left.val){
	// 插入在左孩子右边，左孩子先左旋
	node.left = rotateLeft(node.left,nodeHeight);
	}
	// 节点右旋
	node = rotateRight(node,nodeHeight);
	}
	}else if (cmp > 0){
	// 右子树插入
	node.right = insert(root.right,val,nodeHeight);
	// 如果左右子树高度差超过 1，进行旋转调整
	if (nodeHeight.getOrDefault(node.right,0) - nodeHeight.getOrDefault(node.left,0) > 1){
	if (val < node.right.val){
	// 插入在右孩子左边，右孩子先右旋
	node.right = rotateRight(node.right,nodeHeight);
	}
	// 节点左旋
	node = rotateLeft(node,nodeHeight);
	}
	}else {
	// 一样的节点，啥都没发生
	return node;
	}
	// 获取当前节点新高度
	int height = getCurNodeNewHeight(node,nodeHeight);
	// 更新当前节点高度
	nodeHeight.put(node,height);
	return node;
	}

	/**
	* node 节点左旋
	* @param node node
	* @param nodeHeight node 高度缓存
	* @return 旋转后的当前节点
	*/
	private TreeNode rotateLeft(TreeNode node,Map<TreeNode,Integer> nodeHeight){
	//--- 指针调整
	TreeNode right = node.right;
	node.right = right.left;
	right.left = node;
	//--- 高度更新
	// 先更新 node 节点的高度，这个时候 node 是 right 节点的左孩子
	int newNodeHeight = getCurNodeNewHeight(node,nodeHeight);
	// 更新 node 节点高度
	nodeHeight.put(node,newNodeHeight);
	//newNodeHeight 是现在 right 节点左子树高度，原理一样，取现在 right 左右子树最大高度 + 1
	int newRightHeight = Math.max(newNodeHeight,nodeHeight.getOrDefault(right.right,0)) + 1;
	// 更新原 right 节点高度
	nodeHeight.put(right,newRightHeight);
	return right;
	}

	/**
	* node 节点右旋
	* @param node node
	* @param nodeHeight node 高度缓存
	* @return 旋转后的当前节点
	*/
	private TreeNode rotateRight(TreeNode node,Map<TreeNode,Integer> nodeHeight){
	//--- 指针调整
	TreeNode left = node.left;
	node.left = left.right;
	left.right = node;
	//--- 高度更新
	// 先更新 node 节点的高度，这个时候 node 是 right 节点的左孩子
	int newNodeHeight = getCurNodeNewHeight(node,nodeHeight);
	// 更新 node 节点高度
	nodeHeight.put(node,newNodeHeight);
	//newNodeHeight 是现在 left 节点右子树高度，原理一样，取现在 right 左右子树最大高度 + 1
	int newLeftHeight = Math.max(newNodeHeight,nodeHeight.getOrDefault(left.left,0)) + 1;
	// 更新原 left 节点高度
	nodeHeight.put(left,newLeftHeight);
	return left;
	}

	/**
	* 获取当前节点的新高度
	* @param node node
	* @param nodeHeight node 高度缓存
	* @return 当前 node 的新高度
	*/
	private int getCurNodeNewHeight(TreeNode node,Map<TreeNode,Integer> nodeHeight){
	//node 节点的高度，为现在 node 左右子树最大高度 + 1
	return Math.max(nodeHeight.getOrDefault(node.left,0),nodeHeight.getOrDefault(node.right,0)) + 1;
	}
	}

# 106. 从中序与后序遍历序列构造二叉树

力扣题目链接 (opens new window)

根据一棵树的中序遍历与后序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：

# #思路

首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来在切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。

那么代码应该怎么写呢？

说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间

流程如图：

左子树后序数组不能用 rootIndex-1 来确定，因为但是当递归起来之后，ps 和 is 不再相等，

后序数组应该用后序数组的下标

	class Solution {
	Map<Integer,Integer> map = new HashMap();// 方便根据数值查找位置

	public TreeNode buildTree(int[] inorder, int[] postorder) {
	for(int i = 0 ; i < inorder.length ; i ++){// 用 map 保存中序序列的数值对应位置
	map.put(inorder[i],i);
	}
	return findNode(inorder,0,inorder.length-1, postorder,0,postorder.length-1);
	}

	public TreeNode findNode(int[] inorder,int inorderBegin , int inorderEnd , int[] postorder ,int postorderBegin , int postorderEnd){
	// 左根右
	//z
	if(inorderBegin > inorderEnd \|\| postorderBegin > postorderEnd){
	return null;
	}
	// 获取根节点
	int rootVal = postorder[postorderEnd];
	// 获取根节点索引
	int rootIndex = map.get(rootVal);

	TreeNode root = new TreeNode(rootVal);

	int lenOfLeft = rootIndex-inorderBegin;// 保存中序左子树节点个数，用来确定后序数列的个数
	root.left = findNode(inorder,inorderBegin,rootIndex-1,
	postorder,postorderBegin, postorderBegin + lenOfLeft -1);
	root.right = findNode(inorder,rootIndex + 1, inorderEnd ,
	postorder,postorderBegin + lenOfLeft ,postorderEnd-1);

	return root;
	}

# 方法二、迭代

更 105 一样，只需从右子树开始。可以先看 105 的解析

	class Solution {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
	Deque<TreeNode> stack = new LinkedList();
	TreeNode root = new TreeNode(postorder[postorder.length - 1]);
	stack.offerFirst(root);
	int index = inorder.length - 1;
	for(int i = postorder.length - 2 ; i >= 0 ; i--){
	TreeNode node = stack.peekFirst();
	if(node.val != inorder[index]){
	node.right = new TreeNode(postorder[i]);
	stack.offerFirst(node.right);
	}else{
	while(!stack.isEmpty() && stack.peekFirst().val == inorder[index]){
	node = stack.pollFirst();
	index --;
	}
	node.left = new TreeNode(postorder[i]);
	stack.offerFirst(node.left);
	}
	}

	return root;
	}
	}

# 105. 从前序与中序遍历序列构造二叉树

力扣题目链接 (opens new window)

根据一棵树的前序遍历与中序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

# #思路

本题和 106 是一样的道理。

我就直接给出代码了。

此图应对与 17 行确定前序数列的个数

	class Solution {
	Map<Integer,Integer> map = new HashMap();
	public TreeNode buildTree(int[] preorder, int[] inorder) {
	for(int i = 0 ; i < inorder.length ; i ++){
	map.put(inorder[i],i);
	}
	return buildTree(preorder,0,preorder.length - 1 , inorder , 0 ,inorder.length - 1);
	}

	public TreeNode buildTree(int[] preorder, int preBegin, int preEnd , int[] inorder, int inBegin, int inEnd) {
	if(preBegin > preEnd \|\| inBegin > inEnd){
	return null;
	}
	int rootIndex = map.get(preorder[preBegin]);
	TreeNode root = new TreeNode(preorder[preBegin]);

	int leftOfLen = rootIndex - inBegin; // 保存中序左子树个数，用来确定前序数列的个数
	root.left = buildTree(preorder,preBegin + 1 , preBegin + leftOfLen , inorder , inBegin , rootIndex - 1);
	root.right = buildTree(preorder,preBegin + leftOfLen + 1 , preEnd , inorder , rootIndex + 1 , inEnd);
	return root;
	}
	}

# 方法二：迭代

	class Solution {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
	Deque<TreeNode> stack = new LinkedList();
	int index = 0;
	TreeNode root = new TreeNode(preorder[0]);
	stack.offerFirst(root);
	for(int i = 1 ; i < preorder.length ; i++){
	TreeNode node = stack.peekFirst();
	//index 对应的中序值，与前序的值不相等，
	if(node.val != inorder[index]){
	node.left = new TreeNode(preorder[i]);
	stack.offerFirst(node.left);
	}else{
	while(!stack.isEmpty() && stack.peekFirst().val == inorder[index]){
	node = stack.pollFirst();
	index++;
	}
	node.right = new TreeNode(preorder[i]);
	stack.offerFirst(node.right);
	}
	}
	return root;
	}
	}

# B 树

# 插入

从根节点开始搜索：
- 如果根节点为空，则将关键字作为新的根节点插入。
- 如果根节点非空，则在树中递归搜索合适的叶子节点。
插入关键字：
- 如果叶子节点未满（关键字个数小于节点容量），则简单地将关键字插入到该节点的有序位置，并将节点中的关键字重新排序。
- 如果叶子节点已满（关键字个数等于节点容量），则需要进行节点分裂操作。
节点分裂：
- 将该节点的所有关键字按顺序排列。
- 找到中间的关键字 mid，并将其提升到父节点中。
- 创建两个新的节点 leftNode 和 rightNode，其中 leftNode 包含 mid 左侧的关键字，rightNode 包含 mid 右侧的关键字。
- 如果该节点是叶子节点，将 leftNode 和 rightNode 作为孩子节点插入父节点，并更新父节点的关键字和孩子指针。
- 如果该节点不是叶子节点，将 leftNode 和 rightNode 作为孩子节点插入父节点，并更新父节点的关键字和孩子指针。
树的调整：
- 如果根节点分裂，需要创建一个新的根节点，并将分裂后得到的两个子节点连接到新的根节点上。
- 如果父节点分裂，需要将父节点的中间关键字提升到祖父节点中，并将分裂后得到的两个子节点连接到新的父节点上。
- 如果一直往上走，直到找到一个不满的节点或者到达根节点为止。

通过递归向下搜索、插入和可能的节点分裂，可以完成 B 树的插入操作。在插入之后，可能需要根据特定的 B 树实现选择性地进行节点合并、旋转或平衡操作，以维护 B 树的平衡性质。

需要注意的是，B 树的插入操作涉及到节点的移动和调整，因此可能会影响树的结构和性能。可根据具体的 B 树实现和需求进行进一步的优化和调整。

# 删除

查找待删除的关键字：
- 从根节点开始，在 B 树中按照搜索规则找到待删除的关键字所在的叶子节点。
- 比较待删除的关键字与当前节点中的关键字，如果小于某个关键字，则进入该关键字左侧的子节点；如果大于所有关键字，则进入最右侧的子节点。
删除操作：
- 在叶子节点中找到待删除的关键字，并将其删除。
- 如果删除后，叶子节点的关键字数量仍满足 B 树的要求（通常为 m/2 向下取整），删除操作结束。
- 如果叶子节点的关键字数量小于最低限度，需要进行节点合并或旋转操作。
节点合并：
- 如果待删除的关键字所在的叶子节点与其相邻的兄弟节点有多余的关键字，可以进行节点合并操作。
- 将待删除的关键字所在节点与一个兄弟节点合并成一个新的节点，并将父节点中对应的关键字下移至新节点。
- 如果父节点的关键字数量也小于最低限度，继续进行节点合并操作。
节点旋转：
- 如果待删除的关键字所在的叶子节点与其相邻的兄弟节点没有多余的关键字，可以进行节点旋转操作。
- 将父节点中的一个关键字下移至待删除关键字所在节点，同时将该关键字所在节点的一个关键字上移至父节点。
- 如果旋转后，父节点的关键字数量仍小于最低限度，继续进行节点旋转操作。
调整树结构：
- 如果发生了节点合并或旋转，需要递归地向上调整 B 树的结构。
- 更新父节点的关键字顺序和指针指向，以保持 B 树的平衡性。
- 如果根节点没有关键字了，将其唯一的子节点作为新的根节点。

# 图

# prim 算法

具体的实现思路如下：

首先构建一个图 g，使用邻接表的形式表示。对于每个节点 i，使用一个 ArrayList<int []> 存储与节点 i 相连的边，每条边是一个 int 数组，包含目标节点 j 和边的权值 w。
初始化最小代价 mCost 为无穷大，mu 和 mv 分别记录最小代价的边的起点和终点。
遍历边集合 edges，将边加入到图 g 中，并更新最小代价的边。
初始化一个集合 set，用于存放已经选择的节点。初始时，将代价最小的边的起点和终点加入到 set 中，并输出该边的信息。
当 set 的大小小于节点数 n 时，进行循环操作：
- 从 set 中选出一个节点 u，遍历节点 u 的邻接边。
- 如果邻接边连接的节点 v 已经在 set 中，跳过该边。
- 否则，更新最小代价 mCost 和对应的起点 mu 和终点 mv，选择剩余最小代价的边。
将终点 mv 加入到 set 中，并输出该边的信息。
循环结束后，得到最小生成树的边集合。

在代码的 main 函数中，构造了一个图 e，并调用 prim 方法进行最小生成树的计算。图 e 的边集合表示了一个具体的图结构，节点数为 6。运行该代码会输出最小生成树的边的信息。

	//edges:[[u,v,w], ], n 为节点数
	public void prim(int[][] edges, int n) {
	// 构建图
	List<int[]>[] g = new ArrayList[n + 1];
	for (int i = 0; i <= n; i++) {
	g[i] = new ArrayList<>();
	}
	int mu = -1, mv = -1, mCost = Integer.MAX_VALUE;
	for (int[] edge : edges) {
	g[edge[0]].add(new int[]{edge[1], edge[2]});
	g[edge[1]].add(new int[]{edge[0], edge[2]});
	// 选取剩余最小代价的节点
	if (mCost > edge[2]) {
	mCost = edge[2];
	mu = edge[0];
	mv = edge[1];
	}
	}
	// 最终集合
	Set<Integer> set = new HashSet<>();
	set.add(mu);
	set.add(mv);
	System.out.println(mu + " " + mv + " : " + mCost);

	while (set.size() < n) {
	// 从 set 中选出节点 u，计算最小代价
	mCost = Integer.MAX_VALUE;
	for (Integer u : set) {
	List<int[]> list = g[u];
	for (int[] v : list) {
	if (set.contains(v[0])) {
	continue;
	}
	// 选取剩余最小代价的节点
	if (mCost > v[1]) {
	mCost = v[1];
	mu = u;
	mv = v[0];
	}
	}
	}
	// 更新
	set.add(mv);
	System.out.println(mu + " " + mv + " : " + mCost);
	}
	}

	public static void main(String[] args) {
	int[][] e = new int[][]<!--swig0-->;
	Solution solution = new Solution();
	solution.prim(e, 6);
	}

# cruskal 算法

具体的实现思路如下：

首先初始化并查集，将每个节点的父节点初始化为自身。
构建一个小根堆 minHeap，用于存放边。按照边的权值从小到大排序。
循环处理 minHeap 中的边，直到 minHeap 为空：
- 从 minHeap 中取出一条边 poll。
- 检查边的两个节点是否已经连通，即判断它们是否在同一个集合中。
- 如果已经连通，跳过该边。
- 否则，合并边的两个节点，并输出该边的信息。
合并操作使用并查集的思想，将两个节点所在集合的根节点连接起来。
查找操作使用路径压缩优化，将节点的父节点设置为根节点，加速后续的查找操作。

在代码的 main 函数中，构造了一个边集合 e，并调用 cruskal 方法进行最小生成树的计算。边集合 e 表示了一个具体的图结构，节点数为 6。运行该代码会输出最小生成树的边的信息。

请问有什么问题我可以帮助你解答的吗？

	class Solution {
	//edges:[[u,v,w], ], n 为节点数
	public void cruskal(int[][] edges, int n) {
	// 初始化并查集
	init(n);
	// 构建小根堆
	PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
	for (int[] edge : edges) {
	minHeap.add(new int[]{edge[0], edge[1], edge[2]});
	}
	while (!minHeap.isEmpty()) {
	int[] poll = minHeap.poll();
	// 检查是否是连通的
	if (find(poll[0]) == find(poll[1])) {
	continue;
	}
	// 合并
	union(poll[0], poll[1]);
	System.out.println(poll[0] + " " + poll[1] + " : " + poll[2]);
	}
	}

	private void union(int i, int j) {
	int l = find(i);
	int r = find(j);
	//l 的父亲指向 r
	father[l] = r;
	}

	private int find(int x) {
	if (x == father[x]) {
	return x;
	}
	// 路径压缩
	return father[x] = find(father[x]);
	}

	int[] father;

	public void init(int n) {
	father = new int[n + 1];
	for (int i = 0; i <= n; i++) {
	father[i] = i;
	}
	}


	public static void main(String[] args) {
	int[][] e = new int[][]<!--swig1-->;
	Solution solution = new Solution();
	solution.cruskal(e, 6);
	}
	}

该代码的时间复杂度为 O (ElogE)，其中 E 表示边的数量。

具体分析如下：

初始化并查集的时间复杂度为 O (n)，其中 n 为节点数。
构建小根堆的时间复杂度为 O (ElogE)，需要将所有边加入堆中，并进行排序。
循环处理小根堆中的边，最多进行 E 次循环。
- 在每次循环中，从堆中取出一条边的时间复杂度为 O (1)。
- 判断边的两个节点是否连通的时间复杂度为 O (1)，通过并查集的 find 操作实现。
- 合并边的两个节点的时间复杂度为 O (1)，通过并查集的 union 操作实现。
- 输出边的信息的时间复杂度为 O (1)。
总体来看，循环处理小根堆中的边的时间复杂度为 O (E)。

综上所述，代码的总体时间复杂度为 O (n + ElogE)。由于 E 可能达到 n^2 级别，因此可以简化为 O (ElogE)。

请注意，这里的时间复杂度分析是基于给定的输入规模，即边的数量 E 和节点数 n。在实际应用中，如果边的数量 E 远大于节点数 n，那么 O (ElogE) 的复杂度会占主导地位。但如果 E 接近于 n^2，那么 O (n + ElogE) 中的 n 项可能会起到更重要的作用。

如果还有其他问题，请随时提问。

# 拓扑排序

这段代码实现了拓扑排序算法，用于对有向无环图（DAG）进行节点排序。拓扑排序的结果可以用于表示图中节点的一种线性排序，其中如果图中存在一条从节点 u 到节点 v 的路径，那么在排序中 u 一定出现在 v 的前面。

具体的实现思路如下：

首先根据输入的边集合 edges 和节点数 n 建立图的邻接表表示（这里使用了 ArrayList 数组 g）。
统计每个节点的入度（即指向该节点的边的数量），并初始化一个入度为 0 的节点队列 q。
将所有入度为 0 的节点放入队列 q 中。
循环处理队列 q 中的节点，每次取出一个入度为 0 的节点 u 并输出该节点。
遍历节点 u 的邻接节点 v，将节点 v 的入度减 1。若节点 v 的入度减至 0，则将节点 v 加入队列 q 中。
最终如果图中存在环（即 c 不为 0），则输出 "构成环"。

在代码的 main 函数中，构造了一个边集合 e，并调用 topologySort 方法进行拓扑排序。边集合 e 表示了一个具体的有向图结构，节点数为 6。运行该代码会输出拓扑排序后的节点顺序。

这段代码的时间复杂度为 O (V+E)，其中 V 表示节点数，E 表示边的数量。具体分析如下：

建图的时间复杂度为 O (E)，需要遍历所有的边。
统计入度的时间复杂度为 O (E)，同样需要遍历所有的边。
拓扑排序的过程中，每个节点和边都会被访问一次，因此时间复杂度为 O (V+E)。因此，总体时间复杂度为 O (V+E)。

如果你有更多问题，欢迎继续向我提问。

	// edge[0] -> edge[1]
	public void topologySort(int[][] edges, int n) {
	// 建图
	List<Integer>[] g = new ArrayList[n];
	for (int i = 0; i < n; i++) {
	g[i] = new ArrayList<>();
	}
	// 只需要统计入度
	int[] degree = new int[n];
	for (int[] edge : edges) {
	g[edge[0]].add(edge[1]);
	degree[edge[1]]++;
	}
	// 首先找到入度为 0 的节点，放入集合 q 中，并开始循环删除
	Deque<Integer> q = new ArrayDeque<>();
	for (int i = 0; i < n; i++) {
	if (degree[i] == 0) {
	q.add(i);
	}
	}
	int c = n;
	// 循环删除
	while (!q.isEmpty()) {
	c--;
	Integer u = q.pollFirst();
	// 输出
	System.out.println(u);
	List<Integer> list = g[u];
	for (Integer v : list) {
	degree[v]--;
	// 加入集合
	if (degree[v] == 0) {

	q.addLast(v);
	}
	}
	}
	if (c != 0) {
	System.out.println("构成环");
	}
	}

	public static void main(String[] args) {
	int[][] e = new int[][]<!--swig2-->;
	Solution solution = new Solution();
	solution.topologySort(e, 6);
	}

# 排序

# 基数排序

# 数组

	class Solution {
	public int maximumGap(int[] nums) {
	/*
	链式基数排序
	先构建一个链表数组，下标依次对应数字下标
	例如: l1 l2 l3 l4 链表数组
	↓ ↓ ↓ ↓
	i1 i2 i3 i4 要排序的数组
	依次对每个数的个位数的值所在的元素放入对应所在的链表中，然后每个链表再还原数组
	例如：192 ，232，123，121
	l1 l2 l3
	↓ ↓ ↓
	121 192 123
	↓
	232
	再还原
	121 192 232 123
	同理对十位数，百位数.... 一样的操作，最后的结果即为排序的结果
	*/
	int maxV = Arrays.stream(nums).max().getAsInt();
	int exp = 1;
	int n = nums.length;
	while (exp <= maxV) {
	int[] arr = new int[n]+
	int[] cnt = new int[10];
	for (int num : nums) {
	//digit : 当前位数
	// - 192, exp = 1, d = 192
	// - 192, exp = 10, d = 19
	int digit = num / exp;
	cnt[digit % 10]++;
	}
	/*
	用于确定下标
	[23, 24, 5, 15, 3]
	cnt [3] = 2, cnt [4] = 1, cnt [5] = 2
	cnt [3] = cnt [3] + 0 : 23, 3 前面有 0 个元素
	cnt [4] = cnt [4] + 2 : 24 前面有 2 个元素
	cnt [5] = cnt [5] + 3 : 5, 15 前面有 3 个元素
	*/
	for (int i = 0; i < 9; i++) {
	cnt[i + 1] += cnt[i];
	}
	/*
	从后往前遍历
	[23, 24, 5, 15, 3]
	cnt [3] = 2, cnt [4] = 3, cnt [5] = 5
	对于 5, 15
	- 15 对应的下标 (4) : cnt [5] - 1, cnt [5]--
	- 5 对应的下标 (3) : cnt [5] - 1, cnt [5]--
	若从前往后遍历
	cnt [5] = 5
	- 导致 5 对应的下标从 3 变为 cnt [5] - 1 = 4
	*/
	for (int i = n - 1; i >= 0; i--) {
	int digit = nums[i] / exp;
	arr[cnt[digit % 10] - 1] = nums[i];
	cnt[digit % 10]--;
	}
	nums = arr;
	exp *= 10;
	}
	int ans = 0;
	for (int i = 1; i < n; i++) {
	ans = Math.max(ans, nums[i] - nums[i - 1]);
	}
	return ans;
	}
	}

c 语言

	int maximumGap(int* nums, int numsSize){
	int n = numsSize;
	// 获取最大数字
	int max = INT_MIN;
	int *p = nums;
	for (int i = 0; i < n; i++) {
	max = fmax(max, *(p + i));
	}
	int exp = 1;
	while (exp <= max) {
	int arr = (int ) malloc(numsSize * sizeof(int));
	//cnt [i] 前面有几个元素
	int cnt = (int ) calloc(10, sizeof(int));
	for (int i = 0; i < n; i++) {
	int digit = nums[i] / exp;
	cnt[digit % 10]++;
	// (*(cnt + digit % 10))++;
	}
	for (int i = 1; i < 10; i++) {
	cnt[i] += cnt[i - 1];
	}

	// 倒序遍历
	for (int i = n - 1; i >= 0; i--) {
	int digit = *(nums + i) / exp;
	arr[cnt[digit % 10] - 1] = nums[i];
	cnt[digit % 10]--;
	}
	free(cnt);
	exp *= 10;
	nums = arr;
	}
	int ans = 0;

	for (int i = 1; i < n; i++) {
	ans = fmax(ans, nums[i] - nums[i - 1]);
	}
	return ans;
	}

# 链式基数排序

	// 链式基数排序
	void radixSort(int* nums, int numsSize) {
	// 注：这是双向链表，head 与 tail 指针为哨兵
	MyLinkedList* arr[10];
	// 初始化
	for (int i = 0; i < 10; i++) {
	arr[i] = myLinkedListCreate();
	}
	// 获取最高位
	int max = INT_MIN;
	for (int i = 0; i < numsSize; i++) {
	max = max(max, nums[i]);
	}
	int exp = 1;
	while (exp <= max) {
	// 分配到指定位置
	for (int i = 0; i < numsSize; i++) {
	int digit = nums[i] / exp % 10;
	// 尾插法
	myLinkedListAddAtTail(arr[digit], nums[i]);
	}
	// 重新排列
	int index = 0;
	for (int i = 0; i < 10; i++) {
	MyLinkedList* cur = arr[i];
	while (cur->size != 0) {
	nums[index++] = cur->head->next->v;
	myLinkedListDeleteAtIndex(cur, 0);
	}
	}
	exp *= 10;
	}
	// 释放链表
	for (int i = 0; i < 10; i++) {
	myLinkedListFree(arr[i]);
	}
	}

双向链表

	typedef struct Node {
	int v;
	struct Node prev, next;
	} Node;
	typedef struct {
	int size;
	Node head, tail;
	} MyLinkedList;

	Node* nodeCreate(int val) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->next = NULL;
	node->prev = NULL;
	node->v = val;
	return node;
	}

	MyLinkedList* myLinkedListCreate() {
	MyLinkedList* linkedList = (MyLinkedList*)malloc(sizeof(Node));
	linkedList->head = nodeCreate(-1);
	linkedList->tail = nodeCreate(-1);
	linkedList->head->next = linkedList->tail;
	linkedList->tail->prev = linkedList->head;
	linkedList->size = 0;
	return linkedList;
	}
	// 获取下标 index 的节点
	int myLinkedListGet(MyLinkedList* obj, int index) {
	if (index < 0 \|\| index >= obj->size) {
	return -1;
	}
	// 从右往左
	if (index > obj->size / 2) {
	Node* tail = obj->tail->prev;
	int n = obj->size - 1;
	while (n > index) {
	tail = tail->prev;
	n--;
	}
	return tail->v;
	} else {
	// 从左往右
	Node* head = obj->head->next;
	int n = 0;
	while (n < index) {
	head = head->next;
	n++;
	}
	return head->v;
	}
	}

	// 头插法
	void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
	Node* node = nodeCreate(val);
	node->next = obj->head->next;
	node->next->prev = node;
	node->prev = obj->head;
	obj->head->next = node;
	obj->size++;
	}

	// 尾插法
	void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
	Node* node = nodeCreate(val);
	node->prev = obj->tail->prev;
	node->prev->next = node;
	obj->tail->prev = node;
	node->next = obj->tail;
	obj->size++;
	}
	// 在第 index 个位置插入
	void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
	if (index < 0 \|\| index > obj->size) {
	return;
	}
	Node* node = nodeCreate(val);
	Node* cur = NULL;
	// 从右往左
	if (index > obj->size / 2) {
	cur = obj->tail;
	int n = obj->size - 1;
	while (n > index) {
	cur = cur->prev;
	n--;
	}
	} else {
	// 从左往右
	cur = obj->head->next;
	int n = 0;
	while (n < index) {
	cur = cur->next;
	n++;
	}
	}
	// 获取 cur 的前驱插入
	node->prev = cur->prev;
	node->prev->next = node;
	node->next = cur;
	cur->prev = node;
	obj->size++;
	}

	// 在第 index 个位置删除
	void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
	if (index < 0 \|\| index >= obj->size) {
	return;
	}
	Node* cur = NULL;
	// 从右往左
	if (index > obj->size / 2) {
	cur = obj->tail->prev;
	int n = obj->size - 1;
	while (n > index) {
	cur = cur->prev;
	n--;
	}
	} else {
	// 从左往右
	cur = obj->head->next;
	int n = 0;
	while (n < index) {
	cur = cur->next;
	n++;
	}
	}
	// 删除 cur
	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	free(cur);
	obj->size--;
	}
	// 释放链表
	void myLinkedListFree(MyLinkedList* obj) {
	// 首先释放里面的全部元素
	Node* head = obj->head;
	Node* tail = obj->tail;
	while (head != NULL) {
	Node* del = head;
	head = head->next;
	free(del);
	}
	free(obj);
	}

# 归并排序

	#include <stdlib.h>
	#include <cstring> //memcpy

	// 归并
	int* nnums;// 必须要全局，否则调用函数后，会清空当前栈的局部变量，应该
	int* mergeSort(int* nums, int l1, int r1) {
	if (l1 >= r1) {
	int s[1] = {nums[r1]};
	nnums = s;
	return nnums;
	}
	int mid = l1 + (r1 - l1) / 2;
	nnums = mergeSort(nums, l1, mid);
	int* lnums = (int*)calloc((mid - l1 + 1), sizeof(int));
	//int: 4 个字节
	// 2 3 4 5：4 个 int，16 个字节
	//nnums 为指针
	memcpy(lnums, nnums, sizeof(int) * (mid - l1 + 1));

	int* rnums = mergeSort(nums, mid + 1, r1);
	int nl = mid - l1 + 1;
	int nr = r1 - mid;
	int l = 0, r = 0, n = 0;
	int* tmp = (int*)calloc(r1 - l1 + 1, sizeof(int));
	while (l < nl \|\| r < nr) {
	int lnum = l == nl ? INT_MAX : lnums[l];
	int rnum = r == nr ? INT_MAX : rnums[r];
	if (lnum < rnum) {
	tmp[i++] = lnum;
	l++;
	} else {
	tmp[i++] = rnum;
	r++;
	}
	}
	nnums = tmp;
	return nnums;
	}

	int main(int argc, char const* argv[]) {
	int arr[] = {-1,23,23,01};
	int n = sizeof(arr) / sizeof(arr[0]);
	int* nums = mergeSort(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
	for (int i = 0; i < n; i++) {
	printf("%d ", nums[i]);
	}
	system("pause");
	return 0;
	}

# 堆排序

	// 堆排序，从大到小
	// 小根堆:k<2k+1,k<2k
	/* 调整以 key 为根的大根堆
	例如：1 3 2 1 5 7 调整为大根堆
	i = 3 , key = 1 以索引为 3 为根的大根堆
	2 * k > len return;
	1 3 2 1 5 7
	↑
	k

	------------------------------------------------------------

	i = 2，key = 2 以索引为 2 为根的大根堆
	--
	1 3 7 1 5 (2)
	↑ ↑
	k → k

	1 3 7 1 5 2 将 key 插入这个位置 nums [k] = key;
	------------------------------------------------------------
	i = 1, key = 3 , 以索引为 1 为根的大根堆

	-----
	1 7 (3) 1 5 2
	↑ ↑
	k → k

	1 7 5 1 (3) 2
	↑ ↑
	k → k

	1 7 5 1 3 2 将 key 插入这个位置 nums [k] = key;

	------------------------------------------------------------

	i = 0, key = 1 , 以索引为 0 为根的大根堆

	------
	7 (1) 5 1 3 2
	↑ ↑
	k → k
	-----
	7 5 (1) 1 3 2
	↑ ↑
	k → k
	-----
	7 5 3 1 (1) 2
	↑ ↑
	k → k
	7 5 3 1 1 2

	至此完成了大根堆的创建
	从上述可以看出，每次打括号的地方的索引：k 的当前位置赋值后
	需要取检查当前索引 k 为根索引是否为大根堆即 k *= 2;
	即要去检查： 2 * k , 2 * k + 1 ，二者的值是否大于 key
	*/

	// 从上往下调整堆
	void sink(int* nums, int i, int n) {
	int key = nums[i];
	for (int k = i * 2; k < n; k *= 2) {
	// 小根堆，选择小者
	if (k + 1 < n && nums[k] > nums[k + 1]) {
	k++;
	}
	// 满足条件
	if (key <= nums[k]) {
	break;
	}
	// 覆盖
	nums[i] = nums[k];
	i = k;
	}
	nums[i] = key;
	}

	void createHeap(int* nums, int n) {
	for (int k = n - 1; k >= 0; k--) {
	sink(nums, k, n);
	}
	}

	void swap(int* nums, int i, int j) {
	nums[i] ^= nums[j];
	nums[j] ^= nums[i];
	nums[i] ^= nums[j];
	}

	void heapSort(int* nums, int numsSize) {
	// 首先创建小根堆
	createHeap(nums, numsSize);

	// 从最后一个开始，此时堆顶是最小的元素 mVal
	// 将 mVal 与 lastIndex 交换位置，然后重复调整堆
	int lastIndex = numsSize - 1;
	while (lastIndex > 0) {
	swap(nums, 0, lastIndex);
	sink(nums, 0, lastIndex--);
	}
	}

	int main(int argc, char const* argv[]) {
	int arr[] = {10, 9, 8,6,43,21,412,3};
	int n = sizeof(arr) / sizeof(arr[0]);
	heapSort(arr, sizeof(arr) / sizeof(arr[0]) - 1);
	for (int i = 0; i < n; i++) {
	printf("%d ", arr[i]);
	}

	system("pause");
	return 0;
	}

# 快排

	// 快排
	int partition(int* nums, int left, int right) {
	// 选择枢纽，这里默认首元素
	int key = nums[left];
	int l = left;
	int r = right - 1;
	// 使得左边都小于 key，右边都大于 key
	while (l < r) {
	// 这里必须右指针先走，否则若 l 先走，则可能交换之后大的被交换过来
	// 因为枢纽为首元素
	while (l < r && nums[r] >= key) {
	r--;
	}
	//nums [r] 小于 key
	nums[l] = nums[r];

	while (l < r && nums[l] <= key) {
	l++;
	}
	nums[r] = nums[l];
	}
	nums[l] = key;
	return l;
	}
	void quickSort(int* nums, int l, int r) {
	if (l >= r) {
	return;
	}

	// 分区
	int m = partition(nums, l, r);

	// 递归左右区间
	quickSort(nums, l, m);
	quickSort(nums, m + 1, r);
	}

	int main(int argc, char const* argv[]) {
	int arr[] = {10,12,3,12,312,3,21, 9, 8, 3};
	int n = sizeof(arr) / sizeof(arr[0]);
	quickSort(arr, 0, sizeof(arr) / sizeof(arr[0]));
	for (int i = 0; i < n; i++) {
	printf("%d ", arr[i]);
	}

	system("pause");
	return 0;
	}

# 希尔排序

	// 希尔排序
	void shellSort(int* nums, int numsSize, int* ts, int tSize) {
	// 选取增量
	for (int k = 0; k < tSize; k++) {
	int t = ts[k];
	// 间隔为 t，进行直接插入排序
	for (int i = 0, j = i - t; i < numsSize; i += t, j = i - t) {
	int key = nums[i];
	while (j >= 0 && nums[j] > key) {
	nums[j + t] = nums[j];
	j -= t;
	}
	nums[j + t] = key;
	}
	}
	}

# 折半插入排序

	// 折半插入排序
	void binarySearch(int* nums, int numsSize) {
	for (int i = 0; i < numsSize; i++) {
	int l = 0;
	int r = i - 1;
	while (l < r) {
	int m = (l + r) / 2;
	if (nums[m] >= nums[i]) {
	// 2 3
	r = m;
	} else {
	l = m + 1;
	}
	}
	nums[l] = nums[i];
	for (int j = i; j > l; j--) {
	nums[j] = nums[j - 1];
	}
	}
	}

# 简单选择排序

	#define min(a, b) (((a) > (b)) ? (b) : (a))

	// 简单选择排序；每次选择最小的
	void selectSort(int* nums, int numsSize) {
	for (int i = 0; i < numsSize; i++) {
	int m = nums[i];
	for (int j = i + 1; j < numsSize; j++) {
	m = min(nums[j], m);
	}
	nums[i] = m;
	}
	}

# 直接插入排序

	// 直接插入排序
	void insertSort(int* nums, int numsSize) {
	for (int i = 0; i < numsSize; i++) {
	int num = nums[i];
	int j = i - 1;
	while (j > 0 && nums[j] > num) {
	nums[j + 1] = nums[j];
	j--;
	}
	nums[j] = num;
	}
	}

# 冒泡排序

	#define max(a, b) (((a) < (b)) ? (b) : (a))


	void swap(int* nums, int i, int j) {
	nums[i] ^= nums[j];
	nums[j] ^= nums[i];
	nums[i] ^= nums[j];
	}

	// 冒泡排序，升序
	void bubbleSort(int* nums, int numsSize) {
	// 遇到反着的交换位置
	int n = numsSize;
	for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
	if (nums[j] < nums[i]) {
	swap(nums, i, j);
	}
	}
	}
	}

# 8 大排序比较

排序算法	时间复杂度	空间复杂度	是否稳定	最佳情况	最坏情况	适用场景
冒泡排序	O(n^2)	O(1)	是	O(n)	O(n^2)	小型数据集
选择排序	O(n^2)	O(1)	否	O(n^2)	O(n^2)	不适合大型数据集
插入排序	O(n^2)	O(1)	是	O(n)	O(n^2)	小型数据集或基本有序数据集
希尔排序	O(nlog^2 n)	O(1)	否	-	-	大型数据集
归并排序	O(nlogn)	O(n)	是	O(nlogn)	O(nlogn)	大型数据集但需额外内存空间
快速排序	O(nlogn)	O(logn)	否	O(nlogn)	O(n^2)	大型数据集
堆排序	O(nlogn)	O(1)	否	O(nlogn)	O(nlogn)	大型数据集但不稳定
计数排序	O(n+k)	O(n+k)	是	O(n+k)	O(n+k)	数据范围不大的整数排序

# KMP 算法

# 28. 实现 strStr ()

力扣题目链接 (opens new window)

实现 strStr () 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。

示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2

示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明：当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr () 以及 Java 的 indexOf () 定义相符。

# 思路

本题是 KMP 经典题目。

以下文字如果看不进去，可以看我的 B 站视频：

KMP 的经典思想就是: 当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

本篇将以如下顺序来讲解 KMP，

什么是 KMP
KMP 有什么用
什么是前缀表
为什么一定要用前缀表
如何计算前缀表
前缀表与 next 数组
使用 next 数组来匹配
时间复杂度分析
构造 next 数组
使用 next 数组来做匹配
前缀表统一减一 C++ 代码实现
前缀表（不减一）C++ 实现
总结

读完本篇可以顺便把 leetcode 上 28. 实现 strStr () 题目做了。

# 什么是 KMP

说到 KMP，先说一下 KMP 这个名字是怎么来的，为什么叫做 KMP 呢。

因为是由这三位学者发明的：Knuth，Morris 和 Pratt，所以取了三位学者名字的首字母。所以叫做 KMP

# KMP 有什么用

KMP 主要应用在字符串匹配上。

KMP 的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

所以如何记录已经匹配的文本内容，是 KMP 的重点，也是 next 数组肩负的重任。

其实 KMP 的代码不好理解，一些同学甚至直接把 KMP 代码的模板背下来。

没有彻底搞懂，懵懵懂懂就把代码背下来太容易忘了。

不仅面试的时候可能写不出来，如果面试官问：next 数组里的数字表示的是什么，为什么这么表示？

估计大多数候选人都是懵逼的。

下面 Carl 就带大家把 KMP 的精髓，next 数组弄清楚。

# 什么是前缀表

写过 KMP 的同学，一定都写过 next 数组，那么这个 next 数组究竟是个啥呢？

next 数组就是一个前缀表（prefix table）。

前缀表有什么作用呢？

前缀表是用来回退的，它记录了模式串与主串 (文本串) 不匹配的时候，模式串应该从哪里开始重新匹配。

为了清楚的了解前缀表的来历，我们来举一个例子：

要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

请记住文本串和模式串的作用，对于理解下文很重要，要不然容易看懵。所以说三遍：

要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

如动画所示：

动画里，我特意把子串 aa 标记上了，这是有原因的，大家先注意一下，后面还会说道。

可以看出，文本串中第六个字符 b 和模式串的第六个字符 f，不匹配了。如果暴力匹配，会发现不匹配，此时就要从头匹配了。

但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符 b 继续开始匹配。

此时就要问了前缀表是如何记录的呢？

首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

那么什么是前缀表：记录下标 i 之前（包括 i）的字符串中，有多大长度的相同前缀后缀。

# 最长公共前后缀？

文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

正确理解什么是前缀什么是后缀很重要！

那么网上清一色都说 “kmp 最长公共前后缀” 又是什么回事呢？

我查了一遍算法导论和算法 4 里 KMP 的章节，都没有提到 “最长公共前后缀” 这个词，也不知道从哪里来了，我理解是用 “最长相等前后缀” 更准确一些。

因为前缀表要求的就是 $\color{red}相同前后缀的长度。$

而最长公共前后缀里面的 “公共”，更像是说前缀和后缀公共的长度。这其实并不是前缀表所需要的。

所以字符串 a 的最长相等前后缀为 0。字符串 aa 的最长相等前后缀为 1。字符串 aaa 的最长相等前后缀为 2。等等.....。

# 为什么一定要用前缀表

这就是前缀表，那为啥就能告诉我们上次匹配的位置，并跳过去呢？

回顾一下，刚刚匹配的过程在下标 5 的地方遇到不匹配，模式串是指向 f，如图：

然后就找到了下标 2，指向 b，继续匹配：如图：

以下这句话，对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配非常重要！

下标 5 之前这部分的字符串（也就是字符串 aabaa）的最长相等的前缀和后缀字符串是子字符串 aa ，因为找到了最长相等的前缀和后缀 $\color{red}匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。$

所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

很多介绍 KMP 的文章或者视频并没有把为什么要用前缀表？这个问题说清楚，而是直接默认使用前缀表。

# 如何计算前缀表

接下来就要说一说怎么计算前缀表。

如图：

长度为前 1 个字符的子串 a ，最长相同前后缀的长度为 0。（注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。）

aa ，最长相同前后缀的长度为 1。

长度为前 3 个字符的子串 aab ，最长相同前后缀的长度为 0。

以此类推：长度为前 4 个字符的子串 aaba ，最长相同前后缀的长度为 1。长度为前 5 个字符的子串 aabaa ，最长相同前后缀的长度为 2。长度为前 6 个字符的子串 aabaaf ，最长相同前后缀的长度为 0。

那么把求得的最长相等前后缀的长度就是对应前缀表的元素，如图：

可以看出模式串与前缀表对应位置的数字表示的就是：下标 i 之前（包括 i）的字符串中，有多大长度的相同前缀后缀。

再来看一下如何利用前缀表找到当字符不匹配的时候应该指针应该移动的位置。如动画所示：

找到的不匹配的位置，那么此时我们要看它的前一个字符的前缀表的数值是多少。

为什么要前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。

所以要看前一位的前缀表的数值。

前一个字符的前缀表的数值是 2，所有把下标移动到下标 2 的位置继续比配。可以再反复看一下上面的动画。

最后就在文本串中找到了和模式串匹配的子串了。

# 前缀表与 next 数组

很多 KMP 算法的时间都是使用 next 数组来做回退操作，那么 next 数组与前缀表有什么关系呢？

next 数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为 - 1）之后作为 next 数组。

为什么这么做呢，其实也是很多文章视频没有解释清楚的地方。

其实这并不涉及到 KMP 的原理，而是具体实现，next 数组即可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为 - 1）。

后面我会提供两种不同的实现代码，大家就明白了。

# 使用 next 数组来匹配

以下我们以前缀表统一减一之后的 next 数组来做演示。

有了 next 数组，就可以根据 next 数组来匹配文本串 s，和模式串 t 了。

注意 next 数组是新前缀表（旧前缀表统一减一了）。

匹配过程动画如下：

# 时间复杂度分析

其中 n 为文本串长度，m 为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是 O (n)，之前还要单独生成 next 数组，时间复杂度是 O (m)。所以整个 KMP 算法的时间复杂度是 O (n+m) 的。

暴力的解法显而易见是 O (n × m)，所以 KMP 在字符串匹配中极大的提高的搜索的效率。

为了和力扣题目 28. 实现 strStr 保持一致，方便大家理解，以下文章统称 haystack 为文本串，needle 为模式串。

都知道使用 KMP 算法，一定要构造 next 数组。

# 构造 next 数组

我们定义一个函数 getNext 来构建 next 数组，函数参数为指向 next 数组的指针，和一个字符串。代码如下：

void getNext(int* next, const string& s)

构造 next 数组其实就是计算模式串 s，前缀表的过程。 主要有如下三步：

初始化
处理前后缀不相同的情况
处理前后缀相同的情况

接下来我们详解详解一下。

初始化：

定义两个指针 i 和 j，j 指向前缀末尾位置，i 指向后缀末尾位置。

然后还要对 next 数组进行初始化赋值，如下：

	int j = -1;
	next[0] = j;

j 为什么要初始化为 -1 呢，因为之前说过前缀表要统一减一的操作仅仅是其中的一种实现，我们这里选择 j 初始化为 - 1，下文我还会给出 j 不初始化为 - 1 的实现代码。

next [i] 表示 i（包括 i）之前最长相等的前后缀长度（其实就是 j）

所以初始化 next [0] = j 。

处理前后缀不相同的情况

因为 j 初始化为 - 1，那么 i 就从 1 开始，进行 s [i] 与 s [j+1] 的比较。

所以遍历模式串 s 的循环下标 i 要从 1 开始，代码如下：

for (int i = 1; i < s.size(); i++) {

如果 s [i] 与 s [j+1] 不相同，也就是遇到前后缀末尾不相同的情况，就要向前回退。

怎么回退呢？

next [j] 就是记录着 j（包括 j）之前的子串的相同前后缀的长度。

那么 s [i] 与 s [j+1] 不相同，就要找 j+1 前一个元素在 next 数组里的值（就是 next [j]）。

所以，处理前后缀不相同的情况代码如下：

	while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
	j = next[j]; // 向前回退，回退到之前匹配的位置
	// aabaabaaf
	// aabaaf
	}

处理前后缀相同的情况

如果 s [i] 与 s [j + 1] 相同，那么就同时向后移动 i 和 j 说明找到了相同的前后缀，同时还要将 j（前缀的长度）赋给 next [i], 因为 next [i] 要记录相同前后缀的长度。

代码如下：

	if (s[i] == s[j + 1]) { // 找到相同的前后缀
	j++;
	}
	next[i] = j;

最后整体构建 next 数组的函数代码如下：

	void getNext(int* next, const string& s){
	int j = -1;
	next[0] = j;
	for(int i = 1; i < s.size(); i++) { // 注意 i 从 1 开始
	while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
	j = next[j]; // 向前回退，回退到之前匹配的位置
	}
	if (s[i] == s[j + 1]) { // 找到相同的前后缀
	j++;
	}
	next[i] = j; // 将 j（前缀的长度）赋给 next [i]
	}
	}

代码构造 next 数组的逻辑流程动画如下：

得到了 next 数组之后，就要用这个来做匹配了。

# 使用 next 数组来做匹配

在文本串 s 里找是否出现过模式串 t。

定义两个下标 j 指向模式串起始位置，i 指向文本串起始位置。

那么 j 初始值依然为 - 1，为什么呢？ 依然因为 next 数组里记录的起始位置为 - 1。

i 就从 0 开始，遍历文本串，代码如下：

for (int i = 0; i < s.size(); i++)

接下来就是 s [i] 与 t [j + 1] （因为 j 从 - 1 开始的）进行比较。

如果 s [i] 与 t [j + 1] 不相同，j 就要从 next 数组里寻找下一个匹配的位置。

代码如下：

	while(j >= 0 && s[i] != t[j + 1]) {
	j = next[j];
	}

如果 s [i] 与 t [j + 1] 相同，那么 i 和 j 同时向后移动，代码如下：

	if (s[i] == t[j + 1]) {
	j++; //i 的增加在 for 循环里
	}

如何判断在文本串 s 里出现了模式串 t 呢，如果 j 指向了模式串 t 的末尾，那么就说明模式串 t 完全匹配文本串 s 里的某个子串了。

本题要在文本串字符串中找出模式串出现的第一个位置 (从 0 开始)，所以返回当前在文本串匹配模式串的位置 i 减去模式串的长度，就是文本串字符串中出现模式串的第一个位置。

代码如下：

	if (j == (t.size() - 1) ) {
	return (i - t.size() + 1);
	}

那么使用 next 数组，用模式串匹配文本串的整体代码如下：

	int j = -1; // 因为 next 数组里记录的起始位置为 - 1
	for (int i = 0; i < s.size(); i++) { // 注意 i 就从 0 开始
	while(j >= 0 && s[i] != t[j + 1]) { // 不匹配
	j = next[j]; //j 寻找之前匹配的位置
	}
	if (s[i] == t[j + 1]) { // 匹配，j 和 i 同时向后移动
	j++; //i 的增加在 for 循环里
	}
	if (j == (t.size() - 1) ) { // 文本串 s 里出现了模式串 t
	return (i - t.size() + 1);
	}
	}

此时所有逻辑的代码都已经写出来了，力扣 28. 实现 strStr 题目的整体代码如下：

# 前缀表统一减一 C++ 代码实现

	class Solution {
	public:
	void getNext(int* next, const string& s) {
	int j = -1;
	next[0] = j;
	for(int i = 1; i < s.size(); i++) { // 注意 i 从 1 开始
	while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
	j = next[j]; // 向前回退
	}
	if (s[i] == s[j + 1]) { // 找到相同的前后缀
	j++;
	}
	next[i] = j; // 将 j（前缀的长度）赋给 next [i]
	}
	}
	int strStr(string haystack, string needle) {
	if (needle.size() == 0) {
	return 0;
	}
	int next[needle.size()];
	getNext(next, needle);
	int j = -1; //// 因为 next 数组里记录的起始位置为 - 1
	for (int i = 0; i < haystack.size(); i++) { // 注意 i 就从 0 开始
	while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
	j = next[j]; //j 寻找之前匹配的位置
	}
	if (haystack[i] == needle[j + 1]) { // 匹配，j 和 i 同时向后移动
	j++; //i 的增加在 for 循环里
	}
	if (j == (needle.size() - 1) ) { // 文本串 s 里出现了模式串 t
	return (i - needle.size() + 1);
	}
	}
	return -1;
	}
	};

# 前缀表（不减一）C++ 实现

那么前缀表就不减一了，也不右移的，到底行不行呢？

行！

我之前说过，这仅仅是 KMP 算法实现上的问题，如果就直接使用前缀表可以换一种回退方式，找 j=next [j-1] 来进行回退。

主要就是 j=next [x] 这一步最为关键！

我给出的 getNext 的实现为：（前缀表统一减一）

	void getNext(int* next, const string& s) {
	int j = -1;
	next[0] = j;
	for(int i = 1; i < s.size(); i++) { // 注意 i 从 1 开始
	while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
	j = next[j]; // 向前回退
	}
	if (s[i] == s[j + 1]) { // 找到相同的前后缀
	j++;
	}
	next[i] = j; // 将 j（前缀的长度）赋给 next [i]
	}
	}

此时如果输入的模式串为 aabaaf，对应的 next 为 - 1 0 -1 0 1 -1。

这里 j 和 next [0] 初始化为 - 1，整个 next 数组是以前缀表减一之后的效果来构建的。

那么前缀表不减一来构建 next 数组，代码如下：

	void getNext(int* next, const string& s) {
	int j = 0;
	next[0] = 0;
	for(int i = 1; i < s.size(); i++) {
	while (j > 0 && s[i] != s[j]) { //j 要保证大于 0，因为下面有取 j-1 作为数组下标的操作
	j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
	}
	if (s[i] == s[j]) {
	j++;
	}
	next[i] = j;
	}
	}

此时如果输入的模式串为 aabaaf，对应的 next 为 0 1 0 1 2 0，（其实这就是前缀表的数值了）。

那么用这样的 next 数组也可以用来做匹配，代码要有所改动。

实现代码如下：

	class Solution {
	public:
	void getNext(int* next, const string& s) {
	int j = 0;
	next[0] = 0;
	for(int i = 1; i < s.size(); i++) {
	while (j > 0 && s[i] != s[j]) {
	j = next[j - 1];
	}
	if (s[i] == s[j]) {
	j++;
	}
	next[i] = j;
	}
	}
	int strStr(string haystack, string needle) {
	if (needle.size() == 0) {
	return 0;
	}
	int next[needle.size()];
	getNext(next, needle);
	int j = 0;
	for (int i = 0; i < haystack.size(); i++) {
	while(j > 0 && haystack[i] != needle[j]) {
	j = next[j - 1];
	}
	if (haystack[i] == needle[j]) {
	j++;
	}
	if (j == needle.size() ) {
	return (i - needle.size() + 1);
	}
	}
	return -1;
	}
	};

# 总结

我们介绍了什么是 KMP，KMP 可以解决什么问题，然后分析 KMP 算法里的 next 数组，知道了 next 数组就是前缀表，再分析为什么要是前缀表而不是什么其他表。

接着从给出的模式串中，我们一步一步的推导出了前缀表，得出前缀表无论是统一减一还是不减一得到的 next 数组仅仅是 kmp 的实现方式的不同。

其中还分析了 KMP 算法的时间复杂度，并且和暴力方法做了对比。

然后先用前缀表统一减一得到的 next 数组，求得文本串 s 里是否出现过模式串 t，并给出了具体分析代码。

又给出了直接用前缀表作为 next 数组，来做匹配的实现代码。

可以说把 KMP 的每一个细微的细节都扣了出来，毫无遮掩的展示给大家了！

# 其他语言版本

Java：

	class Solution {
	/**
	* 基于窗口滑动的算法
	* <p>
	* 时间复杂度：O (m*n)
	* 空间复杂度：O (1)
	* 注：n 为 haystack 的长度，m 为 needle 的长度
	*/
	// 双指针
	public int strStr(String haystack, String needle) {
	// 若 needle 为空返回 0
	if(needle == null){
	return 0;
	}
	int left = 0 ;
	char[] h = haystack.toCharArray();
	char[] n = needle.toCharArray();
	//haystack 的长度小于 needle 的长度返回 - 1
	if(h.length < n.length){
	return -1;
	}
	// 记录 needle 的长度
	int length = n.length ;
	// 循环 haystack
	while(left < h.length){
	int right = left;
	int index = 0 ;// 记录 needle 的下标
	while(right < h.length && h[right] == n[index]){
	//h 中相同子串的长度等于 n 的长度直接返回 left
	if(length==( index+1)){
	return left;
	}
	right++;
	index++;
	}
	left++;
	}
	return -1;

	}
	}

	// 方法一
	class Solution {
	public void getNext(int[] next, String s){
	int j = -1;
	next[0] = j;
	for (int i = 1; i<s.length(); i++){
	while(j>=0 && s.charAt(i) != s.charAt(j+1)){
	j=next[j];// 向前回退，回退到之前匹配的位置
	}

	if(s.charAt(i)==s.charAt(j+1)){
	j++;
	}
	next[i] = j;
	}
	}
	public int strStr(String haystack, String needle) {
	if(needle.length()==0){
	return 0;
	}

	int[] next = new int[needle.length()];
	getNext(next, needle);
	int j = -1;
	for(int i = 0; i<haystack.length();i++){
	while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
	j = next[j];
	}
	if(haystack.charAt(i)==needle.charAt(j+1)){
	j++;
	}
	if(j==needle.length()-1){ // aabaabaaf
	//aabaaf 最后 j=4 , 因为 needle.length ()=3 , 匹配成功 j=0 开始
	return (i-needle.length()+1);
	}
	}

	return -1;
	}
	}

	class Solution {
	// 前缀表（不减一）Java 实现
	public int strStr(String haystack, String needle) {
	if (needle.length() == 0) return 0;
	int[] next = new int[needle.length()];
	getNext(next, needle);

	int j = 0;
	for (int i = 0; i < haystack.length(); i++) {
	while (j > 0 && needle.charAt(j) != haystack.charAt(i))
	j = next[j - 1];
	if (needle.charAt(j) == haystack.charAt(i))
	j++;
	if (j == needle.length())
	return i - needle.length() + 1;
	}
	return -1;

	}

	private void getNext(int[] next, String s) {
	int j = 0;
	next[0] = 0;
	for (int i = 1; i < s.length(); i++) {
	while (j > 0 && s.charAt(j) != s.charAt(i))
	j = next[j - 1];
	if (s.charAt(j) == s.charAt(i))
	j++;
	next[i] = j;
	}
	}
	}

# 459. 重复的子字符串

力扣题目链接 (opens new window)

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过 10000。

示例 1:
输入: "abab"
输出: True
解释：可由子字符串 "ab" 重复两次构成。

示例 2:
输入: "aba"
输出: False

示例 3:
输入: "abcabcabcabc"
输出: True
解释：可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

# #思路

暴力的解法，就是一个 for 循环获取子串的终止位置，然后判断子串是否能重复构成字符串，又嵌套一个 for 循环，所以是 O (n^2) 的时间复杂度。

有的同学可以想，怎么一个 for 循环就可以获取子串吗？至少得一个 for 获取子串起始位置，一个 for 获取子串结束位置吧。

其实我们只需要判断，以第一个字母为开始的子串就可以，所以一个 for 循环获取子串的终止位置就行了。而且遍历的时候都不用遍历结束，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。

暴力的解法，这里就不讲了。

主要讲一讲移动匹配和 KMP 两种方法。

# #移动匹配

当一个字符串 s：abcabc，内部又重复的子串组成，那么这个字符串的结构一定是这样的：

也就是又前后又相同的子串组成。

那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前后的子串做后串，就一定还能组成一个 s，如图：

所以判断字符串 s 是否有重复子串组成，只要两个 s 拼接在一起，里面还出现一个 s 的话，就说明是又重复子串组成。

当然，我们在判断 s + s 拼接的字符串里是否出现一个 s 的的时候，要刨除 s + s 的首字符和尾字符，这样避免在 s+s 中搜索出原来的 s，我们要搜索的是中间拼接出来的 s。

代码如下：

	class Solution {
	public:
	bool repeatedSubstringPattern(string s) {
	string t = s + s;
	t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
	if (t.find(s) != std::string::npos) return true; // r
	return false;
	}
	};

不过这种解法还有一个问题，就是我们最终还是要判断一个字符串（s + s）是否出现过 s 的过程，大家可能直接用 contains，find 之类的库函数。却忽略了实现这些函数的时间复杂度（暴力解法是 m * n，一般库函数实现为 O (m + n)）。

如果我们做过 28. 实现 strStr (opens new window) 题目的话，其实就知道，实现一个高效的算法来判断一个字符串中是否出现另一个字符串是很复杂的，这里就涉及到了 KMP 算法。

# #KMP

# #为什么会使用 KMP

以下使用 KMP 方式讲解，强烈建议大家先把一下两个视频看了，理解 KMP 算法，在来看下面讲解，否则会很懵。

在一个串中查找是否出现过另一个串，这是 KMP 的看家本领。那么寻找重复子串怎么也涉及到 KMP 算法了呢？

KMP 算法中 next 数组为什么遇到字符不匹配的时候可以找到上一个匹配过的位置继续匹配，靠的是有计算好的前缀表。前缀表里，统计了各个位置为终点字符串的最长相同前后缀的长度。

那么最长相同前后缀和重复子串的关系又有什么关系呢。

可能很多录友又忘了前缀和后缀的定义，在回顾一下：

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串，这里那字符串 s：abababab 来举例，ab 就是最小重复单位，如图所示：

# #如何找到最小重复子串

这里有同学就问了，为啥一定是开头的 ab 呢。其实最关键还是要理解最长相等前后缀，如图：

步骤一：因为这是相等的前缀和后缀，t [0] 与 k [0] 相同， t [1] 与 k [1] 相同，所以 s [0] 一定和 s [2] 相同，s [1] 一定和 s [3] 相同，即：，s [0] s [1] 与 s [2] s [3] 相同。

步骤二：因为在同一个字符串位置，所以 t [2] 与 k [0] 相同，t [3] 与 k [1] 相同。

步骤三：因为这是相等的前缀和后缀，t [2] 与 k [2] 相同，t [3] 与 k [3] 相同，所以，s [2] 一定和 s [4] 相同，s [3] 一定和 s [5] 相同，即：s [2] s [3] 与 s [4] s [5] 相同。

步骤四：循环往复。

所以字符串 s，s [0] s [1] 与 s [2] s [3] 相同， s [2] s [3] 与 s [4] s [5] 相同，s [4] s [5] 与 s [6] s [7] 相同。

正是因为最长相等前后缀的规则，当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串。

# #简单推理

这里在给出一个数推导，就容易理解很多。

假设字符串 s 使用多个重复子串构成（这个子串是最小重复单位），重复出现的子字符串长度是 x，所以 s 是由 n * x 组成。

因为字符串 s 的最长相同前后缀的的长度一定是不包含 s 本身，所以最长相同前后缀长度必然是 m * x，而且 n - m = 1，（这里如果不懂，看上面的推理）

所以如果 nx % (n - m) x = 0，就可以判定有重复出现的子字符串。

next 数组记录的就是最长相同前后缀字符串：KMP 算法精讲 (opens new window) 这里介绍了什么是前缀，什么是后缀，什么又是最长相同前后缀)，如果 next [len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

最长相等前后缀的长度为：next [len - 1] + 1。(这里的 next 数组是以统一减一的方式计算的，因此需要 + 1，两种计算 next 数组的具体区别看这里：字符串：KMP 算法精讲 (opens new window))

数组长度为：len。

如果 len % (len - (next [len - 1] + 1)) == 0 ，则说明数组的长度正好可以被 (数组长度 - 最长相等前后缀的长度) 整除，说明该字符串有重复的子字符串。

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

强烈建议大家把 next 数组打印出来，看看 next 数组里的规律，有助于理解 KMP 算法

如图：

next [len - 1] = 7，next [len - 1] + 1 = 8，8 就是此时字符串 asdfasdfasdf 的最长相同前后缀的长度。

(len - (next [len - 1] + 1)) 也就是： 12 (字符串的长度) - 8 (最长公共前后缀的长度) = 4 (最小重复子串的长度)， 4 正好可以被 12 (字符串的长度) 整除，所以说明有重复的子字符串（asdf）。

C++ 代码如下：（这里使用了前缀表统一减一的实现方式）

	class Solution {
	public:
	void getNext (int* next, const string& s){
	next[0] = -1;
	int j = -1;
	for(int i = 1;i < s.size(); i++){
	while(j >= 0 && s[i] != s[j + 1]) {
	j = next[j];
	}
	if(s[i] == s[j + 1]) {
	j++;
	}
	next[i] = j;
	}
	}
	bool repeatedSubstringPattern (string s) {
	if (s.size() == 0) {
	return false;
	}
	int next[s.size()];
	getNext(next, s);
	int len = s.size();
	if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
	return true;
	}
	return false;
	}
	};

前缀表（不减一）的 C++ 代码实现：

	class Solution {
	public:
	void getNext (int* next, const string& s){
	next[0] = 0;
	int j = 0;
	for(int i = 1;i < s.size(); i++){
	while(j > 0 && s[i] != s[j]) {
	j = next[j - 1];
	}
	if(s[i] == s[j]) {
	j++;
	}
	next[i] = j;
	}
	}
	bool repeatedSubstringPattern (string s) {
	if (s.size() == 0) {
	return false;
	}
	int next[s.size()];
	getNext(next, s);
	int len = s.size();
	if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
	return true;
	}
	return false;
	}
	};

# #其他语言版本

Java：

	class Solution {
	//KMP
	public boolean repeatedSubstringPattern(String s) {
	int j = -1 ;
	int[] next = new int[s.length()];
	next[0] = j;
	char[] cs = s.toCharArray();
	// 计算 next 数组
	for(int i = 1 ; i < cs.length ; i++ ){
	while(j >= 0 && cs[i] != cs[j+1]){
	j = next[j];// 回退 next [j] 保存的就是最长相等前缀的长度，但是第一个索引位置为 0
	}
	if(cs[i] == cs[j+1]){
	j++;
	}
	next[i] = j;
	}
	int length = next.length;
	//length-(next [length-1]+1) 就是最小重复字串的长度
	if(next[length-1] >=0 && length%(length-(next[length-1]+1))==0){
	return true;
	}
	return false;
	}


	// 移动匹配
	public boolean repeatedSubstringPattern1(String s) {
	String t = s;
	s = s+s;
	s = s.substring(1,s.length()-1);
	//abaaba
	return s.contains(t);
	}
	}

# 最长回文子串

5. 最长回文子串

难度中等 6006

给你一个字符串 s ，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

通过次数 1,285,308

提交次数 3,444,060

# dp

直接用 $\text{String[][]}$ dp

	class Solution {
	public String longestPalindrome(String s) {
	// b a b a d
	// b t f t f f
	// a t f t f
	// b t f f
	// a t f
	// b t
	//dp [i][j] 区间 i ~ j 之间是不是回文子串
	// s[i] = s[j]
	// dp[i][j] = dp[i + 1][j - 1];
	// s[i] != s[j]
	// dp[i][j] = false;
	String max = "";
	int n = s.length();
	String[][] dp = new String[n][n];
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	dp[i][j] = "";
	}
	}
	for (int i = n - 1; i >= 0; i--) {
	for (int j = i; j < n; j++) {
	if (s.charAt(i) == s.charAt(j)) {
	if (j - i <= 1) {
	if (j - i == 1) {
	dp[i][j] = s.charAt(i) + "" + s.charAt(j);
	if (max.length() <= 1) {
	max = s.charAt(i) + "" + s.charAt(j);
	}
	}else {
	dp[i][j] = s.charAt(i) + "";
	if (max.length() < 1) {
	max = s.charAt(i) + "" ;
	}
	}
	}else if (!dp[i + 1][j - 1].equals("")) {
	dp[i][j] = s.charAt(i) + dp[i + 1][j - 1] + s.charAt(j);
	if (max.length() < dp[i][j].length()) {
	max = dp[i][j];
	}
	}
	}
	}
	}
	return max;
	}
	}

//dp

	class Solution {
	public String longestPalindrome(String s) {
	// b a b a d
	// b t f t f f
	// a t f t f
	// b t f f
	// a t f
	// b t
	//dp [i][j] 区间 i ~ j 之间是不是回文子串
	// s[i] = s[j]
	// dp[i][j] = dp[i + 1][j - 1];
	// s[i] != s[j]
	// dp[i][j] = false;
	int n = s.length();
	boolean[][] dp = new boolean[s.length()][s.length()];
	int begin = 0;
	int end = 0;
	for (int i = s.length() - 1; i >= 0; i--) {
	for (int j = i; j < s.length(); j++) {
	if(s.charAt(i) == s.charAt(j)){
	if(j - i <= 1){
	dp[i][j] = true;
	}else if(dp[i + 1][j - 1]){
	dp[i][j] = true;
	}
	if (dp[i][j]) {// 是回文
	if (end - begin < j - i) {
	begin = i;
	end = j;
	}
	}
	}
	}
	}
	return s.substring(begin, end + 1);
	}
	}

# 中心扩展

	class Solution {
	public String longestPalindrome(String s) {
	int left = 0;
	int right = 0;
	for (int i = 0; i < s.length(); i++) {
	// 奇
	int[] ji = extend(s, i, i);
	int[] ou = extend(s, i, i + 1);
	int l = ou[0];
	int r = ou[1];
	if (ji[1] - ji[0] > ou[1] - ou[0]) {
	l = ji[0];
	r = ji[1];
	}
	if (r - l > right - left) {
	left = l;
	right = r;
	}
	}
	return s.substring(left, right + 1);
	}

	public int[] extend(String s, int left, int right) {
	int l = 1;
	int r = -1;
	while(left >= 0 && right < s.length()){
	if(s.charAt(left) != s.charAt(right)){
	return new int[]{l, r};
	}
	l = left;
	r = right;
	left--;
	right++;
	}
	return new int[]{l, r};
	}
	}

# Manacher's Algorithm 马拉车算法

0 1 2 3 4 5 6 7 8 9 10 11 12 
# a # b # a # b # a # d # 
0 1 0 3 0 5 0 3 0 1 0 1 0

	class Solution {
	public String longestPalindrome(String s) {
	// 追加 # 使得 s 变成奇数个统一处理
	StringBuilder builder = new StringBuilder();
	int n = s.length();
	for (int i = 0; i < n; i++) {
	builder.append("#");
	builder.append(s.charAt(i));
	}
	builder.append("#");
	char[] t = builder.toString().toCharArray();
	// 最大回文子串的开始索引
	int leftIndex = 0;
	// 最大回文子串的长度
	int maxLen = 0;

	//p 数组，保存从中心扩展的最大个数
	// 0 1 2 3
	// 例如: c b b d

	// 0 1 2 3 4 5 6 7 8
	// t: # c # b # b # d #
	// p: 0 1 0 1 2 1 0 1 0
	int[] p = new int[2 * n + 1];
	// 中心
	int center = 0;
	// 中心的最右边界 :
	int maxRight = 0;
	//i 关于中心 center 的镜像
	int i_mirror = 0;
	for (int i = 0; i < 2 * n + 1; i++) {
	i_mirror = 2 * center - i;
	// 在中心的半径范围之内，在范围之外直接需要中心扩展
	if (maxRight > i) {
	// 三种情况的综合
	//maxRight - i : i 的位置到达最右边界的长度
	// 1.p[i_mirror] < maxRight - i
	// 在长度范围之内 : p [i] = p [i_mirror]
	// 2.p[i_mirror] == maxRight - i
	// 刚好在长度边界上 : p [i] >= p [i_mirror]
	// 有可能也需要从边界 maxRight 中心扩展
	// 3.p[i_mirror] > maxRight - i
	// 最大个数大于了长度 : p [i] = maxRight - i
	p[i] = Math.min(maxRight - i, p[i_mirror]);
	}

	// 中心扩展，从边界 + 1 开始进行扩展
	int left = i - (p[i] + 1);
	int right = i + (p[i] + 1);
	while (left >= 0 && right < 2 * n + 1
	&& t[left] == t[right]) {
	p[i]++;
	left--;
	right++;
	}

	// 更新 center 与 maxRight
	// 扩展后的范围大于了中心最右边界
	if (p[i] + i > maxRight) {
	maxRight = p[i] + i;
	center = i;
	}

	// 更新最大回文子串
	if (p[i] > maxLen) {
	maxLen = p[i];
	// 原数组下标: (当前 p 的下标 - maxLen) / 2
	leftIndex = (i - maxLen) / 2;
	}
	}

	// 测试输出
	for (int i = 0; i < 2 * n + 1; i++) {
	System.out.print(i + " ");
	}
	System.out.println();
	for (int i = 0; i < 2 * n + 1; i++) {
	System.out.print(t[i] + " ");
	}
	System.out.println();
	for (int i : p) {
	System.out.print(i + " ");
	}
	return s.substring(leftIndex, leftIndex + maxLen);
	}
	}

数据结构

	typedef struct MyLinkedList{
	int size;
	Node head, tail;
	} MyLinkedList;